Tiene este juego una solución

Question

Estoy desarrollando un juego simple usando Java swing. Quiero saber si este juego en particular tiene una solución en el siguiente escenario. Si estoy convencido de que teóricamente no se puede llegar a una solución en este punto, enviaré una notificación al usuario.

3x3
http://img814.imageshack.us/img814/7449/screenshot20100924at206.png

4x4
http://img39.imageshack.us/img39/1851/screenshot20100924at241.png

El objetivo de este juego es llenar los números del 1 al 8 (o de 1 a 15) utilizando el espacio disponible para empuje los números a ese espacio vacío. Cada vez que termino con la combinación que se muestra arriba. Solo quiero convencerme a mí mismo de que no hay forma de obtener la solución adecuada del escenario anterior. Por favor ayuda.

EDIT: solución ha sido publicado en here y here

Answer 1

Sí, y no. Si genera los números aleatoriamente, creo que hay una situación que podría ocurrir que hace que el rompecabezas sea insoluble. La forma en que sugiero generar un rompecabezas es comenzar con el acertijo resuelto y ejecutar un número (aumentando en función de la dificultad) de los movimientos en reversa. De esa forma sabrá que el rompecabezas final es solvente.

Answer 2

Probablemente esta discusión de The 15 Puzzle le dará la respuesta. Sospecho que el análisis de las permutaciones en ese rompecabezas se aplicará a su rompecabezas más pequeño.

Answer 3

de la Wikipedia francés en el "Taquin" (El rompecabezas de 15):

Anécdota

Posición initiale du taquin de Sam Loyd Loyd
affirma qu'il avait «rendu le monde entier fou »avec un taquin modifié. Dans la configuration proposée, les carreaux 14 et 15 étaient inversés, l'espace vide étant placé à bas à droite. Loyd prétendait avoir promis 1 000 USD à celui qui remettrait les carreaux dans l'ordre, mais la récompense n'aurait jamais été réclamée.
La resolución de la problème est imposible. D'une part, il faut en effet échanger les places des carreaux 14 et 15, et l'on peut montrer que cette opération nécessite un nombre débiles de glissements. D'autre part, il faut que la case vide retrouve sa place initiale, opération qui, quant à elle, nécessite un nombre pair de glissements. Il est toutefois possible d'ordonner les chiffres de 1 à 15 si la case vide est initialement en haut à gauche.

---

Anécdota

posición inicial de 15 rompecabezas de Sam Loyd
Loyd dijo que había "hecho el mundo loco" con un rompecabezas de 15 modificado. En la configuración propuesta, las piezas 14 y 15 se invirtieron, y el espacio vacío se colocó en la parte inferior derecha. Loyd afirmó haber prometido 1 000 USD a alguien que pondría las fichas en orden, pero nunca se reclamó la recompensa. Resolver este problema es imposible.Por un lado, debe intercambiar los lugares de los mosaicos 14 y 15, y se puede demostrar que esta operación requiere un número impar de diapositivas. Por otro lado, el espacio vacío debe volver a su posición original, una operación que requiere un número par de diapositivas. Es posible ordenar los números del 1 al 15 si el espacio vacío está inicialmente en la esquina superior izquierda.

---

Recursos:

• fr.wikipedia - Taquin