Algoritmo de sudoku
O algoritmo de sudoku consiste em verificar através de lógica matemática, as possibilidades para resolver o problema apresentado.
Existem diversos algoritmos e regras para cada implementação, sendo bastante utilizados para técnicas de aperfeiçoamento da lógica, em cursos e faculdades ligadas a área de exatas.
Basicamente, é necessário observar que a regra do jogo só permite números distintos de 1 até 9 em zonas e linhas (ambas composta por nove casas), o jogo contém uma tabela com nove linhas e nove colunas.[1]
Técnicas
Matemática
O problema geral de solucionar enigmas Sudoku em tabuleiros de blocos é conhecido como NP-completo.[2] Isto dá algumas indicações de porque o Sudoku é difícil de resolver. Contudo, em tabuleiros de tamanhos finitos o problema é finito e pode ser solucionado através de um autômato finito probabilístico que conhece toda a árvore do jogo. Solucionar enigmas Sudoku (assim como qualquer outro problema NP-difícil) pode ser expresso como um problema de preenchimento gráfico de cores. O objetivo do enigma em sua forma padrão é construir gráfico apropriado de nove colorações, informando parcialmente as nove colorações. O gráfico em questão tem 81 vértices, uma interpolação em cada célula da grade. Os vértices podem ser rotulados com os pares ordenados , onde x e y são números inteiros entre 1 e 9. Neste caso, dois vértices distintos rotulados por e são conectados por uma borda se e apenas se .
O enigma é então completado designando-se um número inteiro entre 1 e 9 para cada interpolação, de tal maneira que os vértices que são unidos através de uma borda não tenham nenhum número inteiro igual designado neles. Uma grade de solução válida para o Sudoku é também um quadrado latino. Há significativamente menos soluções de grades de Sudoku válidas do que os quadrados latinos, porque o Sudoku impõe restrições de região adicionais. Apesar disso, o número de solução de Sudoku para uma grade padrão de 9×9 foram calculados em 2005 por Bertram Felgenhauer como sendo 6.670.903.752.021.072.936.960.[3] Este número é igual a , o último fator o qual é um número primo. O resultado é derivado através da lógica e computação força bruta. A derivação deste resultado foi simplificada consideravelmente por análises fornecidas por Frazer Jarvis e o número foi confirmado independentemente por Ed Russell. Russel e Jarvis também demonstraram de que quando as simetrias são levadas em conta, havia 5.472.730.538 soluções.[4] O número de soluções válidas para a variação do Sudoku de uma grade 16×16 é desconhecido.
Tentativa e erro
Essa técnica, consistem em criar uma classe de verificação de inconsistências, chamando-a, a cada número preenchido, se estiver incorreto, reinicia-se com um número diferente, até se obter o número perfeito, técnica bastante trabalhosa, já que para o correto preenchimento, é necessário cerca de um trilhão de tentativas. Por exemplo,
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9f/Sudoku_grid_pairing.png/180px-Sudoku_grid_pairing.png)
Resolução de um sudoku em branco
Embora a resolução de tabelas de sudoku parcialmente preenchidas possa ser bastante difícil, as tabelas em branco podem ser resolvidas rapidamente. Talvez a forma mais fácil de fazer isto seja produzir a solução raiz, que pode ser obtida por meio de um algoritmo bem simples, cujo tempo de execução é polinomial:[5]
Para uma grade padrão de tamanho n² x n² o algoritmo tem a seguinte forma (em java):
final int n = 3; final int[][] field = new int[n*n][n*n]; for (int i = 0; i < n*n; i++) for (int j = 0; j < n*n; j++) field[i][j] = (i*n + i/n + j) % (n*n) + 1;
O procedimento acima produz o seguinte sudoku 9x9:
+-----------------------+
| 1 2 3 | 4 5 6 | 7 8 9 |
| 4 5 6 | 7 8 9 | 1 2 3 |
| 7 8 9 | 1 2 3 | 4 5 6 |
|-------+-------+-------|
| 2 3 4 | 5 6 7 | 8 9 1 |
| 5 6 7 | 8 9 1 | 2 3 4 |
| 8 9 1 | 2 3 4 | 5 6 7 |
|-------+-------+-------|
| 3 4 5 | 6 7 8 | 9 1 2 |
| 6 7 8 | 9 1 2 | 3 4 5 |
| 9 1 2 | 3 4 5 | 6 7 8 |
+-----------------------+
Referências
- ↑ http://diuf.unifr.ch/people/juillera/Sudoku/Sudoku.html Sudoku explorado por Nicolas Juillerat (Conhecido poplarmente por jogos de lógica em geral)
- ↑ «Cópia arquivada» (PDF). Consultado em 9 de fevereiro de 2010. Arquivado do original (PDF) em 16 de julho de 2006
- ↑ http://www.afjarvis.staff.shef.ac.uk/sudoku/
- ↑ http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html
- ↑ Lewis, R (2007) Metaheuristics Can Solve Sudoku Puzzles Journal of Heuristics, vol. 13 (4), pp 387-401.
Ligações externas
- Sudoku - Rosetta Code - implementações em diversas linguagens de programação
- http://www.research.att.com/~gsf/man/man1/sudoku.html sudoku by gsf (em inglês)
- AMS.org (em inglês)
- Download de um assitente para Excel.(em inglês)
- Resolvendo com PL/pgSQL, da Microshell (em inglês)
- Sudoku,Wordoku