# 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()