8puzzle

IS563 Proyecto de Programación

8 Puzzle
Escriba un programa para resolver el problema del 8­puzzle (y su generalizacion natural) usando el algoritmo de busqueda A*.
El Problema. El problema del 8­puzzle es un rompecabezas popularizado por Sam Loyd en la década de 1870. Se juega en una cuadrícula de 3­por­3 con bloques marcados del 1 al 8 y uno en blanco. Su objetivo es reorganizar los bloques para que estén en orden. Está permitido deslizar
los bloques horizontal o verticalmente dentro del cuadro en blanco. A continuación se muestra una secuencia de movimientos legales desde un
tablero inicial (izquierda) a la posición objetivo (derecha).
    1  3        1     3        1  2  3        1  2  3        1  2  3
 4  2  5   =>   4  2  5   =>   4     5   =>   4  5      =>   4  5  6 7  8  6        7  8  6        7  8  6        7  8  6        7  8 
 inicial                                                      meta

Búsqueda mejor el primero. A continuación se describe una solución algorítmica al problema que muestra una metodología de inteligencia
artificial conocida como Algoritmo de búsqueda A*. Se define un estado del juego como: la posición del tablero, el número de movimientosrealizados para alcanzar la posición del tablero y los estados anteriores. Primero, se inserta el estado inicial (el tablero inicial, 0 movimientos y,
un estado anterior nulo) dentro de una cola de prioridad. Luego, se borra de la cola de prioridad el estado con la prioridad mínima y se inserta,dentro de la cola de prioridad, todos los estados vecinos (aquellos que pueden ser alcanzados en un movimiento). Repita este procedimiento
hasta que el estado sacado sea el estado objetivo. El éxito de este enfoque depende de la elección de la función de prioridad para un estado. Se
consideran dos funciones de prioridad:
Función prioridad de Hamming. El número de bloques en posición incorrecta, más el número de movimientos realizados para alcanzar elestado. Intuitivamente, estados con un número menor de bloques en posición incorrecta están cerca del estado objetivo y se prefiere
estados que hayan sido alcanzados usando un pequeño número de movimientos
Función prioridad Manhattan. La suma de las distancias (suma de la distancia vertical y horizontal) de los bloques a su posición objetivo,
más el número de movimientos realizados hasta ahora para alcanzar el estado.Por ejemplo, las prioridades Hamming y Manhattan del estado inicial a continuación son 5 y 10, respectivamente.
 8  1  3        1  2  3     1  2  3  4  5  6  7  8    1  2  3  4  5  6  7  8
 4     2        4  5  6     ­­­­­­­­­­­­­­­­­­­­­­    ­­­­­­­­­­­­­­­­­­­­­­
 7  6  5        7  8        1  1  0  0  1  1  0  1    1  2  0  0  2  2  0  3
 inicial          meta         Hamming = 5 + 0          Manhattan = 10 + 0Observación clave: para resolver el puzzle desde un estado dado en la cola de prioridad, el número total de movimientos que debemos hacer
(incluidos los que ya se han hecho) es al menos su prioridad, usando la función Hamming o Manhattan. (Para la prioridad Hamming, esto es
cierto, ya que cada boque fuera de lugar debe moverse al menos una vez para llegar a su posición objetivo. Para la prioridad Manhattan, esto escierto, ya que cada bloque debe mover su distancia Manhattan a su posición objetivo. Observe que no se cuenta el bloque en blanco cuando se
calcula las prioridades Hamming o Manhattan.)
Consecuentemente, tan pronto como se saca un estado, no sólo se ha descubierto una secuencia de movimientos desde el tablero inicial al tablero
asociado con el estado, sino que se tiene el menor número de movimientos. (Desafío para aquellos con inclinación matemática: probar estehecho).
Una optimización importante. Después de implementar la búsqueda mejor el primero, se dará cuenta de una característica molesta: estados
correspondiendo a la misma posición del tablero están están en la cola de prioridad muchas veces. Para evitar exploraciones innecesarias de...