Resolvendo Sudoku - Parte 3

Fechando a série, vamos ver como usar o Algorítimo X com Dancing Links (DLX) para resolver Sudokus,

Dancing Links - Diagrama extraído do artigo de Donald Knuth

O primeiro passo é ver como considerar um Sudoku um problema de Cobertura Exata. Começamos examinando o conjunto de opções: cada uma das 9x9 posições do diagrama pode ter um dos dígitos de 1 a 9. Isto fornece as 9x9x9 = 729 linhas da nossa tabela.

Quais são as restrições e quais as colunas correspondentes? São as seguintes (atenção para não confundir linhas e colunas do diagrama do Sudoku com as linhas e colunas da tabela que será utilizada pelo algorítimo):

• Cada posição do diagrama pode conter um único dígito. É óbvio, mas essencial. Isto corresponde a 81 colunas (uma cada para posição do diagrama), indicando que é necessário escolher um dos nove dígitos para cada posição.
• Cada número só pode aparecer uma vez em cada linha do diagrama. São mais 81 colunas na tabela, cada coluna corresponde a uma combinação dígito x linha, indicando que que é necessário escolher uma das 9 colunas do diagrama onde aparecerá esta combinação.
• Cada número só pode aparecer uma vez em cada coluna do diagrama. São mais 81 colunas na tabela, cada coluna corresponde a uma combinação dígito x coluna, indicando que que é necessário escolher uma das 9 linhas do diagrama onde aparecerá esta combinação.
• Cada número só pode aparecer uma vez em cada bloco (sub-diagrama 3x3). São mais 81 colunas na tabela, cada coluna corresponde a uma combinação dígito x bloco, indicando que que é necessário escolher uma das 9 posições do bloco onde aparecerá esta combinação.

Ufa, é um total de 4 x 81 = 324 colunas. Repare, porém, que a maior parte da tabela de 729 x 324 estará vazia, pois cada coluna possui apenas 9 células. Ótimo para a nossa representação esparsa.

Agora é só seguir o algorítimo descrito no artigo do Knuth para construir o programa. A Wikipedia indica uma implementação do DLX, que você pode ver em https://github.com/blynn/dlx. Esta implementação é razoavelmente genérica, podendo ser usada tanto com Sudoku como com problemas de lógica que aparecem em revistas (exemplos aqui). Entretanto, esta implementação usa macros e alguns recursos da versões mais modernas de C que acabam escondendo um pouco o funcionamento,

A minha implementação (que você também pode ver no github) é específica para Sudoku mas (espero) um pouco mais legível.

Compensou a complexidade adicional? No meu micro de teste, o problema difícil, que demorava quase um minuto com a força bruta, foi resolvido instantaneamente.