Algoritmo de sudoku

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de Algoritmo de Sudoku)
Ir para: navegação, pesquisa

O algoritmo de sudoku consiste em verificar através de lógica matemática, as possibilidade 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[editar | editar código-fonte]

Matemática[editar | editar código-fonte]

O problema geral de solucionar enigmas Sudoku em tabuleiros n^2 \times n^2 de blocos n \times n é 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 (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.[3] 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.[4] O número de soluções válidas para a variação do Sudoku de uma grade 16×16 é desconhecido.

Tentativa e erro[editar | editar código-fonte]

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


Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido de en:Sudoku algorithms. Ajude e colabore com a tradução.
Exemplo de sudoku ilustrando as posiveis combinações (em azul claro).

Resolução de um sudoku em branco[editar | editar código-fonte]

Embora a resolução de tabelas de sudoku parcialmente preenchidas frequentemente possa ser bastante difícil de resolver, 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 do seguinte 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

  1. http://diuf.unifr.ch/people/juillera/Sudoku/Sudoku.html Sudoku explorado por Nicolas Juillerat (Conhecido poplarmente por jogos de lógica em geral)
  2. http://www.phil.uu.nl/~oostrom/cki20/02-03/japansepuzzles/ASP.pdf
  3. http://www.afjarvis.staff.shef.ac.uk/sudoku/
  4. http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html
  5. Lewis, R (2007) Metaheuristics Can Solve Sudoku Puzzles Journal of Heuristics, vol. 13 (4), pp 387-401.

Ligações externas[editar | editar código-fonte]