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.http://diuf.unifr.ch/people/juillera/Sudoku/Sudoku.html Sudoku explorado por Nicolas Juillerat (Conhecido poplarmente por jogos de lógica em geral)
Técnicas Matemática
O problema geral de solucionar enigmas Sudoku em tabuleiros de blocos é conhecido como NP-completo. 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.http://www.afjarvis.staff.shef.ac.uk/sudoku/ 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.http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html 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,
thumb|180px|right|Exemplo de sudoku ilustrando as posiveis combinações (em azul claro).
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:Lewis, R (2007) Metaheuristics Can Solve Sudoku Puzzles Journal of Heuristics, vol. 13 (4), pp 387-401.
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 | +-----------------------+
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 AMS.org Download de um assitente para Excel. Resolvendo com PL/pgSQL, da Microshell Sudoku,Wordoku
Sudoku Algoritmo