sudoku = [ [0, 7, 0, 1, 9, 0, 4, 0, 8],
           [8, 0, 6, 3, 0, 0, 1, 0, 0],
           [0, 4, 5, 0, 8, 2, 3, 0, 6],
           [0, 6, 0, 0, 2, 3, 5, 0, 4],
           [5, 8, 0, 0, 0, 0, 2, 6, 3],
           [4, 3, 0, 6, 1, 5, 0, 8, 9],
           [0, 0, 4, 5, 6, 0, 0, 7, 0],
           [0, 0, 9, 2, 0, 0, 8, 0, 5],
           [7, 0, 8, 0, 3, 0, 6, 4, 0]]

u = set(range(1,10))

num_passadas = 0
preenchi_celula = True
while preenchi_celula:
    num_passadas += 1
    preenchi_celula = False
    for l in range(9):
        for c in range(9):
            if sudoku[l][c] == 0:
                npode = set()

                # percorre a linha
                for j in range(9):
                    if sudoku[l][j] != 0:
                        npode.add(sudoku[l][j])

                # percorre a coluna
                for i in range(9):
                    if sudoku[i][c] != 0:
                        npode.add(sudoku[i][c])

                # percorre a sudoku de 3x3
                kl = l // 3 * 3
                kc = c // 3 * 3
                for i in range(kl, kl+3):
                    for j in range(kc, kc+3):
                        if sudoku[i][j] != 0:
                            npode.add(sudoku[i][j])

                # se só resta um valor, então ele é o candidato
                if len(npode) == 8:
                    dif = u.difference(npode)
                    sudoku[l][c] = dif.pop()
                    preenchi_celula = True
    
for linha in sudoku:
    print(linha)

print(num_passadas)