En el capítulo anterior vimos de que iba el tema del backtracking, ahora vamos a ver un nuevo ejemplo y algún que otro concepto de la IA, veremos otra aplicación de esta técnica como el 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)
	contador1
     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 o el método en que se resuelve una de las soluciones. El circuito del Caballo

La Heurística

Como ya os habreis 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.

El concepto de heurística representa al de un indicador de la calidad de la solución parcial de la rama que estamos mirando, puede ser excluyente o dar una idea de lo buena que puede llegar a ser esa solución.

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.

De cualquier modo, la exploración se debe hacer dando prioridad a la heurística más prometedora. En el mundo real se puede hacer la apreciación de elegir un camino, el oscuro y tenebroso o el iluminado y transitado.