PROYECTO PARA RESOLVER UN PROBLEMA DE UN JUEGO CLÁSICO

 

En IA, los puzzles son considerados retos para medir el desempeño de distintos algoritmos desarrollados y de comprobar los avances en juegos utilizando la información o características elegidas por el programador (número de piezas colocadas correctamente, distancia de cada nodo a su posición final, etc.).

 

OBJETIVO del juego

 

En esta práctica, el alumno elegirá un algoritmo para resolver el puzzle de N^2 – 1 para N = 4, de donde también tendrá la libertad de elegir las características o features que considere necesarias para alcanzar la solución del juego.

 

 

-DESARROLLO DE LA PRÁCTICA

 

1.- Identifique las reglas del Puzzle:

Observe la siguiente matriz de 4 x 4:

 

Observe que existen 15 números distintos naturales en el rango del [1, 15] y un espacio vacío, distribuidos de

forma aleatoria en la matriz. Solamente es válido permutar una posición del espacio en blanco con cualquiera

de los 4 vecinos del espacio en blanco. Por ejemplo, son movimientos válidos:

ó

 

 

 

NO es un movimiento válido moverse en diagonales

El objetivo del Puzzle es el de ordenar la matriz, de la siguiente manera:

2.- Cree las clases o estructuras que considere necesarias.

Implemente clases o estructuras que le permitan abstraer el problema en algo más simple. No existen restricciones en este aspecto.

 

3.- Si va a utilizar la recursión, tenga cuidado.

La memoria asignada a la pila para las llamadas a recursión es muy limitada, por lo que si decide utilizar la recursión normalmente puede alcanzar una excepción en el programa causada por el desborde de dicha pila, por lo que tómese su tiempo de pensar bien en una solución iterativa, o bien, cree su propia pila de recursión y utilícela.

 

4.- Comience con los números colocados aleatoriamente en la matriz.

Considere que no todas las matrices colocadas de forma aleatoria tienen solución. Es aconsejable investigar qué posiciones iniciales de los números tienen solución.

 

5.- Pruebe el desempeño de su algoritmo.

Realice cinco pruebas en donde mida el tiempo que le toma a su algoritmo alcanzar el resultado. Promédielo y repórtelo en una tabla junto con la matriz inicial escogida. Pruebe con cuatro distintas matrices iniciales.

 

6.- Consejos.

• Implementar una estructura que recuerde si un determinado estado ya fue visitado anteriormente, para

evitar ciclos infinitos en el programa.

• Un algoritmo interesante es aquél que mide la distancia entre la posición de un nodo entre su posición

actual y la posición final a que debe llegar.

 

EVALUACIÓN Y RESULTADOS

 

La evaluación de esta práctica será mediante la exposición del algoritmo funcionando en clase, y un reporte escrito por los alumnos pertenecientes al curso, el cual deberá incluir imágenes o capturas de pantalla de las implementaciones realizadas, así como de las evaluaciones del desempeño de sus algoritmos. Sólo será calificación aprobatoria si el algoritmo cumple con el objetivo.

 

 

 

 

 

 

 

bibliografía

 

 

 

https://www.itescam.edu.mx/principal/sylabus/fpdb/recursos/r148974.PDF