# Retorna um conjunto com os possíveis valalores
# para uma célula ainda não resolvida
def valores_possiveis_celula(tabuleiro, lin, col):
    nao_possiveis = set()
    nao_possiveis.update(tabuleiro[lin])
    nao_possiveis.update(tabuleiro[i][col] for i in range(9))
    li = lin // 3 * 3
    ci = col // 3 * 3
    for i in range(li, li+3):
        nao_possiveis.update(tabuleiro[i][ci:ci+3])
        
    todos_possiveis = set(range(1, 10))
    possiveis = todos_possiveis.difference(nao_possiveis)
    
    return possiveis


sudoku_1 = [ [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]]

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

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

sudoku = sudoku_3

# Tenta ver quais células tem um única possibilidade
resolvi_algum_celula = True
repeticoes = 0
while resolvi_algum_celula:
    # percorre cada célula da matriz
    resolvi_algum_celula = False
    repeticoes += 1
    for l in range(9):
        for c in range(9):
            if sudoku[l][c] == 0: # Para células ainda nao preenchidas
                possiveis = valores_possiveis_celula(sudoku, l, c)
                if len(possiveis) == 1: # Só tem uma possibilidade
                    sudoku[l][c] = possiveis.pop()
                    resolvi_algum_celula = True

# Tenta ver quais valores só podem ir num posição
for l in range(9):
    posicoes = dict()
    for j in range(9):
        if sudoku[l][j] == 0:
            for vp in valores_possiveis_celula(sudoku, l, j):
                d = posicoes.get(vp, set())
                d.add(j)
                posicoes[vp] = d
    for vp, pos in posicoes.items():
        if len(pos) == 1: 
            sudoku[l][pos.pop()] = vp

print(repeticoes)
for linha in sudoku:
    print(*linha)