Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Hugu

Procuro algoritmo para resolver puzzle 4x4

Mensagens Recomendadas

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.