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.

Técnicas

Matemática

O problema geral de solucionar enigmas Sudoku em tabuleiros $n^{2}\times n^{2}$ de blocos $n\times n$ é 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 $(x,\,y)$, onde x e y são números inteiros entre 1 e 9. Neste caso, dois vértices distintos rotulados por $(x,\,y)$ e $(x',\,y')$ são conectados por uma borda se e apenas se $x=x'\ \lor y=y'\,\lor (\lceil x/3\rceil =\lceil x'/3\rceil \land \lceil y/3\rceil =\lceil y'/3\rceil )$.

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. Este número é igual a $9!\times 72^{2}\times 2^{7}\times 27.704.267.971$, 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. 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,

$81!=1\times 2\times 3\times 4\times ...81=1,20893E+24$

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:

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 (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