Sudoku FlowComo os computadores resolvem Sudoku
Atualizado em 2026-10-05
Backtracking
O solucionador testa um número permitido em uma célula vazia e continua. Se nenhum número levar a uma solução, ele desfaz uma escolha anterior e tenta outra. Escolher primeiro a célula com menos números possíveis costuma tornar a busca 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 posições para os números de modo que cada célula e cada número em cada linha, coluna e bloco sejam cobertos exatamente uma vez. Em um artigo de novembro de 2000, Donald Knuth descreveu Dancing Links, uma forma eficiente de executar seu Algorithm X, que usa backtracking; aplicado ao modelo de cobertura exata do Sudoku, ele encontra rapidamente todas as soluções de um quebra-cabeça.
Fontes: Wikipedia: Sudoku solving algorithms, Knuth, Dancing links (arXiv cs/0011047, 2000)
Busca aleatória
Alguns programas preenchem a grade aleatoriamente e depois rearranjam os números para reduzir a quantidade de conflitos, usando métodos como recozimento simulado ou algoritmos genéticos. Esses métodos foram estudados como abordagens alternativas; seu desempenho depende do programa e do quebra-cabeça.
Fontes: Wikipedia: Sudoku solving algorithms
Solucionadores que pensam como pessoas
Um mecanismo de dicas tem outra função: além de encontrar a resposta, mostrar o próximo passo que uma pessoa consegue seguir. O mecanismo do nosso app testa técnicas humanas em uma ordem fixa, das mais fáceis, como Single oculto, às mais difíceis, como cadeias e conjuntos quase bloqueados, e usa a primeira que leva à inserção de um número; as mais difíceis funcionam eliminando candidatos primeiro. A técnica mais difícil que ele usa em um quebra-cabeça determina o nível desse quebra-cabeça no app.
Fontes: O que cada nível de dificuldade do Sudoku exige de você
