Puzzzle

I NTELIGENCIA ARTIFICIAL
Puzzle 3 x 3 con 3 Heurísticas
El juego del puzzle se representa, sobre un tablero de 3x3 casillas. 8 de las casillas
contienen una pieza o ficha que se puede deslizar a lo largo del tablero horizontal y
verticalmente. Las fichas vienen marcadas con los números del 1 al 8, y el 0 representa a la
casilla vacía, que permite los movimientos de las fichas. El objetivodel problema es partiendo
de un tablero inicial con las fichas desordenadas alcanzar un tablero en el que todas las fichas
estén ordenadas en orden creciente, dejando el hueco en la primer casilla del tablero. El
número total de estados o tableros posibles que se pueden generar en el juego del puzzle es 9! =
362,880 estados.
Tu labor es resolver este problema empleando 3 Heurísticas, Piezasfuera de lugar,
Suma de distancias fuera de lugar y 2 por número de regresos directos.
El estado al que se desea llegar para cualquier puzzle dado siempre será:
012
345
678

A continuación se describe como debe de funcionar cada heurística.

Primera opción del menú: Piezas fuera de lugar
Dado un puzzle inicial, lo insertarás en un pila de estados, si dicho estado aún no es la
solución, losacarás del tope de la pila, pero debes tener en cuenta que no se vale volver a meter
a dicho estado en la pila (si es que eventualmente se vuelve a generar), es decir no debes meter
estados en la pila que alguna vez ya insertaste, una vez sacado dicho estado del tope de la pila,
deberás generar los hijos de este, considerando sólo a aquellos nunca han sido insertados en la
pila, y deberáscontar el número g(n) de piezas fuera de lugar de cada estado, una vez que
tengas estos valores, los ordenaras de mayor a menor (por el número de piezas fuera de lugar) y
en ese orden los insertarás en la pila, es decir, primero insertarás el que tenga el mayor número
de piezas fuera de lugar, luego el segundo y así sucesivamente, en caso de empates, insertarás
primero el de mayor ordenlexicográfico.
El proceso continuará hasta que se llegue a la solución.
Ejemplo:
0) 1
4
6

23
05
78
Hijos

1) 1 0 3
425
678
Piezas
lugar

fuera

de

2) 1 2
45
67

4

3) 1 2 3
475
608

3
0
8

5

5

4) 1 2 3
045
678
3

META
0 12
3 45
6 78

Como puedes observar, en este ejemplo hay empate según el número de piezas fuera de
lugar (entre 2) y 3)), por lo quedeberás ordenarlos e insertarlos en la pila de la siguiente forma:
3) 1 2 3
475
608
5

2) 1 2 3
450
678
5

1) 1 0 3
425
678
4

4) 1 2 3
045
678
3

Ya que el 3) tiene menor orden lexicográfico que el 2) (recuerda que lo puedes observar
mejor si ves a las matrices como vectores), y por ende primero se inserta en la pila el 3), luego
el 2), después el 1) y finalmente el 4), queal quedar en el tope de la pila, será el siguiente estado
a evaluar (ya que como se puede ver, este no es la solución), y nuevamente el proceso se repite.
Nota: Nótese que el número 0 (blanco), no cuenta como una pieza fuera de lugar.

Segunda opción del menú: Suma de distancias fuera de lugar
Dado un puzzle inicial, lo insertarás en una pila de estados, si dicho estado aún no es lasolución, lo sacarás del tope de la pila, pero debes tener en cuenta que no se vale volver a meter
a dicho estado en la pila (si es que eventualmente se vuelve a generar), es decir no debes meter
estados en la pila que alguna vez ya insertaste, una vez sacado dicho estado del tope de la pila,
deberás generar los hijos de este, considerando sólo a aquellos nunca han sido insertados en la
pila, y deberásobtener la sumatoria h(n) de las distancias de las piezas fuera de lugar (es
decir, cuantas casillas se aleja una pieza, de donde debería encontrarse), una vez que tengas
estos valores, los ordenaras de mayor a menor (o sea la suma calculada) y en ese orden los
insertarás en la pila, es decir, primero insertarás el que tenga la mayor sumatoria, luego el
segundo y así sucesivamente, en...