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

  1. Procure a primeira casa vazia, a partir do canto superior esquerdo.
  2. 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.
  3. Se algum número servir, coloque-o e vá para a próxima casa vazia.
  4. Se chegar a uma casa em que nenhum número serve, volte à casa anterior e teste o próximo número.
  5. 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.

  1. Guarde, para cada casa vazia, os números que podem entrar (os candidatos).
  2. Procure uma técnica aplicável, começando pelas mais fáceis.
  3. 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.