[desafio] embaralhar slide puzzle

por **saim** 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.

por **PedroX** 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!

por **saim** 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!

por Conteúdo patrocinado

[desafio] embaralhar slide puzzle

[desafio] embaralhar slide puzzle

Re: [desafio] embaralhar slide puzzle

Re: [desafio] embaralhar slide puzzle

Re: [desafio] embaralhar slide puzzle