Procuro algoritmo para resolver puzzle 4x4

[Hugu]

Boas,

Queria resolver um puzzle daqueles, cuja a imagem é partida em pequenos quadrados e depois são misturados e o objectivo do jogo é rearranjar a imagem inicial.. n sei se já estão a ver qual é o jogo.

Alguém sabe de algum programa/algoritmo/script, que resolva este tipo de puzzle (4x4)?

Obrigado

[Warrior]

Esse problema é NP, o que significa que puzzles grandes podem possuir soluções exponenciais no tempo (demorar eternidades).

Ainda assim, 16 peças é algo que se resolve facilmente com qualquer linguagem de programação usando uma pesquisa em profundidade. Só tens que gerar todas as permutações, e possivelmente fazer alguns cortes na geração. Investiga um pouco sobre isso que vais ver que é bastante simples.

De modo mais eficiente, só mesmo usando programação com restrições, mas não me parece ser o teu objectivo.

[Hugu]

Esse problema é NP, o que significa que puzzles grandes podem possuir soluções exponenciais no tempo (demorar eternidades).

Ainda assim, 16 peças é algo que se resolve facilmente com qualquer linguagem de programação usando uma pesquisa em profundidade. Só tens que gerar todas as permutações, e possivelmente fazer alguns cortes na geração. Investiga um pouco sobre isso que vais ver que é bastante simples.

De modo mais eficiente, só mesmo usando programação com restrições, mas não me parece ser o teu objectivo.

Acabei por descobrir o SBP Solver, mas este falhou muito em slide puzzles 4x4 .. :S

[lupe]

Para puzzles maiores, em que as pesquisas que varrem todo o universo exigem esforço computacional exponencial, como disse o Warrior, podes sempre recorrer a uma meta-heurística, por exemplo, os algoritmos genéticos.

[Warrior]

Acabei por descobrir o SBP Solver, mas este falhou muito em slide puzzles 4x4 .. :S

Isso porque a  solução não tem 16 movimentos mas mais..

Pesquisa por CLP (constraint logic programming), sempre aprendes algo útil