Como Computadores Resolvem Sudoku

Um computador pode resolver um Sudoku 9×9 muito rapidamente, mas não existe um único “algoritmo de Sudoku”. Solvers diferentes são construídos para tarefas diferentes.

Um solver completo tenta determinar se um puzzle possui zero, uma ou várias soluções.

Um solver human-style tenta explicar o puzzle por técnicas lógicas reconhecíveis e em uma ordem útil para uma pessoa.

Geradores, validadores e sistemas de difficulty rating podem precisar dos dois.

Sudoku como problema de constraints

Cada célula pode ser vista como uma variável cujo domínio contém os dígitos ainda possíveis.

As constraints clássicas exigem:

• um dígito por célula;
• cada dígito uma vez por linha;
• uma vez por coluna;
• uma vez por bloco.

Quando um valor é fixado, candidatos incompatíveis são removidos de outras posições. Essa propagação de constraints corresponde, em termos computacionais, à atualização de candidatos que uma pessoa faz depois de uma colocação.

Propagação de candidatos

Um solver simples pode repetir:

1. calcular candidatos legais;
2. colocar valores forçados;
3. eliminar candidatos impossíveis após cada colocação;
4. repetir enquanto houver progresso.

Esse processo resolve puzzles fáceis e também reduz muito o espaço de busca dos difíceis.

Mas ele não garante resolver qualquer Sudoku válido. Um solver completo precisa de uma forma de explorar alternativas quando a propagação deixa de produzir progresso.

Backtracking

Backtracking é uma das abordagens completas mais simples.

1. escolha uma célula não resolvida;
2. tente um candidato legal;
3. propague as constraints;
4. se surgir uma contradição, desfazer a escolha;
5. tentar outro candidato;
6. continuar até completar a grade ou esgotar as alternativas.

Implementações eficientes normalmente escolhem primeiro uma célula com poucos candidatos para reduzir o branching.

Backtracking não é o mesmo que a forma como uma pessoa é ensinada a resolver. É uma estratégia de busca para garantir completude.

Contagem de soluções

Para validar unicidade, um solver não deve simplesmente parar ao encontrar a primeira solução.

Ele precisa continuar o suficiente para distinguir:

• nenhuma solução;
• exatamente uma solução;
• pelo menos duas soluções.

Encontrar uma segunda solução já é suficiente para provar que o puzzle não é único.

Essa separação entre resolver e contar soluções é essencial para geradores e validadores.

Sudoku como exact cover

Sudoku clássico 9×9 pode ser formulado como um problema de exact cover.

Cada possível atribuição (linha, coluna, dígito) é uma linha candidata.

Existem:

9 × 9 × 9 = 729

atribuições candidatas antes de considerar as pistas.

Cada atribuição cobre quatro tipos de constraint:

1. a célula precisa receber um valor;
2. o dígito precisa aparecer na linha;
3. o dígito precisa aparecer na coluna;
4. o dígito precisa aparecer no bloco.

Há 81 constraints de cada tipo, totalizando:

81 × 4 = 324 constraints

Algorithm X

Algorithm X, de Donald Knuth, resolve problemas de exact cover escolhendo uma constraint ainda não satisfeita, experimentando linhas candidatas que a cobrem e removendo temporariamente opções incompatíveis.

O processo faz busca sistemática e backtracking sobre a representação de exact cover.

Para Sudoku, uma solução corresponde a escolher exatamente 81 atribuições (r,c,d) que cubram cada uma das 324 constraints uma única vez.

Dancing Links (DLX)

Dancing Links, normalmente abreviado como DLX, é uma técnica de implementação eficiente para as operações de remoção e restauração usadas por Algorithm X.

Algorithm X é o algoritmo de busca.

DLX é uma estrutura/implementação que torna as operações de cover/uncover muito rápidas.

Eles são frequentemente citados juntos, mas não são exatamente a mesma coisa.

Programação por constraints e modelos do tipo SAT

Sudoku também pode ser expresso em sistemas mais gerais:

• Constraint Programming;
• SAT;
• SMT;
• Integer Programming;
• outras técnicas de satisfação de constraints.

Essas formulações não são necessárias para um Sudoku 9×9 comum, mas mostram que o puzzle pertence a uma classe ampla de problemas combinatórios.

Para versões generalizadas de Sudoku, o problema de decisão é NP-completo. Isso não significa que um puzzle clássico 9×9 individual seja “impossível” para computadores; o tamanho 9×9 é fixo e pequeno para solvers modernos.

Solvers de estilo humano

Um solver human-style não busca apenas qualquer solução.

Ele mantém candidatos e aplica técnicas como:

• Singles;
• Candidatos Bloqueados;
• Pares/Trincas/Quadras;
• Fish;
• Wings;
• Cadeias;
• e outras técnicas configuradas.

Além de resolver, ele registra qual técnica produziu cada dedução.

Isso é útil para hints, explicações, geração pedagógica e difficulty rating.

Por que solvers completos e human-style devem ser separados

As duas tarefas respondem a perguntas diferentes.

Um solver completo pergunta:

Quantas soluções matemáticas existem?

Um solver human-style pergunta:

Que sequência de técnicas explicáveis consegue resolver este puzzle?

Um puzzle pode ter exatamente uma solução e ainda assim não ser resolvido por um human-style solver limitado a técnicas básicas.

Separar os papéis evita confundir validade matemática com experiência de resolução.

Como um gerador usa solvers

Um gerador pode combinar:

1. um solver completo para verificar unicidade após remover pistas;
2. um solver human-style para medir dificuldade e rota lógica;
3. regras editoriais para simetria, estilo e qualidade;
4. repetição até atingir o objetivo desejado.

O solver não “desenha” automaticamente uma boa experiência. Ele verifica propriedades dentro de um processo de geração mais amplo.

Computadores adivinham?

Depende do solver.

Um algoritmo de busca pode explorar alternativas por backtracking. Isso é totalmente válido quando o objetivo é obter completude ou contar soluções.

Um solver human-style pode ser configurado para evitar busca e retornar somente deduções explicáveis.

Por isso dizer “o computador adivinha” é impreciso. A pergunta correta é qual modelo de resolução está sendo usado.

FAQ

Qual é o algoritmo mais rápido para Sudoku?

Não existe uma resposta universal. Backtracking otimizado, exact cover/DLX, SAT e outros métodos resolvem 9×9 muito rapidamente. A melhor escolha depende de velocidade, contagem de soluções, explicabilidade e integração.

Quais são as 324 constraints de exact cover?

81 de célula, 81 de linha-dígito, 81 de coluna-dígito e 81 de bloco-dígito.

Por que existem 729 linhas candidatas?

Porque existem 9 linhas × 9 colunas × 9 dígitos possíveis para uma atribuição (r,c,d).

Algorithm X é a mesma coisa que Dancing Links?

Não. Algorithm X é o algoritmo de exact cover; DLX é uma implementação eficiente das operações que ele usa.

Solvers humanos usam backtracking?

Um solver projetado para imitar resolução lógica normalmente não. Um solver completo pode usar backtracking internamente para verificar soluções.

O que aprender depois

Continue com Como os Sudokus São Gerados, Sudoku e Matemática e Como Criar um Sudoku para conectar esses algoritmos à construção e à dificuldade.