[desafio] embaralhar slide puzzle

Ver o tópico anterior Ver o tópico seguinte Ir em baixo

[desafio] embaralhar slide puzzle

Mensagem por saim em Ter 27 Ago 2013, 14:03

Sabe o que é um slide puzzle, certo?
Então, estou atualizando um slide puzzle meu, aqui. As peças são dispostas numa grid. Existem duas arrays 2D com a posição (em x e em y) de cada peça.

Pra embaralhar, eu pego o espaço em branco e troco ele de lugar com uma peça aleatória, 200 vezes. O resultado é bom, então o problema já está contornado.
Mas, só por curiosidade, existe alguma maneira de fazer isso usando shuffle e garantir a solução do puzzle? É fácil colocar as peças numa ds_list e usar o ds_list_shuffle, mas garantir a solução do problema depois disso, não parece tão fácil.

Se houver uma forma de verificar se a solução existe, posso fazer um "while (solução não existe) { shuffle_de_novo) }", mas como verificar?

Até alterei o título, colocando um "desafio", pra incentivar o pessoal a quebrar a cabeça.

saim

Ranking : Nota B
Número de Mensagens : 2964
Idade : 38
Data de inscrição : 14/01/2011
Notas recebidas : C-D-A-B
Reputação : 121
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   : 1
   : 0
   : 3

Voltar ao Topo Ir em baixo

Re: [desafio] embaralhar slide puzzle

Mensagem por PedroX em Ter 27 Ago 2013, 16:24

Achei o artigo a seguir interessante:

http://www.cs.princeton.edu/courses/archive/fall12/cos226/assignments/8puzzle.html

A seção "Detecting unsolvable puzzles." explica o que você quer saber.




  • Odd board size. Given a board, an inversion is any pair of blocks i and j where i < j but i appears after j when considering the board in row-major order (row 0, followed by row 1, and so forth).

    If the board size N is an odd integer, then each legal move changes the number of inversions by an even number. Thus, if a board has an odd number of inversions, then it cannot lead to the goal board by a sequence of legal moves because the goal board has an even number of inversions (zero).
    The converse is also true: if a board has an even number of inversions, then it can lead to the goal board by a sequence of legal moves.


  • Even board size. If the board size N is an even integer, then the parity of the number of inversions is not invariant. However, the parity of the number of inversions plus the row of the blank square is invariant: each legal move changes this sum by an even number. If this sum is even, then it cannot lead to the goal board by a sequence of legal moves; if this sum is odd, then it can lead to the goal board by a sequence of legal moves.

O trecho está incompleto porque não deu para colar as tabelas numéricas aqui.

Até mais!

PedroX

Ranking : Nota C
Número de Mensagens : 6034
Idade : 21
Data de inscrição : 26/07/2008
Notas recebidas : C+B
Reputação : 286
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   :
   :
   :

Voltar ao Topo Ir em baixo

Re: [desafio] embaralhar slide puzzle

Mensagem por saim em Ter 27 Ago 2013, 21:01

Parece complexo. Vou dar uma lida com calma, mais tarde. Legal saber que TEM jeito, mas parece mais complicado (e demorado) que embaralhar manualmente (puxa, usa o A*!).
Valeu pelo link!

saim

Ranking : Nota B
Número de Mensagens : 2964
Idade : 38
Data de inscrição : 14/01/2011
Notas recebidas : C-D-A-B
Reputação : 121
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   : 1
   : 0
   : 3

Voltar ao Topo Ir em baixo

Re: [desafio] embaralhar slide puzzle

Mensagem por Conteúdo patrocinado Hoje à(s) 16:21


Conteúdo patrocinado


Voltar ao Topo Ir em baixo

Ver o tópico anterior Ver o tópico seguinte Voltar ao Topo

- Tópicos similares

 
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum