El problema del caballo, el intrincado enigma matemático en el que no se puede repetir

Ahora bien, todos estaremos de acuerdo en que es mejor apoyarse en los descubrimientos de personas de reconocido prestigio y solvencia, no vaya a ser que nuestro punto de partida no sea correcto. Sin embargo, nadie está libre de pecado. Pero antes de acusar al pecador, hagamos un pequeño recorrido histórico.

El modo de moverse el caballo en el juego de ajedrez , tan diferente al resto de las piezas, ha despertado el interés de la comunidad matemática a lo largo del tiempo. Algunos de los problemas planteados tienen fácil solución. Por ejemplo, se ve rápidamente que un caballo necesita seis movimientos para trasladarse desde un vértice al vértice diagonalmente opuesto. Ahora bien, ya no es tan fácil descubrir que existe un total de 108 formas diferentes de realizar dicho trayecto en solo seis movimientos.

Hoy vamos a concentrarnos en el problema más famoso relacionado con el caballo de ajedrez: ¿existe algún recorrido que pase por las 64 casillas del tablero y el caballo pase una sola vez por cada casilla? Sobre este problema y sus variantes se han llegado a escribir tratados enteros, y algunos de los más insignes matemáticos de la historia han aportado su granito de arena.

El propio enunciado del problema ya propone dos versiones: encontrar recorridos “elegantes” en los que el punto final quede a un salto de caballo del punto inicial –llamados recorridos cerrados – o trayectorias que no cumplen dicha propiedad –llamados recorridos abiertos –. La ventaja de los recorridos cerrados es que cualquier punto del recorrido puede servir como punto de partida del trayecto. Pues bien, allá por el año 840 se conocían ya dos recorridos, uno abierto atribuido a Ali C. Mani y uno cerrado atribuido a al-Adli ar-Rumi , ambos ajedrecistas árabes. Hoy en día se cree que existen más de 33 billones de soluciones posibles , gracias al trabajo de Martin Löbbing e Ingo Wegener quienes, en 1995, pusieron 20 ordenadores a funcionar conjuntamente durante cuatro meses.

Si la ciencia avanza que es una barbaridad, se debe a que la humanidad no se ha conformado con obtener respuestas sino por plantear nuevas preguntas. En el tema que nos ocupa, las preguntas que surgieron fueron: ¿es posible que un caballo de ajedrez pueda realizar un recorrido completo en tableros con un número diferente de filas y columnas que el usual?

El primer estudio matemático del problema fue presentado por el ilustre Leonhard Euler a la Academia de Ciencias de Berlín en 1759 optando a la recompensa de 4.000 francos que se ofrecía al mejor trabajo sobre el problema del caballo (no llegó a recibir el premio ya que era el director de la Academia en esa época y no quedaba bien ser arte y parte). En ese trabajo Euler afirmó que no existe ningún recorrido cerrado de un caballo de ajedrez en tableros rectangulares con menos de cinco filas. La autoridad de su afirmación hizo que nadie se la cuestionara durante 150 años, hasta que Ernest Bergholt demostró en 1918 la existencia de recorridos en tableros de tres filas y diez columnas así como en tableros de tres filas y doce columnas (publicó sus soluciones en la revista British Chess Magazine). ¡El gran Euler se equivocó esta vez!

En 1991, Allen Schwenk probó que, en un tablero de m filas y n columnas (con m menor o igual que n), es posible encontrar un recorrido cerrado de un caballo de ajedrez salvo si se cumple alguna de estas condiciones:

m y n son impares.

m=1, 2 o 4.

m=3 y n=4, 6 u 8.

En resumen, excepto para tableros de tamaño 3x4, 3x6 y 3x8, existen recorridos cerrados de un caballo de ajedrez en tableros de tamaño 3xn, siendo n un número par.

Por cierto, otro problema que se planteó Euler en el trabajo citado fue el de construir un cuadrado mágico al numerar los pasos sucesivos del caballo en su recorrido por el tablero. Solo pudo conseguir un cuadrado semimágico y dejó pendiente de solución el problema de conseguir que la suma de las diagonales fuera también la misma que la de las filas y columnas.

Con otra pieza de ajedrez, concretamente con el rey, es posible encontrar un recorrido por todo el tablero de modo que el cuadrado numérico resultante sea mágico: la suma de los números en cada fila, cada columna y cada diagonal es igual a 260.

Parece que no se ha encontrado solución al problema equivalente con el movimiento del caballo. De hecho, en 2003 salió a la luz el resultado de  Jean Charles Meyrignac y Guenter Stertenbrink quienes demostraron que existe un total de 140 cuadrados semimágicos en un tablero de ajedrez que corresponda al recorrido de un caballo pero, lamentablemente, ninguno de ellos es un cuadrado mágico. En esta página detallan su trabajo y muestran el programa utilizado.

De acuerdo, es posible que sea una pérdida de tiempo dedicarse a resolver este tipo de problemas intrascendentes. Pero problemas de optimización en todo tipo de transportes –rutas de mínima distancia pero máximo aprovechamiento– son muy actuales y en las técnicas utilizadas para su resolución son muy importantes los algoritmos más eficientes y precisos, como los que se pueden aplicar al resolver el dichoso problema del salto del caballo. Incluso, a nivel didáctico, estos problemas son muy apropiados para ilustrar la teoría de grafos , especialidad matemática de gran alcance.

El ABCDARIO DE LAS MATEMÁTICAS es una sección que surge de la colaboración con la Comisión de Divulgación de la Real Sociedad Matemática Española (RSME).

Pedro Alegría es profesor de matemáticas en la UPV/EHU y miembro de la comisión de divulgación de la RSME.