Problema del 8-puzzle
Estoy desarrollando la aplicación del 8-puzzle, que consiste en una rejilla cuadrada en la que hay situados 9 cuadrados. 8 de estas casillas tienen un número, y la casilla restante está vacía. Cada casilla adyacente al hueco puede deslizarse hacia él. El juego consiste en transformar la posición inicial en la posición final mediante el desplazamiento de las casillas.
Estado Inicial:
------------
| 1 | 3 | 5 |
------------
| 4 | 2 | |
------------
| 7 | 8 | 6 |
------------
Estado Final:
------------
| 1 | 2 | 3 |
------------
| 4 | 5 | 6 |
------------
| 7 | 8 | |
------------
Además, el puzzle inicial debe generarse de forma aleatoria.
Tengo el programa casi totalmente implementado, solo me falta un pequeño detalle: el puzzle inicial se genera de forma aleatoria, por tanto puede darse el caso de que no exista una solución, es decir, nunca conseguiremos llegar al estado final a partir del inicial.
Bueno pues después de este rollo esta es mi pregunta: ¿Existe alguna forma de averiguar si el puzzle inicial se puede resolver?
Estado Inicial:
------------
| 1 | 3 | 5 |
------------
| 4 | 2 | |
------------
| 7 | 8 | 6 |
------------
Estado Final:
------------
| 1 | 2 | 3 |
------------
| 4 | 5 | 6 |
------------
| 7 | 8 | |
------------
Además, el puzzle inicial debe generarse de forma aleatoria.
Tengo el programa casi totalmente implementado, solo me falta un pequeño detalle: el puzzle inicial se genera de forma aleatoria, por tanto puede darse el caso de que no exista una solución, es decir, nunca conseguiremos llegar al estado final a partir del inicial.
Bueno pues después de este rollo esta es mi pregunta: ¿Existe alguna forma de averiguar si el puzzle inicial se puede resolver?
2 respuestas
Respuesta de equargnolo
1
La verdad no creo que exista una forma para que el puzzle se resuelva (osea ver si tiene solución) aunque en este juego nunca he encontrado alguna forma de que sea imposible resolver
(Mientras todos los números sean distintos) si la existiera podrías validarla para que no se diera. Bueno lamento no poder darte una respuesta más concreta pero la verdad no creo que aya alguna manera para resolver eso.
(Mientras todos los números sean distintos) si la existiera podrías validarla para que no se diera. Bueno lamento no poder darte una respuesta más concreta pero la verdad no creo que aya alguna manera para resolver eso.
