El tour del caballo

El caballo saltarín

En esta sección, nos adentraremos en la exploración de uno de los problemas más intrigantes originados del fascinante mundo del ajedrez. El protagonista de este enigma es el caballo, una pieza cuyo singular tipo de movimiento lo distingue de todas las demás piezas en el tablero de ajedrez. Esta peculiaridad convierte este problema en un retador pasatiempo intelectual. Sin más preámbulos, la definición del problema:

“Colocamos el caballo en una casilla inicial en un tablero de dimensiones $m \times n$. El objetivo es encontrar un camino que recorra cada casilla del tablero exactamente una vez.”

En términos más sencillos, el desafío consiste en recorrer todas las casillas del tablero, sin repetir ninguna, utilizando el característico movimiento en “L” del caballo. Al enfrentarse por primera vez a este desafío, es probable que uno se dé cuenta de que no es nada trivial, y puede requerir varios intentos para lograrlo incluso en el clásico tablero de $8 \times 8$. Es importante destacar que el tablero no necesariamente tiene que ser cuadrado; puede ser cualquier rectángulo.

Este problema ha capturado la atención de notables matemáticos a lo largo de la historia. Entre ellos destaca Leonhard Euler, considerado uno de los matemáticos más preeminentes de todos los tiempos. Euler no solo logró resolver este problema para un tablero de $8 \times 8$, sino que además construyó un semi-cuadrado mágico en el que cada fila y columna suman 260, las mitades de las filas y columnas suman 130, y cada número representa el orden del movimiento con el cual el caballo visitó esa casilla en particular.

La elegancia de esta solución se puede apreciar en el cuadrado mágico de Euler.

Más allá de esta intrigante construcción, este problema también puede ser utilizado como un medio para generar arte computacional. A continuación, se presenta una serie de composiciones artísticas inspiradas en los movimientos de un caballo:

Las obras representadas corresponden a tableros de diferentes tamaños: 20x20 (esquina superior izquierda), 50x50 (esquina superior derecha), 64x64 (esquina inferior izquierda) y 130x130 (esquina inferior derecha). Cada una de estas composiciones ilustra la rica variedad de patrones que pueden surgir de la sencilla pero desafiante tarea de recorrer un tablero de ajedrez con un caballo.

Para relacionar más al lector con el problema procederé a mostrar la solución de un tablero 8x8 mediante flechas:

Una observación crucial en la resolución de este problema es que las primeras casillas que visita el caballo tienden a estar ubicadas en las regiones más alejadas del centro. Esta técnica desempeña un papel fundamental en la solución del desafío planteado. Por si no se ha dado cuenta se trata de la solución al cuadrado mágico de Euler mostrado anteriormente.

El tour del caballo en este contexto está estrechamente vinculado a uno de los problemas más relevantes en el campo de la informática: el conocido problema de encontrar un camino hamiltoniano, el cual se clasifica como un problema NP.

Caminos hamiltonianos y grafos

El problema del camino hamiltoniano se define de la siguiente manera:

“Dado un grafo, se busca encontrar un camino que visite cada uno de los vértices exactamente una vez”. (Un camino es la secuencia en la que se recorren los vértices del grafo).

Esta definición presenta una notable similitud con el concepto del tour del caballo. Pero ¿qué son exactamente un grafo y sus vértices?

Un grafo es una estructura de datos que proporciona una gran flexibilidad para representar relaciones entre diferentes elementos. Consiste en un conjunto de vértices (también conocidos como nodos) y aristas (o conexiones). Los vértices pueden ser cualquier tipo de objeto, desde números hasta palabras y objetos más complejos. Las aristas, por otro lado, conectan dos vértices si existe alguna relación entre ellos. En el caso de que las aristas tengan un valor numérico que represente algún aspecto de la relación entre los elementos conectados, se denomina grafo valuado.

Volviendo al tema del camino hamiltoniano, al modificar ligeramente las condiciones del problema, surgen dos problemas interesantes adicionales. Si agregamos la restricción de que, al llegar al último vértice, se debe regresar al vértice inicial, se obtiene lo que se conoce como ciclo hamiltoniano. Por otro lado, si utilizamos un grafo valuado (cada arista tiene asociado un número que expresa el coste de usar esa arista) y buscamos el camino que minimice la suma de los valores de las aristas recorridas, nos enfrentamos al problema del viajante.

Pero ¿cómo se relacionan los grafos y los diferentes problemas hamiltonianos con el tour del caballo?

Aunque no sea evidente a primera vista, el tablero de ajedrez puede considerarse como un grafo implícito, donde los vértices y las aristas están presentes de manera disimulada. En este caso, los vértices representarían las casillas del tablero, mientras que las aristas modelarían la relación entre dos casillas. Por lo tanto, habría una arista entre dos casillas específicas si es posible moverse de una a otra mediante un único movimiento del caballo. A continuación, se muestra un ejemplo de un tablero de $3 \times 3$ y su correspondiente transformación en un grafo que ilustra el anterior concepto.

En primer lugar, se numeran las casillas del tablero asignándole a cada uno de ellas un número natural (esto es una técnica muy usual a la hora de trabajar con grafos) y se dibuja el grafo.

En esta representación, se cumple que existe una arista entre dos casillas si es posible moverse entre ellas en un solo movimiento. Por ejemplo, desde la casilla 9 se puede llegar a las casillas 4 y 2 mediante un movimiento de caballo, mientras que la casilla 5 no tiene ninguna arista, ya que no es posible llegar a ella desde ninguna otra casilla.

Ahora bien, ¿cómo es capaz un ordenador de entender un grafo y cómo se representa para que sea comprendido por una máquina?

Representación de grafos

La representación de un grafo es un elemento crucial en la eficacia y eficiencia de los algoritmos que los utilizan. Existen múltiples representaciones, cada una con sus ventajas y desventajas únicas. Antes de adentrarnos en la explicación de estas representaciones, es esencial reconocer que los grafos pueden ser de dos tipos: dirigidos y no dirigidos.

En los grafos dirigidos, las aristas funcionan como “flechas”, es decir, la relación existe sólo desde un vértice hacia otro, y puede darse el caso de que no exista una relación en sentido contrario. En contraste, en los grafos no dirigidos, las aristas indican que existe una relación bidireccional entre los dos vértices, tal como se ilustró con el grafo que discutimos anteriormente.

Entre las diversas representaciones de grafos, la matriz de adyacencia es una opción notable. Como su nombre lo sugiere, es una matriz en la que la fila $i$ y la columna $j$ representan la relación desde el vértice $i$ hacia el vértice $j$.

Si estamos trabajando con un grafo no ponderado, es común usar un 1 para denotar la existencia de una arista desde $i$ a $j$, y un 0 en caso contrario. Sin embargo, si el grafo es ponderado, colocaremos el valor de la arista que conecta los vértices $i$ y $j$ en la respectiva posición de la matriz. Si no existe tal conexión, a menudo se usa un número muy grande para indicar que la arista es inutilizable, aunque también existen otras alternativas.

Tomemos, por ejemplo, la matriz de adyacencia del grafo de un tablero 3x3, que se representaría de la siguiente manera:

Es relevante notar que la matriz de adyacencia es simétrica. Es decir, si intercambiamos filas por columnas, obtenemos la misma matriz. Esta característica siempre está presente en las matrices de adyacencia de grafos no dirigidos, debido a la naturaleza bidireccional de sus relaciones. Puede parecer que existe una redundancia de información, y en efecto, así es. Por lo tanto, realmente sólo necesitamos la mitad de la matriz, específicamente, la sección por encima o debajo de la diagonal que se extiende desde la esquina superior izquierda hasta la esquina inferior derecha, para tener todos los datos necesarios del grafo. Además, es importante señalar que tanto la columna como la fila del 5 están vacías, ya que es imposible llegar a esa casilla o partir de ella hacia otra.

La principal ventaja de esta representación es que permite consultar en tiempo constante si se puede pasar de un vértice a otro. Esto es particularmente útil en la implementación de dos algoritmos ampliamente utilizados en grafos: Warshall y Floyd. Warshall es útil para determinar si existe un camino entre un vértice y cualquier otro, y también proporciona dicho camino. Por otro lado, Floyd opera sobre grafos ponderados y proporciona el camino más corto entre dos vértices, si existe, y el valor de dicho camino.

Sin embargo, la matriz de adyacencia también almacena relaciones inexistentes, es decir, los 0s en la matriz. Además, estos 0s superan en número a los 1s, lo que indica que el número de relaciones es pequeño en comparación con el total de posibles relaciones. Esto nos lleva a preguntar: ¿no debería existir una forma de almacenar únicamente las relaciones existentes en el grafo y evitar almacenar los 0s?

Efectivamente, la respuesta es afirmativa. Para este propósito, se puede utilizar la lista de adyacencia. Su principal premisa es almacenar sólo las relaciones entre los diferentes vértices, lo que permite un gran ahorro de memoria e incluso, en ocasiones, de tiempo de cómputo. En una lista de adyacencia, cada vértice tiene asignada una lista en la que figuran los vértices con los que está relacionado. La lista de adyacencia para el grafo anterior se presentaría de la siguiente manera:

Como puede ver, se ha logrado una significativa reducción en la cantidad de información almacenada utilizando la lista de adyacencia. En este caso específico del tablero de ajedrez, somos afortunados ya que una pieza de caballo solo puede moverse a un máximo de dos casillas. Sin embargo, a medida que el tamaño del tablero aumenta, la eficiencia en términos de memoria de la lista de adyacencia sobre la matriz de adyacencia también se incrementa. Esto se debe a que, como mucho, un caballo podrá moverse a 8 casillas diferentes desde una casilla específica, por lo que la lista tendrá a lo sumo ese número de elementos.

La principal desventaja de este método de representación es que, si necesitamos verificar la existencia de una arista entre dos vértices, debemos buscar en la lista del primer vértice para ver si el segundo vértice aparece o no. Es importante mencionar que esta representación también puede ser usada para grafos ponderados. En ese caso, los elementos de las listas son reemplazados por tuplas de dos valores: el vértice y el peso de la arista. Esta representación puede no ser adecuada para algoritmos como Floyd o Warshall El algoritmo de Floyd encuentra la ruta más corta entre todos los pares de nodos en un grafo. Por otro lado, el algoritmo de Warshall determina si existe un camino entre todos los pares de nodos., pero es más eficiente para algoritmos que buscan caminos o ciclos hamiltonianos.

Por último, vale la pena mencionar que existe otra forma de representar un grafo, denominada lista de aristas. Como su nombre lo indica, esta lista contiene todas las aristas, cada una expresada como una tupla de dos enteros, donde el primer entero representa el vértice origen y el segundo el vértice destino. Sin embargo, este método de representación se utiliza raramente.

Habiendo examinado las diferentes formas de representación de un grafo, estamos listos para abordar el problema del camino hamiltoniano. Para resolver este desafío, debemos recurrir a una estrategia bien conocida: el backtracking.

Backtracking vs. el tour del caballo

Al igual que en el problema de las $n$-damas, nos enfrentamos a una interrogante: ¿cómo podemos prever si una decisión que tomamos nos llevará inexorablemente a un callejón sin salida o a una solución válida?

Necesitaremos la habilidad de retroceder y explorar otros caminos para encontrar una solución válida, si es que existe. Por esta razón, el backtracking parece la opción más adecuada de manera intuitiva. Sin embargo, como se mencionó anteriormente, estamos lidiando con un problema NP. Afortunadamente, el “tour del caballo” es una versión específica del problema donde podemos mejorar notablemente la eficiencia del algoritmo utilizando una heurística Una heurística es una regla práctica o método aproximado que ayuda a simplificar y resolver problemas, a menudo permitiendo encontrar soluciones suficientemente buenas aunque no siempre óptimas. conocida como la regla de Warnsdorff. Esta regla reduce la complejidad del algoritmo, permitiendo una solución en tiempo lineal.

Una heurística es una guía que nos orienta hacia los estados que son más propensos a conducir a una solución válida. La regla de Warnsdorff nos aconseja dirigirnos hacia el vértice de menor grado. Aquí surge una nueva pregunta: ¿qué es el grado de un vértice?

El grado de un vértice se define como el número de vértices a los que se puede llegar desde dicho vértice con un único movimiento. Es similar al número de aristas de un vértice, pero no se cuentan aquellas aristas que llevan a un vértice ya visitado. Si el grado de un vértice es 0, significa que no podremos realizar ningún movimiento más una vez que lleguemos a ese vértice. Por lo tanto, solo deberíamos dirigirnos a un vértice de grado 0 si este es el último movimiento que pretendemos hacer.

Una vez que hemos aclarado este término, podemos proceder a resolver el problema en un tablero de 5x5. Supongamos que la casilla inicial del caballo corresponde a1, es decir, un caballo situado en la esquina inferior izquierda. Usaremos una matriz de las mismas dimensiones que el tablero para registrar las casillas que ya hemos visitado y avanzar en la resolución del problema. Esta matriz será de enteros, y el valor de una casilla será el número de orden en el que fue visitada. Al comenzar, todos los valores de la matriz serán 0, excepto la casilla inicial, que tendrá el valor 1. El cero indica que esa casilla no ha sido visitada de momento.

En la primera vuelta alrededor del tablero, el caballo ha pasado por las cuatro esquinas, ya que estas siempre tienen grado 1, al llevar solo a dos casillas y una de ellas ya estará visitada (por la que ha llegado a la esquina). En el segundo movimiento, al moverse desde la casilla b3 a la a5, se aplica claramente la regla al preferir ir a la esquina a5 con grado 1 en lugar de ir a las casillas c5 o d4 con grado 3. La matriz de visitados quedaría de la siguiente manera, junto al tablero que indica los movimientos del caballo:

Siguiendo la misma heurística, el caballo realiza una segunda vuelta por el tablero, obteniendo el siguiente tablero y estado:

En la última vuelta, el tablero se completaría y se obtendría el siguiente tablero y estado final:

Como resultado interesante, se observa que la última casilla visitada es justamente la central, que en el tablero de 5x5 es la única casilla con grado 8 al inicio del problema. Esto demuestra que el caballo, siguiendo la heurística utilizada, logra alcanzar y visitar todas las casillas del tablero, finalizando en la única casilla con grado 8 al comienzo.

Para terminar, a continuación se presenta el diagrama de flujo que indica el funcionamiento del algoritmo usado para resolver el tour del caballo.

A continuación, se describen detalladamente cada uno de los pasos del algoritmo representados en el diagrama de flujo.

1. Comienzo: Se inicia el algoritmo.
2. Entrada: Se introduce el problema con la casilla inicial del caballo y el tamaño del tablero. A medida que avance el problema incluirá las casillas ya recorridas y la posición actual del caballo.
3. ¿Todas las casillas recorridas?: Se verifica si se han recorrido todas las casillas con el caballo. Si es así se termina y en caso contrario se continua con el algoritmo en la siguiente fase.
4. ¿Se puede mover el caballo a una casilla?: Se intenta colocar el caballo en una de las casillas a su alcance en un único movimiento. Esas casillas además no deben haberse visitado. En el caso de que haya más de una se ordenan siguiendo la regla de Warnsdorff de menor a mayor.
5. Retroceder última bifurcación: El algoritmo vuelve a la última bifurcación, eliminando el último movimiento del caballo junto a la indicación de que esa casilla ha sido visitada.
6. Mover caballo: Se mueve el caballo a la casilla seleccionada. La casilla en la que estaba anteriormente el caballo se marca como visitada.
7. Solución: Una matriz del mismo tamaño que el tablero usado que indica en qué movimiento ha visitado el caballo esa salida.
8. Fin: El algoritmo concluye su ejecución.

Se puede ver que es muy parecido al algoritmo de las $n$-damas. Y es natural al usar los dos backtracking. Las únicas diferencias reseñables son la representación (por algo es la parte más importante del algoritmo) y el uso de la regla de Warnsdorff. La regla simplemente cambia el orden en el que se visitan las casillas priorizando aquellas que tengan menos movimientos disponibles.

Complejidad algorítmica del tour del caballo

En el estudio de la complejidad algorítmica, resulta habitual tomar en consideración el caso peor, aquel en que todas las circunstancias posibles que pueden ser adversas efectivamente ocurren. Una estrategia simplificada para calcular este escenario peor podría consistir en suponer que el caballo siempre podrá mover al máximo número de casillas.

Por ejemplo, partiendo de una casilla en un tablero de ajedrez, es posible realizar hasta 8 movimientos distintos, es decir, cada vértice en este contexto tiene un máximo de 8 aristas. Esto implica que para cada casilla transitada, existen 8 posibles elecciones. Dado que el tablero es de dimensiones n x m, esta decisión se tomaría n*m veces, proporcionando la siguiente fórmula para la complejidad en el peor caso:

Donde $n$ denota el número de filas y $m$ el número de columnas. Aunque este cálculo muestra un crecimiento exponencial, afortunadamente este límite superior está bastante alejado de la verdadera complejidad del problema en cuestión.

En la mayoría de los casos, el número de elecciones será menor a 8, dado que puede suceder que la casilla en estudio tenga menos de 8 aristas, o que alguna de estas aristas conduzca a una casilla previamente visitada, la cual no necesitará ser considerada nuevamente. Aplicando la heurística de Warnsdorff, el recorrido del tablero se realiza desde el exterior hacia el interior, lo que implica que, al llegar a las casillas centrales, ya se habrá visitado las casillas periféricas a estas, evitando así considerar numerosas trayectorias.

Con estas consideraciones, el problema puede resolverse en un tiempo razonable mediante un ordenador, incluso cuando $n$ y $m$ son superiores a 100. En el caso de que el tour del caballo busque encontrar un ciclo hamiltoniano, es decir, un recorrido que desde la última casilla permita regresar a la inicial en un solo movimiento, esta heurística no reduciría la complejidad de manera tan significativa, ya que no orienta la búsqueda hacia la última casilla apropiada.

Comparando la complejidad del problema general del camino/ciclo hamiltoniano y el problema del viajero, se puede observar una notable diferencia respecto al tour del caballo, dado que cada vértice en estos problemas podría tener un número indeterminado de aristas, desde una sola hasta una arista dirigida a cada uno de los otros vértices.

Nuevamente, para el cálculo de la complejidad es necesario considerar el peor caso, en el que todos los vértices están conectados con todos los demás. Si consideramos un grafo con $n$ vértices, donde existe una arista entre todos los vértices, en el primer vértice tendríamos que elegir entre $n - 1$ aristas, ya que solo se ha visitado este primer vértice. En el segundo vértice, tendríamos $n - 2$ opciones de aristas, ya que el primer vértice y el actual ya han sido visitados. Continuando con este procedimiento, se puede apreciar su similitud con la función factorial, lo que nos lleva a la siguiente fórmula:

En la búsqueda del camino/ciclo hamiltoniano, no se alcanzaría esta complejidad en un escenario donde todos los vértices están interconectados, ya que habría un camino/ciclo hamiltoniano posible seleccionando las aristas de manera aleatoria. Sin embargo, esta complejidad se presenta con frecuencia en el problema del viajero, debido a la posibilidad común de que todos los vértices estén conectados. En este caso, sería necesario explorar todas las rutas posibles para determinar cuál de ellas tiene un coste menor Afortunadamente, es posible reducir esta complejidad utilizando el paradigma de la programación dinámica, que posee una complejidad de $O(2^n*n^2)$. Este tópico será tratado en el próximo capítulo. [Steven Halim, 2013].

Con respecto a la heurística utilizada en el tour del caballo, no resultaría muy útil en el caso general, ya que su aporte a la identificación de las rutas más prometedoras no es suficiente para compensar el coste computacional asociado a su aplicación.