Jump to content
Sign in to follow this  
Hugu

Procuro algoritmo para resolver puzzle 4x4

Recommended Posts

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.