Resolvendo Sudoku - Parte 2

Neste segundo post vamos abordar uma teoria que nos permitirá resolver problemas Sudoku de forma bastante rápida.

Vamos encostar um pouco o Sudoku e falar de um problema mais genérico, a Cobertura Exata (exact cover).A definição precisa pode ser lida na Wikipedia, segue uma descrição mais relaxada, baseada na representação do problema através de uma tabela (ou matriz bidimensional).

Cada linha da tabela corresponde a uma opção e cada coluna a uma restrição, e cada posição da tabela pode conter 0 ou 1:

• Olhando uma linha, os 1s indicam quais restrições se aplicam àquela opção
• Olhando uma coluna, os 1s indicam quais opções atendem aquela restrição

O problema consiste em selecionar um conjunto de opções onde cada restrição seja atendida uma única vez. Ou seja, olhando somente as linhas selecionadas teremos exatamente um 1 em cada coluna.

Confuso? Vamos tentar um exemplo simples. Considere que temos um conjunto de blocos que podem ser redondos, triangulares ou quadrados e ter cor azul, verde ou vermelha:

• redondo azul
• redondo verde
• triangulo azul
• quadrado verde
• quadrado vermelho

Nosso objetivo é escolhermos um conjunto de objetos de tal forma que teremos um só de cada forma e um só de cada cor. A tabela teria o seguinte formato:

                         redondo  quadrado  triangulo  azul  verde  vermelho
    redondo azul            1         0         0        1     0       0
    redondo verde           1         0         0        0     1       0
    triangulo azul          0         0         1        1     0       0
    quadrado verde          0         1         0        0     1       0
    quadrado vermelho       0         1         0        0     0       1

A solução para o problema é pegar os seguintes blocos:

• redondo verde
• triangulo azul
• quadrado vermelho

Donald Knuth chamou de Algorítimo X o algorítimo óbvio de solução da cobertura exata. É parecido com o que implementei no post anterior:

• Selecione a próxima coluna (restrição)
• Vá tentando as linhas que atendam a esta coluna
• remova as linhas que tenham 1 nas mesmas colunas que a linha sendo tentada
• remova as colunas que tenham 1 na linha sendo testada
• repita recursivamente com a matriz reduzida 

A grande sacada de Knuth foi perceber que a ineficiência da implementação típica deste algorítimo está na representação da tabela através de uma matriz dimensional:

• Tipicamente um problema tem poucos 1s e muito espaço é gasto armazenando os 0s
• A procura de linhas e colunas com 1 requer pular estas posições com 0
• O backtraking é feito gerando uma cópia de toda a matriz

Usando listas ligadas para implementar uma matriz esparsa, que armazene só as posições com 1, os dois primeiros pontos são resolvidos. O lance de gênio foi perceber que se a lista for duplamente ligada o backtracking pode ser feito sem armazenamento adicional.

Em uma lista duplamente ligada, cada elemento possui ponteiros tanto para o próximo elemento como para o anterior:

Quando retiramos um elemento da lista (por exemplo o item B no desenho acima), alteramos os ponteiros dos elementos antes e depois dele (A e C no exemplo):

Entretanto, o elemento retirado mantém os ponteiros necessários para reverter a remoção:

Usando esta propriedade da listas duplamente ligadas, que Knuth chamou de "dancing links", o Algorítimo X pode ser implementado de uma forma muito eficiente.

No próximo post veremos o que isto tem a ver com o Sudoku e a minha implementação.