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

Resolvendo o sudoku usando backtracking

+1 voto
40 visitas
perguntada Jun 6 em Programação Computacional por Marcelo A. Costa (6 pontos)  
editado Jun 20 por Marcelo A. Costa
Compartilhe
comentou Jun 12 por danielcajueiro (5,016 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 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 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.
...