Jump to content
Greemax

Algoritmo para resolver numberlink

Recommended Posts

Greemax

Boas pessoal,

O meu trabalho de final de semestre é um programa que resolva puzzles do numberlink/flow. Gostaria de saber se alguém sabe algum algoritmo que possa usar para resolver os puzzles. Eu ja tentei calcular os caminhos mais proximos entre os pontos, e se isto nao resolvesse, permutava a ordem que os calcucala até ter uma solução, ou solução nenhuma se não fosse um puzzle possivel.

O algoritmo que implementei resolve uma grande parte de puzzles, mas alguns da como se nao tivessem solução e outros da erro.

Cumps

Share this post


Link to post
Share on other sites
Rui Carlos

Já pesquisaste se existe algum algoritmo eficiente para resolver o problema?

Se não existir, a solução passará por testares todas as alternativas possíveis, possivelmente usando um sistema de backtracking. Ou seja, começas com um número a traçar uma linha, preenchendo uma posição de cada vez, tentando chegar ao destino. Depois passas para outro número/linha, até que chegues a um ponto em que é impossível resolver o problema. E quando isso acontecer, voltas um movimento atrás, e tentas outra alternativa. Se já não te restam alternativas para aquele movimento, voltas atrás mais um movimento.

Um algoritmo recursivo deverá ser a forma mais simples de resolveres o problema.

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

×
×
  • 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.