Circuito del Caballo: Backtracking
Damián Miércoles 7 de Febrero del 2007
Tiempo atrás publiqué un artículo sobre backtracking, en donde se vio como salir de un laberinto, ahora les voy a exponer la manera en que se puede implementar esta técnica recursivamente para resolver el problema del Circuito del Caballo.
El “Circuito del Caballo” es un problema muy recurrido en los libros de programación, ya que si se hace con una implementación estructurada entonces es necesario conocer muy bien las estructuras de control para poder lograr llegar a la solución, y si se pide hacer recursivamente pues es muy importante estar seguro de cómo funciona la “pila de ejecución”.
El Problema
El planteamiento: Se coloca en un tablero de ajedrez vacío un caballo en la casilla que se quiera, y a partir de ahí se debe lograr “pasar” -siguiendo las reglas del movimiento del caballo en el juego de ajedrez- por las 63 casillas restantes una única vez por cada casilla.
Este problema se presta mucho para el backtracking porque no hay manera de idear una solución en general, no es como resolver un sistema de ecuaciones, y quien lo trate de resolver “a mano” tendrá obligadamente que anotar los caminos que ha seguido para ir descartando posibilidades y evitar repetir caminos. El problema no es nada nuevo, desde el siglo XVIII el matemático Leonhard Euler había encontrado una solución, y todavía sigue la pregunta abierta sobre ¿cúantas soluciones diferentes existen?
El backtracking
Ahora a los que nos atañe, necesitamos idear una función recursiva que logre “recordar” los caminos que se han tomado desde cada posición; y, para aplicar el backtracking también necesitamos que sólo retroceda hasta la casilla anterior si ya no hay posibilidad de resolver el problema desde cierto camino. El pseudocódigo sería el siguiente:
Mueve el caballo a la casilla dada
mueveCaballo (casilla)
Pone un caballo sobre el tablero en la casilla dada.
ponCaballo (casilla)
Obtiene las casillas "no visitadas" que se pueden
alcanzar con un movimiento válido de caballo desde
la casilla dada
casillasDesde (casilla)
El contador lleva el número de casillas visitadas
Booleano resuelveCaballo (casilla, contador)
if contador = 64 then
return VERDADERO
else
if contador = 0 then
ponCaballo (casilla)
contador
1
endif
for 
do
mueveCaballo (i)
if resuelveCaballo (i, contador + 1) then
return VERDADERO
else
mueveCaballo (casilla) aqui el Backtracking
endif
endfor
return FALSO
endif
end
Una solución
Esta es la animación de cómo el caballo podría lograr el circuito.
La Heurística
Como se habrán dado cuenta el algoritmo es muy ineficiente, porque es muy fácil llegar a combinaciones en donde ya es claramente imposible hacer el circuito (ej. cuando alguna casilla queda inaccesible). La primer heurística que se nos podría ocurrir es: verificar si hay casillas inaccesibles para descartar un camino de búsqueda; pero esa heurísitica no es la mejor, ya que se tendría que verificar en las 64 casillas si ya había sido visitada o si está inaccesible, cosa que no parecería importante, pero tomando en cuenta que al principio hay muchas casillas sin visitar, entonces habría que verificar muchas casillas y eso requiere más cómputo.
Otra Heurística histórica y hasta la fecha muy buena es la de Warnsdorff, que propone las siguientes reglas: (1) Se debe ir a la casilla desde la que se puedan hacer menos movimientos válidos (a casilla no visitadas) en el siguiente paso. (2) En caso de tener más de una opción se elije una al azar.
La heurística se basa en la idea de que es mejor usar primero las casillas que tengan menos posibilidades de ser alcanzadas en movimientos subsecuentes y así evitar tener casillas inaccesibles a lo largo del camino.
Una solución en Java
He aquí una clase que resuelve el problema para un tablero de tamaño 
sin usar ninguna heurística (eso les queda de tarea). Está comentada al estilo de Javadoc.
Genial!