El Problema del Recorrido del Caballo de Ajedrez

por Pascual PEIRÓ CODINA

La peregrinación del caballo de ajedrez consiste en su paseo por todas las casillas del tablero sin pasar dos veces por la misma, utilizando sus movimientos: dos casillas horizontales y una vertical o a la inversa. Cuando desde la última casilla podamos pasar a la primera se trata de una "peregrinación cerrada".
A lo largo de los siglos, matemáticos de todo el mundo dedicaron un especial interés a este problema. Uno de ellos se destacó por sus ingeniosas e increíbles soluciones, Leonard Euler (Basilea - Suiza, 1707-1783). Una de sus soluciones es un recorrido en el que las filas y columnas suman 260. El desarrollo de los movimientos del caballo por las 64 casillas ya es, en sí, muy difícil de conseguir como para, además, lograr que filas y columnas sumen lo mismo.

Leonard Euler
Podemos imaginarnos cómo Euler, en el siglo XVIII, trabajó para resolver el acertijo, sus herramientas fueron una pluma, papel, mucha paciencia y una grandísima dosis de algo que demostró toda su vida: genialidad. Así, la técnica empleada sería, básicamente, la misma que he utilizado con ayuda de un programa informático diseñado en B.A.S.I.C. para este estudio, realizar movimientos del caballo de una a otra casilla hasta que, en el caso de que no queden casillas vacías, es necesario volver atrás, borrar el movimiento anterior y realizar un salto de caballo distinto. El proceso se repite hasta que se complete el recorrido.
A Euler le hubiera encantado disponer de la capacidad de cálculo de un ordenador. Al programa en B.A.S.I.C., en cambio, me encantaría añadirle la genialidad que demostró este gran matemático. A diferencia de los programas para jugar a ajedrez, este no da prioridad a los movimientos, el caballo puede mover, como máximo, a ocho casillas y, como mínimo, a dos realizándose los ocho posibles movimientos por orden. Así, intenta el primer movimiento, y si este no es posible porque la casilla está ocupada, intenta el segundo y así, sucesivamente, hasta que completa todas las posibilidades.
Teniendo en cuenta que disponemos de 64 casillas y en cada movimiento de dos a ocho posibles casillas para mover el caballo, podemos hacernos una idea del gran número de posibilidades. Sin entrar en cálculos con grandes números, traducido a tiempo real, el algoritmo podría resultar “infinito”. Por supuesto, se puede encontrar una solución en unos minutos o segundos si el ordenador realiza los movimientos adecuados. Esto me indujo a pensar en realizar recorridos con menos casillas que se pueden completar en pocos segundos, por ejemplo en un tablero de 4x4, de 5x5, de 3x8, etc,.

Para recorrer el tablero de ajedrez de 8x8 se pueden enlazar varios recorridos comenzando uno de ellos en una casilla a la que se accede desde el último movimiento del anterior. Por ejemplo dos recorridos de 3x3 se podrían enlazar como se muestra -desde la casilla de movimiento 8 pasamos al siguiente con el movimiento 9-:

Como es preferible que sean completos, hemos de analizar todas las posibilidades en cada uno de ellos. A continuación se describen algunos recorridos completos y otros que no es posible realizar (en estos se refleja un ejemplo, pero se han analizado todas las posibilidades):

3x3	3x4	3x5	4x4
No hay solución		No hay solución	No hay solución

Problema del caballo
El problema del caballo es un antiguo problema matemático en el que se pide que, teniendo una cuadrícula de n x n casillas y un caballo de ajedrez colocado en una posición cualquiera ( x, y ), el caballo pase por todas las casillas y una sola vez.
Solución para 63 saltos de caballo por las 64 casillas.
Muchos matemáticos han buscado una solución matemática a este problema, entre ellos Leonhard Euler.
Se han encontrado muchas soluciones a este problema y de hecho no se sabe con seguridad de cuántas maneras diferentes es posible solucionarlo.
Algunas variaciones de este problema han sido estudiadas por los matemáticos, tales como:
Buscar soluciones cíclicas, en la cual se debe llegar a la misma casilla de la cual se partió.
Tableros de diferente número de columnas o diferente número de filas.
Juegos de dos jugadores basados en la idea.
Problemas usando ligeras variaciones en la forma de moverse el caballo.
El problema del caballo es una forma del problema más general problema de la ruta Hamiltoniana en la teoría de grafos.
A la derecha podemos apreciar una de las posibles soluciones en un tablero de ajedrez convencional de ocho columnas por ocho filas. Abajo, una solución cíclica en que la casilla de destino es justo la anterior a la de partida.
63 14 37 24 51 26 35 10
22 39 62 13 36 11 50 27
15 64 23 38 25 52 9 34
40 21 16 61 12 33 28 49
17 60 1 44 29 48 53 8
2 41 20 57 6 55 32 47
59 18 43 4 45 30 7 54
42 3 58 19 56 5 46 31

OTROS PROBLEMAS