UNIVERSIDAD NACIONAL DE COLOMBIA
SEDE MANIZALES
Análisis y Diseño de Algoritmos – Proyecto final – 2008-II
Escriba un programa que haciendo uso de estrategias exhaustivas, permita resolver elproblema del Puzzle, el cual se compone de un tablero cuadrado de 3×3 casillas, en las cuales se acomodan los números del 1 al 8 dejando un espacio libre para realizar los movimientos.
El programacomienza con una disposición aleatoria de los números del 1 al 8, sobre las diferentes casillas del tablero, y el objetivo del juego es presentar los movimientos que son requeridos para que eltablero quede ordenado con el espacio libre en el centro, tal como se muestra en la figura:
[pic]
Las fichas se pueden mover siempre y cuando el espacio libre esté a uno de sus lados, de tal maneraque los movimientos se hacen sobre el espacio libre así:
Ejemplo:
[pic]
Su programa debe recibir una configuración inicial del tablero (se debe cargar o leer), y luego calcular la forma dellegar a la solución mostrando cada uno de los movimientos o pasos que se deben seguir para que se alcance la configuración objetivo o final.
Los movimientos o pasos deben ser por ejemplo:mover 5 a la izquierda, mover 6 hacia arriba, …..
Notas:
• El proyecto se puede realizar en forma individual o en parejas, de tal manera que la entrega se realizará personalmente el mismo díadel Parcial 3 (Diciembre 17), antes del mismo (8:00 a.m.), en el cual se incluirá una pregunta que será la sustentación del mismo.
• Se deberá entregar el programa correspondiente, incluyendo elcódigo fuente, la explicación de cómo se desarrolló el proyecto, y la forma de utilizarlo (mini manual de usuario).
• El proyecto se calificará: 10% al funcionamiento del mismo, y 10% lasustentación (punto adicional en el examen)
———————–
En el anterior cuadro se pueden realizar los siguientes movimientos:
El 5 hacia la derecha, El 2 hacia la izquierda
El 4 hacia abajo,…
