15-puzzle

15-puzzle

por Cristina Gomes Fernandes -
Número de respostas: 3
Uma ajudinha com o 15-puzzle...

Dê uma lida no site...

http://mathworld.wolfram.com/15Puzzle.html

Tem alguma coisa lá que você pode usar no seu programa.

Até,

Cris
Em resposta à Cristina Gomes Fernandes

Re: 15-puzzle

por Wanderley Guimarães -
Pessoal,

Lá vai algumas dicas para resolver o 15-puzzle:
  1. Defina um estado.
    1. Dá para representar o tabuleiro em um unsigned long long. (Pense!)
    2. Os movimentos necessários também podem ser representados com dois unsigned long long (Pense mais um pouco!)
  2. Memorize os estados.
    1. Como seu estado é um unsigned long long é fácil gerar uma função de hash. <http://www.ime.usp.br/~pf/mac0122-2002/aulas/hashing.html>;
  3. Busca por prioriadade.
    1. Definia uma função de custo para os estados. Use algo do tipo: Nível  + Distância Manhattan <http://en.wikipedia.org/wiki/Taxicab_geometry>;
      1. Dica: Não calcule a distância de manh... do 0 (zero).
    2. Escreva uma fila de prioridade <http://www.ime.usp.br/~pf/mac0122-2002/aulas/heapsort.html>;.
  4. TOME CUIDADO NA HORA DE IMPRIMIR A SAÍDA
Boa sorte!
Em resposta à Wanderley Guimarães

Re: 15-puzzle

por Rafael Schouery -
Fiz tudo isso, mas o problema é falta de memória.
Vc limitou a quantidade de caras no hash?
E quando vai colocar alguem no heap, mas o heap tah cheio, vc joga fora o ultimo elemento?
meu struct é só tres unsigned long long, não vejo de onde mais tirar...