Gira de Knight

Un recorrido de caballo es una secuencia de movimientos de un caballo en un tablero de ajedrez en la que el caballo visita cada casilla exactamente una vez. Si el caballo termina en una casilla que está a un movimiento de caballo de la casilla inicial (de modo que podría recorrer el tablero de nuevo inmediatamente, siguiendo el mismo camino), el recorrido es "cerrado" o "reentrante"; de lo contrario, es "abierto". ^{[ 1 ] [ 2 ]}

El problema del recorrido del caballo es el problema matemático de encontrar un recorrido del caballo. Crear un programa para encontrar un recorrido del caballo es un problema común que se les plantea a los estudiantes de informática . ^{[ 3 ]} Las variaciones del problema del recorrido del caballo involucran tableros de ajedrez de tamaños diferentes al habitual de 8 × 8 , así como tableros irregulares (no rectangulares).

El problema del recorrido del caballo es una instancia del problema más general del camino hamiltoniano en la teoría de grafos . El problema de encontrar un recorrido cerrado del caballo es, de manera similar, una instancia del problema del ciclo hamiltoniano . A diferencia del problema general del camino hamiltoniano, el problema del recorrido del caballo se puede resolver en tiempo lineal . ^{[ 4 ]}

La referencia más antigua conocida al problema del recorrido del caballo data del siglo IX d. C. En el Kavyalankara de Rudrata ^{[ 6 ]} (5.15), una obra sánscrita sobre poética, el patrón del recorrido de un caballo en medio tablero se presenta como una figura poética elaborada ( citra-alaṅkāra ) llamada turagapadabandha o «disposición en los pasos de un caballo». El mismo verso, dividido en cuatro líneas de ocho sílabas cada una, puede leerse de izquierda a derecha o siguiendo el camino del caballo en su recorrido. Dado que los sistemas de escritura índicos utilizados para el sánscrito son silábicos, cada sílaba puede considerarse como una casilla en un tablero de ajedrez. El ejemplo de Rudrata es el siguiente:

transliterado:

Por ejemplo, la primera línea se puede leer de izquierda a derecha o moviéndose del primer cuadrado a la segunda línea, tercera sílaba (2.3) y luego a 1.5 a 2.7 a 4.8 a 3.6 a 4.4 a 3.2.

El poeta y filósofo Sri Vaishnava Vedanta Desika , durante el siglo XIV, en su obra magna de 1008 versos que alaba las sandalias divinas de Srirangam de la deidad Ranganatha , Paduka Sahasram (en el capítulo 30: Chitra Paddhati ), compuso dos versos consecutivos en sánscrito que contienen 32 letras cada uno (en metro Anushtubh ), donde el segundo verso se puede derivar del primero realizando un recorrido del caballo en un tablero de 4 × 8 , comenzando desde la esquina superior izquierda. ^{[ 7 ]} El verso 19 transliterado es el siguiente:

El vigésimo verso que se puede obtener realizando el recorrido del caballero sobre el verso anterior es el siguiente:

sThi thA sa ma ya rA ja thpA

ga tha rA mA dha kE ga vi |

dhu ran ha sAm sa nna thA dhA

sA dhyA thA pa ka rA sa rA ||

Se cree que Desika compuso los 1.008 versos (incluido el especial Chaturanga Turanga Padabandham mencionado anteriormente) en una sola noche como un desafío. ^{[ 8 ]}

Un recorrido descrito en el quinto libro del Bhagavantabaskaraby de Bhat Nilakantha, una obra enciclopédica en sánscrito sobre ritual, ley y política, escrita alrededor de 1600 o 1700, describe tres recorridos de caballeros. Los recorridos no solo son reentrantes, sino también simétricos, y los versos se basan en el mismo recorrido, partiendo de diferentes casillas. ^{[ 9 ]} La obra de Nilakantha es un logro extraordinario, al tratarse de un recorrido cerrado completamente simétrico, anterior a la obra de Euler (1759) por al menos 60 años.

Después de Nilakantha, uno de los primeros matemáticos en investigar el recorrido del caballo fue Leonhard Euler . El primer procedimiento para completar el recorrido del caballo fue la regla de Warnsdorf, descrita por primera vez en 1823 por H. C. von Warnsdorff.

En el siglo XX, el grupo de escritores Oulipo lo utilizó, entre muchos otros. El ejemplo más notable es el recorrido del caballero de 10 × 10 que establece el orden de los capítulos en la novela de Georges Perec , La vida, manual de instrucciones .

En la sexta partida del Campeonato Mundial de Ajedrez de 2010 entre Viswanathan Anand y Veselin Topalov, Anand realizó 13 movimientos consecutivos de caballo (aunque utilizando ambos caballos); los comentaristas en línea bromearon diciendo que Anand estaba intentando resolver el problema del recorrido del caballo durante la partida.

Schwenk ^{[ 11 ]} demostró que para cualquier tablero m × n con m ≤ n , siempre es posible un recorrido cerrado del caballo a menos que se cumpla una o más de estas tres condiciones:

1. m y n son ambos impares
2. m = 1, 2 o 4
3. m = 3 y n = 4, 6 u 8.

Cull et al. y Conrad et al. demostraron que en cualquier tablero rectangular cuya dimensión menor sea al menos 5, existe un recorrido del caballo (posiblemente abierto). ^{[ 4 ] [ 12 ]} Para cualquier tablero m × n con m ≤ n , siempre es posible un recorrido del caballo (posiblemente abierto) a menos que se cumpla una o más de estas tres condiciones:

1. m = 1 o 2
2. m = 3 y n = 3, 5 o 6 ^{[ 13 ]}
3. m = 4 y n = 4. ^{[ 14 ]}

En un tablero de 8 × 8 , hay exactamente 26.534.728.821.064 recorridos cerrados dirigidos (es decir, dos recorridos a lo largo del mismo camino que viajan en direcciones opuestas se cuentan por separado, al igual que las rotaciones y las reflexiones ). ^{[ 15 ] [ 16 ] [ 17 ]} El número de recorridos cerrados no dirigidos es la mitad de este número, ya que cada recorrido se puede trazar en sentido inverso. Hay 9.862 recorridos cerrados no dirigidos en un tablero de 6 × 6. ^{[ 18 ]}

Existen varias maneras de encontrar un recorrido del caballo en un tablero dado con la ayuda de una computadora. Algunos de estos métodos son algoritmos , mientras que otros son heurísticas .

La regla de Warnsdorff

Representación gráfica de la regla de Warnsdorff. Cada casilla contiene un número entero que indica la cantidad de movimientos que el caballo puede realizar desde esa casilla. En este caso, la regla nos indica que debemos movernos a la casilla con el número entero más pequeño, que es el 2.

La regla de Warnsdorff es una heurística para encontrar un único recorrido del caballo. El caballo se mueve de manera que siempre avance a la casilla desde la que tendrá el menor número de movimientos hacia adelante. Al calcular el número de movimientos hacia adelante para cada casilla candidata, no se cuentan los movimientos que vuelven a visitar una casilla ya visitada. Es posible tener dos o más opciones con el mismo número de movimientos hacia adelante; existen varios métodos para resolver estos empates, incluyendo uno ideado por Pohl ^{[ 21 ]} y otro por Squirrel y Cull ^{[ 22 ] .}

Esta regla también puede aplicarse de forma más general a cualquier grafo. En términos de teoría de grafos, cada movimiento se realiza al vértice adyacente con el menor grado . ^{[ 23 ]} Aunque el problema del camino hamiltoniano es NP-difícil en general, en muchos grafos que aparecen en la práctica esta heurística es capaz de encontrar con éxito una solución en tiempo lineal . ^{[ 21 ]} El recorrido del caballo es un caso especial de este tipo. ^{[ 24 ]}

La heurística fue descrita por primera vez en "Des Rösselsprungs einfachste und allgemeinste Lösung" de HC von Warnsdorff en 1823. ^{[ 24 ]}

Un programa informático que encuentra un recorrido del caballo para cualquier posición inicial utilizando la regla de Warnsdorff fue escrito por Gordon Horsington y publicado en 1984 en el libro Century/Acorn User Book of Computer Puzzles . ^{[ 25 ]}

Soluciones de redes neuronales

El problema del recorrido del caballo también se presta a ser resuelto mediante una implementación de red neuronal . ^{[ 26 ]} La red está configurada de tal manera que cada movimiento legal del caballo está representado por una neurona , y cada neurona se inicializa aleatoriamente como "activa" o "inactiva" (salida de 1 o 0), donde 1 implica que la neurona forma parte de la solución. Cada neurona también tiene una función de estado (descrita más adelante) que se inicializa a 0.

Cuando se permite que la red funcione, cada neurona puede cambiar su estado y salida en función de los estados y salidas de sus vecinas (aquellas que se encuentran exactamente a un movimiento de caballo de distancia) según las siguientes reglas de transición:

$${\displaystyle U_{t+1}(N_{i,j})=U_{t}(N_{i,j})+2-\sum _{N\in G(N_{i,j})}V_{t}(N)}$$

$${\displaystyle V_{t+1}(N_{i,j})=\left\{{\begin{array}{ll}1&{\mbox{si}}\,\,U_{t+1}(N_{i,j})>3\\0&{\mbox{si}}\,\,U_{t+1}(N_{i,j})<0\\V_{t}(N_{i,j})&{\mbox{en otro caso}},\end{array}}\right.}$$

dónde${\displaystyle t}$representa intervalos de tiempo discretos,${\displaystyle U(N_{i,j})}$es el estado de la neurona que conecta el cuadrado${\displaystyle i}$al cuadrado${\displaystyle j}$,${\displaystyle V(N_{i,j})}$es la salida de la neurona de${\displaystyle i}$a${\displaystyle j}$, y${\displaystyle G(N_{i,j})}$es el conjunto de vecinos de la neurona.

Aunque son posibles casos divergentes, la red debería converger eventualmente, lo que ocurre cuando ninguna neurona cambia su estado desde el tiempo${\displaystyle t}$a${\displaystyle t+1}$Cuando la red converge, codifica un recorrido del caballo o una serie de dos o más circuitos independientes dentro del mismo tablero.

• Abu Bakr bin Yahya al-Suli
• Rompecabezas de las ocho reinas
• George Koltanowski
• El camino del caballero más largo sin cruzar
• Caminata de autoevitación

• Contenido multimedia relacionado con Knight's Tours en Wikimedia Commons
• Secuencia OEIS A001230 (Número de recorridos cerrados no dirigidos del caballo en un tablero de ajedrez de 2n x 2n)
• Secuencia OEIS A390833 (Número de caminos hamiltonianos no dirigidos en el grafo de caballeros k X n)
• HC von Warnsdorff 1823 en Google Libros
• Introducción a las visitas guiadas de Knight por George Jelliss
• Notas sobre la gira de Knight por George Jelliss
• Philip, Anish (2013). "Un algoritmo generalizado de recorrido de pseudo-caballero para el cifrado de una imagen". IEEE Potentials . 32 (6): 10– 16. Bibcode : 2013IPot...32f..10P . doi : 10.1109/MPOT.2012.2219651 . S2CID 39213422 .