Sudoku FlowComo os computadores resolvem Sudoku
Atualizado em 2026-10-05
Backtracking
O resolvedor experimenta um algarismo válido numa célula vazia e continua. Se nenhum algarismo levar a uma solução, desfaz uma escolha anterior e experimenta outra. Escolher primeiro a célula com menos algarismos possíveis torna muitas vezes a pesquisa muito mais curta.
Fontes: Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle
Cobertura exata e Dancing Links
O Sudoku pode ser reformulado como um problema de cobertura exata: escolher colocações de modo que cada célula, e cada algarismo em cada linha, coluna e bloco, fique coberto exatamente uma vez. Num artigo de novembro de 2000, Donald Knuth descreveu os Dancing Links, uma forma eficiente de executar o seu Algoritmo X de backtracking; aplicado ao modelo de cobertura exata do Sudoku, este método encontra rapidamente todas as soluções de um puzzle.
Fontes: Wikipedia: Sudoku solving algorithms, Knuth, Dancing links (arXiv cs/0011047, 2000)
Pesquisa aleatória
Alguns programas preenchem a grelha ao acaso e depois baralham números para reduzir o número de conflitos, com métodos como o recozimento simulado ou os algoritmos genéticos. Foram estudados como abordagens alternativas; o seu desempenho depende do programa e do puzzle.
Fontes: Wikipedia: Sudoku solving algorithms
Resolvedores que pensam como pessoas
Um motor de dicas tem uma tarefa diferente: não apenas encontrar a resposta, mas mostrar o passo seguinte que uma pessoa consegue acompanhar. O motor da nossa app experimenta técnicas humanas por uma ordem fixa, da mais fácil, como o single oculto, à mais difícil, como as cadeias e os conjuntos quase bloqueados, e usa a primeira que leva à colocação de um algarismo; as mais difíceis funcionam eliminando primeiro candidatos. A técnica mais difícil que utiliza num puzzle define o nível desse puzzle na app.
Fontes: O que cada nível de dificuldade do Sudoku te pede
