problemas de inteligencia artificial

INTELIGENCIA 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 objetivo delproblema 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á:
0 1 2
3 4 5
6 7 8

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 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, ydeberás contar 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

2 3
0 5
7 8
Hijos

1) 1 0 3
4 2 5
6 7 8
Piezas
lugar

fuera

de

2) 1 2
4 5
6 7

4

3) 1 2 3
4 7 5
6 0 8

3
0
8

5

5

4) 1 2 3
0 4 5
6 7 8
3

META
0 1 2
3 4 5
6 7 8

Como puedes observar, en este ejemplo hay empate según el número de piezas fuera de
lugar (entre2) y 3)), por lo que deberás ordenarlos e insertarlos en la pila de la siguiente forma:
3) 1 2 3
4 7 5
6 0 8
5

2) 1 2 3
4 5 0
6 7 8
5

1) 1 0 3
4 2 5
6 7 8
4

4) 1 2 3
0 4 5
6 7 8
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), que al 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 deestados, si dicho estado aún no es la
solució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 nuncahan sido insertados en la
pila, y deberás obtener 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,...