Puzzles

Sempre gostei de resolver sudokus como passatempo. Ultimamente tenho experimentado alguns puzzles diferentes no site puzzle picnic. Neste site tem muitos tipos de puzzles e alguns deles lembram muito problemas de teoria da computação, como o Hamilton Maze, que consiste em determinar um ciclo hamiltoniano e o Shadows que lembra algum tipo de problema de cobertura.

Lembro de algum professor falando sobre problemas NP-difíceis, em como o computador pode levar anos para resolver este tipo de problema, enquanto seres humanos têm capacidade de encontrar a solução muito mais facilmente. A maioria, se não a totalidade, é NP-difícil, inclusive o sudoku [1][2].

Implementação

Sudoku

Implementar um resolvedor de sudoku é bem simples, pois o problema pode ser escrito facilmente com linguagem matemática na forma de restrições. Já implementei diversas vezes um resolvedor de sudokus durante a maratona. Basicamente é um algoritmo de força-bruta: para cada célula chutamos um valor de 1 a 9 que não viole as restrições de linhas, colunas nem sub-quadrados (3×3). Para cada valor chutado, recursamos nas células restantes. Para cada valor chutado, modificamos as restrições para as células seguintes. Por exemplo, se chutarmos o valor 3 na célula (1,2), sabemos que não haverá o valor 3 em qualquer célula da linha 1, ou da coluna 2 ou do mesmo sub-quadrado que (1,2).

O modo mais eficiente que consegui encontrar foi, para cada nível da recursão, escolher a célula com menos possibilidades de valores a serem chutados. Essa é uma heurística comum em algoritmos de força-bruta pois desta forma diminuímos o tamanho da árvore de busca. Desta forma consigo resolver sudokus 9×9 muito rapidamente (16×16 já não fica tão eficiente).

Nonograma

Nonograma (picross) preenchido

Neste jogo temos que preencher algumas células. Em cada linha (coluna) há alguns números. Cada número deste indica que deve haver um bloco deste tamanho de células contínuas em cada linha (coluna) preenchidas. Blocos são separados por pelo menos um espaço em branco.

Fui implementar um resolvedor para este problema, mas tentei implementar as regras lógicas que eu pensei para resolver este problema como ser humano. Achei extremamente complicado e acabei desistindo :( Também não cheguei a pensar em nenhuma força bruta além da trivial de chutar 0 ou 1 em cada célula para no final verificar se satisfez os valores das linhas (colunas).

Referências:
[1] Tese de Takayuki Yato http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/MasterThesis.pdf
[2] NP-dificuldade de alguns puzzles http://en.wikipedia.org/wiki/List_of_NP-complete_problems#Games_and_puzzles

Os comentários estão fechados.

%d bloggers like this: