Também dá para deixar o computador resolver sudoku. O jeito mais simples é testar números nas casas vazias e, quando travar, voltar um passo e tentar de novo. Esse método se chama backtracking (busca com retrocesso).
A ideia do backtracking
- Procure a primeira casa vazia, a partir do canto superior esquerdo.
- Teste nela os números de 1 a 9, em ordem. Se o número já existir na mesma linha, coluna ou bloco, pule-o.
- Se algum número servir, coloque-o e vá para a próxima casa vazia.
- Se chegar a uma casa em que nenhum número serve, volte à casa anterior e teste o próximo número.
- Quando não houver mais casas vazias, o sudoku está pronto.
Uma pessoa evita chutar, mas o computador pode voltar atrás na hora em que erra. Por isso, mesmo testando tudo às cegas, ele chega rápido à resposta.
Como fica em Python
O tabuleiro é uma lista de 81 números, da esquerda para a direita e de cima para baixo (0 é casa vazia). Na casa de índice i, o quociente de i ÷ 9 é a linha e o resto é a coluna.
def can_place(grid, r, c, d):
# Pode colocar se d não existe na mesma linha, coluna ou bloco
for k in range(9):
if grid[r * 9 + k] == d or grid[k * 9 + c] == d:
return False
br, bc = r // 3 * 3, c // 3 * 3
for rr in range(br, br + 3):
for cc in range(bc, bc + 3):
if grid[rr * 9 + cc] == d:
return False
return True
def solve(grid):
# Acha uma casa vazia e testa de 1 a 9. Se travar, volta atrás
for i in range(81):
if grid[i] == 0:
r, c = divmod(i, 9)
for d in range(1, 10):
if can_place(grid, r, c, d):
grid[i] = d
if solve(grid):
return True
grid[i] = 0
return False
return True
puzzle = "3..5..182.....2.9.8.2.91.4...52.9..6724.1.8396..4.85...5.12.9.7.3.7.....267..4..8"
grid = [0 if ch == "." else int(ch) for ch in puzzle]
solve(grid)
for r in range(9):
print(" ".join(str(v) for v in grid[r * 9 : r * 9 + 9])) Ao rodar, a resposta aparece assim. O problema é um ★1 do app NumberPlace.
3 4 9 5 6 7 1 8 2
5 1 6 8 4 2 7 9 3
8 7 2 3 9 1 6 4 5
1 8 5 2 3 9 4 7 6
7 2 4 6 1 5 8 3 9
6 9 3 4 7 8 5 2 1
4 5 8 1 2 3 9 6 7
9 3 1 7 8 6 2 5 4
2 6 7 9 5 4 3 1 8 Contando quantas soluções existem
Ao criar um problema, é bom conferir se ele tem uma única resposta (Por que a resposta é única). Se você mudar um pouco o programa acima para não parar ao achar uma resposta e continuar contando, ele diz quantas soluções existem. Quando acha duas, já se sabe que não é única, e a busca para aí.
def count_solutions(grid, limit=2):
# Para ao achar limit soluções (com 2 já se sabe que não é única)
for i in range(81):
if grid[i] == 0:
r, c = divmod(i, 9)
found = 0
for d in range(1, 10):
if can_place(grid, r, c, d):
grid[i] = d
found += count_solutions(grid, limit - found)
grid[i] = 0
if found >= limit:
break
return found
return 1
grid = [0 if ch == "." else int(ch) for ch in puzzle]
print(count_solutions(grid)) No problema ★1 acima, o resultado é 1. Num problema com duas respostas, é 2.
Como deixar mais rápido
Em vez de testar da esquerda para a direita, comece pela casa que aceita menos números. Isso acelera muito, porque, preenchendo primeiro as casas com um único candidato, quase não há retrocesso. O NumberPlace também usa essa ordem quando confere o número de soluções de um problema.
Resolver com as mesmas técnicas de uma pessoa
O backtracking é rápido e seguro, mas não explica “por que esse número entra aqui”. Para a Dica e para medir a dificuldade dos problemas, o NumberPlace usa outro método.
- Guarde, para cada casa vazia, os números que podem entrar (os candidatos).
- Procure uma técnica aplicável, começando pelas mais fáceis.
- Depois de avançar uma jogada, volte a procurar a partir da técnica mais fácil.
As técnicas são 15, em ordem de dificuldade: de “só cabe aqui” e “só cabe este número” até candidatos bloqueados, pares, X-Wing, XY-Wing e Swordfish (Como resolver sudoku). Como segue a mesma ordem de uma pessoa, dá para saber qual técnica foi necessária. Com isso, o app define as estrelas e mostra o motivo na Dica.
