"""Authored square assignment demo. No external solver, real staffing or API."""
import itertools,json

def solve(C):
    n=len(C)
    if not 1<=n<=9 or any(len(r)!=n for r in C):raise ValueError('small square matrix required')
    if any(type(x)is not int or x<0 for r in C for x in r):raise ValueError('nonnegative integer costs required')
    # dp[mask] is the best cost after assigning the first bit_count(mask) rows.
    dp={0:0};parent={};trace=[]
    for mask in range(1<<n):
        if mask not in dp:continue
        i=mask.bit_count()
        if i==n:continue
        for j in range(n):
            if mask>>j&1:continue
            new=mask|1<<j;value=dp[mask]+C[i][j]
            improved=new not in dp or value<dp[new]
            trace.append({'mask':mask,'row':i,'column':j,'next_mask':new,'candidate':value,'improved':improved})
            if improved:dp[new]=value;parent[new]=(mask,j)
    m=(1<<n)-1;cols=[]
    while m:old,j=parent[m];cols.append(j);m=old
    cols.reverse()
    assert len(set(cols))==n and sum(C[i][j] for i,j in enumerate(cols))==dp[(1<<n)-1]
    return {'cost':dp[(1<<n)-1],'columns_by_row':cols,'dp_by_mask':{str(k):v for k,v in sorted(dp.items())},'relaxations':trace}

def demo():
    C=[[1,2,3],[1,100,100],[100,2,1]];result=solve(C)
    all_perm=[{'columns':list(p),'cost':sum(C[i][j] for i,j in enumerate(p))} for p in itertools.permutations(range(3))]
    unused=set(range(3));greedy=[]
    for i in range(3):
        j=min(unused,key=lambda c:(C[i][c],c));unused.remove(j);greedy.append(j)
    greedy_cost=sum(C[i][j] for i,j in enumerate(greedy))
    assert result['cost']==min(r['cost'] for r in all_perm)==4 and result['columns_by_row']==[1,0,2]
    assert greedy==[0,1,2] and greedy_cost==102
    tied=solve([[1,1],[1,1]]);assert tied['cost']==2 and len(set(tied['columns_by_row']))==2
    invalid=[]
    for Cbad in [[],[[1,2]],[[1,-1],[2,3]],[[True]]]:
        try:solve(Cbad)
        except ValueError:invalid.append(True)
        else:raise AssertionError('invalid input accepted')
    return {'authored_cost_matrix':C,'subset_dp':result,'independent_all_six_permutations':all_perm,'row_greedy':{'columns':greedy,'cost':greedy_cost},'tie_case':tied,'four_invalid_inputs_rejected':invalid,'scipy_hungarian_or_production_assignment_executed':False}

if __name__=='__main__':print(json.dumps(demo(),indent=2))