Antes de mais nada, se você não sabe o que é, não pense bobagem. Sudoku é uma espécie de palavra cruzada com números, que, pelo nome, só pode ter sido inventada no Japão ou em Pelotas. A realidade optou pela primeira.

O jogo consistem tradicionalmente em um tabuleiro 9x9, difidido em 9 quadros de 3x3. Em cada uma das 91 células ficam números de 1 a 9. O jogo começa já com alguns números preenchidos e o objetivo do mesmo é completar os buracos do tabuleiros com outros números, de tal forma que nenhum número se repita por linha, coluna ou "quadro" (células 3x3).

Esse é um passatempo simples e divertido para pessoas normais, que compram uma revistinha com vários desses puzzles nas bancas. Recomendo. É barato e vai te render horas de divertimento.

Mas um Nerd de verdade não se diverte com isso! Depois de resolver uma meia dúzia, pensei em montar um "resolvedor de sudoku".

Montei no excel mesmo uma planilha que, dado um tabuleiro de SDK, ela simplesmente resolve em O(n^5). Nos casos práticos só vi chegar em tempo de execução de n^4. Pode ser baixada e estudada. Solução simplezinha, mas bonitinha. Com um plus por abstrair a algebra de conjuntos do resto da solução. Ela, com um pouco de trabalho, é escalável para outros tamanhos de tabuleiro (12x12, 16x16, etc.) Por não ser exponencial, acredito que ainda fique rápida para tamanhos razoáveis.

Detalhe: montei a planilha que resolve em fração de segundo um SDK em que eu estava empacado a horas em uma hora. :-)

A moral da história é: resolvedor no sudoku dos outros é refresco. :-)