Sudoku
Quase esqueci de dizer que hoje foi um dia de descobertas. Até hoje nunca tinha ouvido falar sobre Sudoku, você já?
Calma! Sudoku não dói e não é de comer. Não é esporte, muito menos prato japonês. Supostamente é algo que eu deveria ter aprendido nas fases iniciais da faculdade - na verdade, faltou avisar os professores de Sistemas de Informação.
Sudoku, conhecido também por “lugar do número”, é um enigma de lógica baseado na colocação. O alvo do enigma é incorporar dígitos numéricos de 1 a 9 em cada matriz 9×9 composta de submatrizes 3×3 (ver imagem abaixo); cada linha, coluna, e submatriz devem conter somente um exemplo de cada número. Terminar o enigma requer paciência e habilidade lógica.
Segundo consta, o Sudoku foi inventado em Indianapólis em 1979. Este nome é a abreviatura japonesa de uma frase bem longa: “kagiru do ni do dokushin do wa Suuji” que significa “os dígitos devem permanecer únicos”.
Como os relacionamentos aritméticos entre números são irrelevantes, os números em enigmas de Sudoku são usados por conveniência. A atração do enigma é que as regras são simples, contudo a linha do raciocínio requerida para resolver o enigma pode ser complexa.
Eu achei bem interessante. Encontrei um joguinho na internet deste enigma em: “Sudoku, o quebra-cabeça mais popular do mundo“. Vale a pena dar uma olhada, nem que seja só pra entender a idéia.
Bom, e para quê isto serve? Qual a utilidade? Bom, não faço idéia, só sei que não é o tipo de problema que uma pessoa leva uma meia horinha pra formular um algoritmo de solução.
Ops, faltou apontar uma solução. Eu ainda nem cheguei a tentar fazer de verdade, nem a descobrir a melhor solução, mas gostei um pouco deste algoritmo:
1. Criar um array com as coordenadas dos números
Array[sub-grade][linha coluna];
2. Povoar os elementos com o número 123456789.
3. Entrar em um loop recursivo:
3.1. Verificar se existe pelo menos um número, em toda a matriz, composto de mais de um número (78 por exemplo).
Se a resposta é sim, continuo, caso contrario saio do loop.
3.2. Escolher um número presente no menor número em comprimento presente no array.
Exemplo: na célula Array[5][32] (quinta submatriz, terceira linha, segunda coluna) temos o numero
“2589″ e este número possui 4 caracteres. Todos os outros sao maiores ou possuem o mesmo número de
caracteres. Então escolhemos aleatoriamente um deles: “8″ e o colocamos em substituição do “2589″
presente na célula.
3.3. Substituir o número escolhido (8) em todos os outros elementos presentes na quinta
sub-grade.
Para cada elemento do Array[5] diferente de [32] substituir o numero 8 com “” (nada).
3.4. Substituir o número escolhido (8) em todos os outros elementos presentes na
linha.
3.5. Substituir o número escolhido (8) em todos os outros elementos presentes na
coluna.
3.6. Recomeçar o loop.
Enjoy! 
