# 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$

## 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):
O procedimento acima produz o seguinte sudoku 9x9: