ESTRATEGIA DE RESOLUCIÓN
La Peregrinación del Caballo de Ajedrez consiste en hacer que el Caballo pase por todas las casillas del tablero sin pasar dos veces por la misma, utilizando los movimientos del caballo del ajedrez: Dos casillas horizontales y una vertical o a la inversa. Cuando desde la última casilla el Caballo pueda saltar a la primera (casilla desde donde se comenzó el recorrido) se trata de una "peregrinación cerrada".
La dinámica para la resolución del juego se basa principalmente en la metodología del Ensayo y Error; de la cual debe valerse el usuario (jugador) para lograr completar el reto que plantea el juego.
Para lograr lo expuesto anteriormente el juego debe básicamente restringir los movimientos que el usuario le puede dar al Caballo, esto implica que el algoritmo empleado debe ser capaz de calcular todos los movimientos posibles del Caballo desde la ubicación actual (esto se debe a que el jugador puede comenzar desde cualquiera de las 64 casillas del tablero), y una vez calculados dichos movimientos saber cuáles son válidos ya que como se dijo antes, el caballo no puede pasar dos veces por una misma casilla; para lograr dicho algoritmo se ha empleado un algoritmo iterativo basado en el método del Backtracking o Vuelta atrás debido a que, si en caso de que el jugador se quede sin movimientos posibles antes de completar el tablero, puede regresar el o los últimos saltos dados para de esa manera crear un recorrido distinto y poder hallar una solución al problema planteado.
Backtracking
Existen problemas para los que no parece haber una forma, teoría o regla fija de cálculo; que nos lleve a obtener la solución buscada, y lo único que se puede hacer es recurrir a una búsqueda exhaustiva para identificar la o las soluciones válidas entre el conjunto de todas las posibles (prueba y error, o tanteo sistemático). Es un esquema muy útil de prueba y error –Método de resolución de problemas basado en el tanteo sistemático y exhaustivo, en el cual la solución del problema se divide en pasos – las posibles soluciones se forman de manera progresiva (solución parcial), comprobando en cada paso o etapa si la solución que se está construyendo puede llevar o no a una solución satisfactoria.
Se consideran problemas cuyas soluciones son construibles por etapas o subareas, de forma que cada una de ellas admita varias soluciones o decisiones:
· Una solución será expresable en forma de tupla (X1, …., Xn), donde cada Xi∈Si representa la decisión tomada en la etapa i-ésima, de entre un conjunto finito de alternativas (Si).
· La solución buscada deberá minimizar, maximizar o satisfacer cierta función criterio o función objetivo (condiciones a cumplir para ser una solución satisfactoria o válida).
· Existirán Predicados acotadores o funciones objetivo parciales: Pi(x1, …., xi), que indiquen si (x1, …., xi) puede conducir a una solución.
Existirán dos categorías de restricciones:
o Restricciones Explícitas: indican los conjuntos Si, es decir, el conjunto finito de alternativas entre las cuales puede tomar valor cada una de las componentes de la tupla solución.
o Restricciones Implícitas: serán las relaciones que se han de establecer entre las componentes de la tupla solución (decisiones tomadas en cada etapa) para satisfacer la función objetivo (llevar a obtener una solución válida).
TABLERO
El planteamiento del juego se basa en un tablero usual de ajedrez, es decir, en un tablero de dimensión 8×8, lejos de complicarse, como parecería normal, el problema se simplifica enormemente. En efecto, es bastante conocido, al menos desde el siglo IX, el problema del recorrido de un caballo sobre un tablero de ajedrez, que puede enunciarse así:
“Encontrar la sucesión de movimientos consecutivos que ha de hacer un caballo de ajedrez, siguiendo las reglas usuales, para que, saliendo desde cualquier casilla del tablero ordinario, pase una única vez por todas las casillas del tablero”
Cada solución de este problema se llama recorrido, paseo o peregrinación del caballo. Si, además, el recorrido cumple que desde la última casilla visitada por el caballo se puede acceder a la primera, con un único movimiento del caballo, entonces el recorrido se llama cerrado.
FUNCIONES UTILIZADAS
El juego realiza lo siguiente: Se da un tablero de 8x8 con 8*8 casillas. Un caballo -que puede moverse según las reglas del ajedrez- se sitúa en cualquier casilla del tablero. Se pide encontrar, si existe, un recorrido del tablero completo, o sea, calcular un circuito de n*n-1 movimientos de forma que cada casilla del tablero sea visitada sólo una vez.
La función más importante es imgTablero_Click() cuyo pseudocódigo es el siguiente:
<PRINCIPIO imgTablero_Click>
CALCULAR casilla seleccionada por el usuario
SI tablero no esta vacío ENTONCES
MARCAR casilla como no válida {la casilla no está vacía}
REPETIR buscar casilla válida
SI casilla válida ENTONCES
MARCAR casilla como válida
SALIR DE REPETIR
FINSI
HASTA fin de movimientos posibles
SINO
MARCAR casilla como válida {la casilla está vacía}
FINSI
SI casilla no válida ENTONCES {la casilla no está vacía}
<FIN> {salir de la función porque el usuario seleccionó una casilla no válida o no vacía}
FINSI
CARGAR los 8 posibles movimientos del caballo
REPETIR mostrar los siguientes movimientos válidos desde la ubicación actual
SI columna y fila <1≤8 ENTONCES
SI casilla no ocupada ENTONCES
Sugerir casilla como nuevo movimiento
SINO
Marcar casilla como no válida
FINSI
SINO
Marcar casilla como no válida
FINSI
HASTA recorrer los 8 posibles movimientos del caballo desde la casilla actual
Marcar casilla actual como ocupada
Guardar último movimiento
Actualizar contador de caballos puestos en el tablero
SI tablero lleno ENTONCES
Juego completado
SINO
SI no hay movimientos posibles desde la casilla actual ENTONCES
Reiniciar juego o volver a juego actual y deshacer movimiento(s) para intentar otra solución
FINSI
FINSI
<FIN>
OPINIONES PERSONALES
El algoritmo de resolución del juego está basado en el Método de Tanteo Sistemático (Intento y Error) Backtracking convertido en una función iterativa debido a la forma en que está implementado en la construcción del juego, ha sido una solución idónea debido a las limitaciones encontradas en el lenguaje utilizado en su construcción; esta conversión supone un ahorro de cálculos que el programa debe realizar para, de manera interactiva con el usuario (jugador) ir encontrando una solución al problema de La Peregrinación del Caballo de Ajedrez.
El lenguaje utilizado –Visual Basic 6- fue elegido para este proyecto entre otras razones, por el hecho de ser un lenguaje visual, ya esto supone la libertad de darle al usuario un entorno gráfico amigable. Esto se ha logrado utilizando imágenes que muestran la figura del Caballo dentro del tablero del juego, además de mostrar de manera clara y agradable a la vista las sugerencias de los próximos movimientos válidos para el Caballo.
A continuación está el enlace para que pueda acceder al juego explicado anteriormente:
Instrucciones para accesar al Juego:
- Hacer Clic en el enlace anterior, el cual lo llevará a otra página Web.
- Cuando esté en la pagina Web, se encontrará con un archivo llamado LPCA.
- Darle Clic al archivo mencionado, para iniciar la descarga.
- Cuando se halla finalizado la descarga, podrá abrirlo.
- Aparecerá una ventana en la que seleccionará el botón Ejecutar.
- Y por último, podrá jugar la Peregrinación del Caballo de Ajedrez.
