from makeprogress import settle

def SOLVE(rowclues, columnclues):
    m,n = len(rowclues), len(columnclues)
    nonogram = [['?']*n for i in range(m)]
    rows_to_be_checked = set(range(m))
    columns_to_be_checked = set(range(n))
    num_iterations = 0
    while rows_to_be_checked or columns_to_be_checked:
        num_iterations +=1
        if rows_to_be_checked:
            i = rows_to_be_checked.pop()
            Psi = '0' + ''.join(nonogram[i]) + '0'
            # progress_descriptor, padded with artificial zeros
            Psi2 = settle(Psi, rowclues[i], face_pattern=list(range(n+2)))
            # face_pattern is a default face pattern where all entries are distinct
            for j,(c1,c2) in enumerate(zip(Psi[1:-1],Psi2[1:-1])):
                if c1!=c2:
                    nonogram[i][j]=c2
                    columns_to_be_checked.add(j)
        else:
            j = columns_to_be_checked.pop()
            Psi = '0'+ ''.join(nonogram[i][j] for i in range(m)) + '0'
            Psi2 = settle(Psi, columnclues[j], face_pattern=list(range(m+2)))
            for i,(c1,c2) in enumerate(zip(Psi[1:-1],Psi2[1:-1])):
                if c1!=c2:
                    nonogram[i][j]=c2
                    rows_to_be_checked.add(i)
    return nonogram, num_iterations

rowclues = [[4,1],[2,2],[2,1,1],[1,2,1],[1,1,1],[1,1,1],[2,2],[1,4]]
columnclues = [[4,1],[2,1],[2,3],[1,1,1],[1,1,1],[4,2],[1,1],[1,4]]

nonogram, num_iterations = SOLVE(rowclues,columnclues)

for row in nonogram:
    print(''.join({'1':"X", '0':".", '?':"?"}[c] for c in row))
unsettled = sum(1 if c=='?' else 0 for row in nonogram for c in row)
if unsettled>0:
    print(unsettled, "unsettled cells.")
else:
    print(end="Solved in ")
print(num_iterations, "iterations.")