Resolvendo Sudoku - Parte 1

Esta curta série de posts tem origem em uma pequena piada. Entrando em uma revistaria de um shopping na Holanda, o livro abaixo foi o único que eu consegui ler (ba dum tss):

Piadas ruins à parte, eu gosto de Sudoku e naturalmente veio a questão de como resolver um destes problemas, de forma eficiente, no computador. Fiquei ainda mais interessado depois que vi na Wikipedia que uma das soluções usa uma ideia do grande Donald Knuth.

Para o caso (improvável) de alguém não conhecer este problema, trata-se de completar um diagrama de 9 por 9 posições, obedecendo as seguintes regras:

• Em cada casa deve ser colocado um dígito de 1 a 9
• Não pode ocorrer repetição de dígito na linha
• Não pode ocorrer repetição de dígito na coluna
• Não pode ocorrer repetição de dígito nos blocos (sub diagramas 3x3 em destaque).

Um exemplo de problema, de autoria de Tim Stellmach e extraído da Wikipedia:

Neste primeiro post, vamos ver a solução mais óbvia, a força bruta. Sendo mais técnico, vamos usar backtracking (ou depth-first). Repetidamente escolhemos a próxima opção para a próxima opção não preenchida, até o problema ser resolvido ou encontrarmos um conflito. Se encontramos um conflito, voltamos atrás na escolha anterior (backtrack). A wikipedia tem uma animação bonitinho de como isto funciona.

Nesta primeira experiência eu usei C#. As principais questões a serem resolvidas foram:

• Como controlar quais opções podem ser testadas em cada posição. Controlei isto associando um mapa de bits em cada posição.
• Quais posições já estão preenchidas e com qual dígito. Para isto basta guardar o dígito ou zero (indicando não preenchida) para cada posição.
• Como voltar à posição anterior. Fui radical neste ponto, guardando uma imagem completa do diagrama.

O programa resultante está no meu github. Alguns comentários:

• A classe Sudoku representa o diagrama.
• Cada posição é armazenada em um inteiro de 16 bits, onde 9 bits controlam os dígitos permitidos e 4 bits guardam o dígito atual (ou zero se posição não preenchida).
• O método Mark registra a escrita de um dígito em uma posição, atualizando os mapas de bits de todas as posições na mesma linha, coluna e bloco.
• O método Next procura a próxima posição não preenchida e NextVal  escreve o próximo valor nesta posição.
• O método Solve procura a solução, copiando o diagrama atual, colocando o próximo valor na próxima posição não preenchida e procurando a solução neste novo diagrama.
• O método Load lê um problema de um arquivo texto.

O resultado foi bastante satisfatório. Em micro não muito moderno (um Intel Core2 Duo @ 3GHz de 2008), o exemplo da Wikipedia foi resolvido em menos de um segundo. A Wikipedia tem também um exemplo construído para atrapalhar o backtracking, que teria demorado 6 horas para ser resolvido em um teste em 2008. Demorou menos de um minuto no meu micro de teste.