Buscar:
Prototipos DesliZAZ 27-03-2014
DesliZAZ, juego roto.


Es bueno revisar las cosas antes de liberarlas aunque el trabajo sea sencillo. He estado trabajando esta semana en el remake de mi juego del rompecabezas deslizable para poderlo ofrecer en varias plataformas usando GameMaker, y cuando estaba a punto de declarar terminado mi trabajo, me puse a jugar con lo que había hecho y ¡sorpresa! craso error que encuentro en el juego.
Pues resulta que el hacer un rompecabezas deslizable de 4 x 4 no es solo quitar una pieza y revolver todo, se trata ni mas ni menos de un problema matemático que va más allá de mi actual conocimiento pero que de no manejarse con cuidado hace que las cosas no funcionen. Después de romperme la sesera para resolver mi juego y 3760 movimientos después voy cayendo en cuenta de que el algoritmo que estoy usando tiene algo incorrecto, pues no puedo resolver el último movimiento donde la disposición de las lozas en un cuadrante nunca podrá resolverse. ¿Por qué? Realmente no lo entiendo,  pero parece que  existen una serie de combinaciones que no son validas, cosa que con el juguete físico nunca ocurrirán porque se mueve de manera que sus combinaciones siempre son validas.
He aquí la explicación (que no he entendido pero puede servirle a ustedes si les llama la atención)

If we treat the blank space in the puzzle as one of the tiles, then each legal move involves swapping that blank "tile" for an adjacent tile. This allows us to regard motions on the puzzle as permutations on 16 characters. That is, elements of the symmetric group S 16. Each primitive move is a "swap" or transposition between only two elements (one of which is the blank).

Because the puzzle begins and ends with the blank tile in the lower right, the blank tile must move an even number of times for the puzzle to be solved. (This is easiest to see by imagining an overlaid checkerboard pattern on top of the puzzle -- after an odd number of moves the blank would be on a different color square.) That means that the solution enacted must be a product of evenly many permutations, so it must be an element of the alternating group A 16, which has exactly half of S 16. (Of the 16! permutations of S 16, 16!/2 permutations are even, and 16!/2 are odd. Moreover even*even=even, even*odd = odd, and odd*odd=even.)

If the necessary correcting permutation happens to be odd, it's not possible to solve the puzzle, no matter what you do. If the necessary correcting permutation is even, and if Axarydax follows the strategy described, then the permutation required for the remaining 2x2 block will necessarily be an even permutation fixing the blank square. The only even permutations of only three elements are the rotations 1->2->3->1 (cycle notation (123)) and 1->3->2->1 (cycle notation (132)). These are easily performed on the remaining four squares without disturbing the others.

La explicación es tomada de aquí: http://stackoverflow.com/questions/3621623/how-to-programatically-solve-the-15-moving-numbers-puzzle

Ahora que sé que mi algoritmo está mal, me dedicaré a corregirlo, y para ello debo de conocer si la combinación de mi grid es correcta o si no. Para ello me basaré en la formula descrita en este artículo: 
http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html

Si a alguien le interesa un poco más este tema, el artículo de la formula para definir si la combinación tiene solución o no, se basó en este otro artículo:
http://kevingong.com/Math/SixteenPuzzle.html
 
Artículos relacionados:
No se han devuelto datos.