7.11. El problema de la gira del caballo¶
Otro problema clásico que podemos usar para ilustrar un segundo algoritmo de grafos común es el llamado “gira del caballo”. El rompecabezas de la gira del caballo se juega en un tablero de ajedrez con una sola pieza de ajedrez, el caballo. El objetivo del rompecabezas es encontrar una secuencia de movimientos que permitan al caballo visitar cada cuadrado del tablero exactamente una vez. Una de esas secuencias se llama “gira”. El rompecabezas de la gira del caballo ha fascinado a los jugadores de ajedrez, matemáticos y científicos por igual durante muchos años. Se sabe que la cota superior del número de giras legales posibles para un tablero de ajedrez de ocho por ocho es \(1.305 \times 10^{35}\); sin embargo, hay incluso un número mayor de posibles callejones sin salida. Claramente éste es un problema que requiere algo de buen seso, algo de verdadera potencia computacional, o ambos.
Aunque los investigadores han estudiado muchos algoritmos diferentes para resolver el problema de la gira del caballo, una búsqueda de grafos es uno de los más fáciles de entender y programar. Una vez más vamos a resolver el problema utilizando dos pasos principales:
Representar como un grafo los movimientos legales de un caballo en un tablero de ajedrez.
Usar un algoritmo de grafos para encontrar una ruta de longitud \(filas \times columnas - 1\) donde cada vértice del grafo se visite exactamente una vez.