Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Resolvendo o sudoku usando backtracking

+1 voto
63 visitas
perguntada Jun 6, 2017 em Programação Computacional por Marcelo A. Costa (6 pontos)  
editado Jun 20, 2017 por Marcelo A. Costa
Compartilhe
comentou Jun 12, 2017 por danielcajueiro (5,196 pontos)  
Ola Marcelo! Vc colocou a pergunta e resposta juntas. Entao fica parecendo que sua pergunta ficou sem resposta. Vc pode editar a pergunta e colocar a resposta no local correto. Abraco

1 Resposta

0 votos
respondida Jun 20, 2017 por Marcelo A. Costa (6 pontos)  

# Define-se o estado inicial das 81
#posições do problema.
tabuleiro = [[4, 8, 5, 0, 0, 0, 0, 3, 9],
[0, 0, 0, 0, 3, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 5],
[8, 0, 0, 6, 1, 0, 0, 0, 0],
[6, 0, 9, 8, 0, 4, 2, 0, 7],
[0, 0, 0, 0, 9, 7, 0, 0, 8],
[9, 0, 0, 0, 0, 0, 0, 5, 0],
[0, 0, 0, 0, 8, 0, 0, 0, 0],
[5, 2, 0, 0, 0, 0, 6, 4, 3]]

#Função usada para imprimir, de forma mais organizada o valor inicial 
# e o resultado final do problema em questão.

def imprimeTabuleiro():
    for r in range(0,9):
        print(tabuleiro[r][0],tabuleiro[r][1],tabuleiro[r][2], "|",
              tabuleiro[r][3], tabuleiro[r][4], tabuleiro[r][5], "|",
              tabuleiro[r][6], tabuleiro[r][7], tabuleiro[r][8],
              sep=" ")
        if (r+1)%3 == 0:
            print("-----------------------")


def resolveSudoku(tabuleiro, i=0, j=0):
    i, j = procuraProximaPosicaoEmBranco(tabuleiro, i, j)
    if i == -1:
        return True
    for e in range(1, 10):
        #Verifica as restrições do problemas
        if verificaSeValorEValido(tabuleiro, i, j, e):
            tabuleiro[i][j] = e
            if resolveSudoku(tabuleiro, i, j):
                return True
            # A linha abaixo desfaz a ação (backtracking)
            # Serve para voltar o tabuleiro ao estado anterior
            # Quando encontramos algum "caminho" inválido
            tabuleiro[i][j] = 0
    return False

#Busca o próximo espaço não preenchido
def procuraProximaPosicaoEmBranco(grid, i, j):
    #Procura na linha atual
    for x in range(i, 9):
        for y in range(j, 9):
            if grid[x][y] == 0:
                return x, y

    #Procura nas linhas subsequentes.
    for x in range(0, 9):
        for y in range(0, 9):
            if grid[x][y] == 0:
                return x, y
    return -1, -1

#Verifica cada uma das restrições do problema
def verificaSeValorEValido(grid, i, j, e):
    #verifica se existe repetição de valores na linhas
    if verificaLinha(grid, i, e):
        #verifica se existe repetição de valores na coluna
        if verificaColuna(grid, j, e):
            #Verifica se existe valores repetidos no box.
            if verificaBox(grid, i, j, e):
                return True
        return False
    return False


def verificaLinha(grid, i, e):
    linhaOk = all([e != grid[i][x] for x in range(9)])
    return linhaOk


def verificaColuna(grid, j, e):
    colunaOk = all([e != grid[x][j] for x in range(9)])
    return colunaOk


# Verifica se já existe o valor no Box atual
# Usamos o módulo para definir o canto superior equerdo do Box
# Em seguinda, verificamos se o valor sugerido para o espaço em
# branco pode ser utilizado dentro daquele box.
def verificaBox(grid, i, j, e):
    boxTopX = 3 * (i // 3) # // retorna apenas a parte inteira da divisão
    boxTopY = 3 * (j // 3)
    for x in range(boxTopX, boxTopX + 3):
        for y in range(boxTopY, boxTopY + 3):
            if grid[x][y] == e:
                return False
    return True

print("Estado Inicial:")
imprimeTabuleiro()
resolveSudoku(tabuleiro)
print("Problema Resolvido:")
imprimeTabuleiro()
comentou Jul 6, 2017 por IgorNascimento (51 pontos)  
Excelente solução utilizando força bruta e backtracking. Funcionou perfeitamente. Um aprimoramento possível é retirar, após usar a procuraProximaPosicaoEmBranco, os valores "e" inválidos da linha, coluna e box.
...