El recorrido de un caballo es una secuencia de movimientos de un caballo en un tablero de ajedrez de modo que el caballo visita cada casilla exactamente una vez. Si el caballo termina en una casilla que está a un movimiento del caballo desde la casilla inicial (para que pueda recorrer el tablero nuevamente inmediatamente, siguiendo el mismo camino), el recorrido se cierra (o se vuelve a entrar); de lo contrario, está abierto. [1] [2]
El problema del recorrido del caballo es el problema matemático de encontrar el recorrido del caballo. Crear un programa para encontrar el recorrido de un caballero es un problema común que se plantea a los estudiantes de informática . [3] Las variaciones del problema del recorrido del caballo involucran tableros de ajedrez de tamaños diferentes a los habituales de 8 × 8 , así como tableros irregulares (no rectangulares).
El problema del recorrido del caballo es un ejemplo del problema de la trayectoria hamiltoniana más general en teoría de grafos . El problema de encontrar un recorrido de caballo cerrado es igualmente un ejemplo del problema del ciclo hamiltoniano . A diferencia del problema general de la trayectoria hamiltoniana, el problema del recorrido del caballo se puede resolver en tiempo lineal . [4]
La primera referencia conocida al problema del recorrido del caballero se remonta al siglo IX d.C. En Kavyalankara [5] (5.15) de Rudrata , una obra sánscrita sobre poética, el patrón del recorrido de un caballero en media pensión se ha presentado como una elaborada figura poética ( citra-alaṅkāra ) llamada turagapadabandha o 'disposición en el pasos de un caballo'. El mismo verso en cuatro versos de ocho sílabas cada uno se puede leer de izquierda a derecha o siguiendo el camino del caballero de gira. Dado que los sistemas de escritura índicos utilizados para el sánscrito son silábicos, se puede considerar que cada sílaba representa un cuadrado 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 pasando 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 Vaisnava Vedanta Desika , durante el siglo XIV, en su obra magna de 1.008 versos alabando las divinas sandalias de Srirangam de la deidad Ranganatha , Paduka Sahasram (en el capítulo 30: Chitra Paddhati ) ha compuesto dos versos sánscritos consecutivos que contienen 32 letras cada una (en métrica Anushtubh ) donde el segundo verso se puede derivar del primer verso realizando un recorrido de Caballero en un tablero de 4 × 8 , comenzando desde la esquina superior izquierda. [6] El verso 19 transliterado es el siguiente:
El verso 20 que se puede obtener realizando el recorrido de Knight en 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 desafío. [7]
Una gira relatada en el quinto libro de Bhagavantabaskaraby por Bhat Nilakantha, una obra ciclopédica en sánscrito sobre rituales, leyes y política, escrita alrededor de 1600 o alrededor de 1700, describe las giras de tres caballeros. Los recorridos no sólo son reentrantes sino también simétricos, y los versos se basan en un mismo recorrido, partiendo de distintas plazas. [8] La obra de Nilakantha es un logro extraordinario al ser un recorrido cerrado totalmente simétrico, anterior a la obra de Euler (1759) en al menos 60 años.
Después de Nilakantha, uno de los primeros matemáticos en investigar el recorrido del caballero fue Leonhard Euler . El primer procedimiento para completar el recorrido del caballero fue la regla de Warnsdorf, descrita por primera vez en 1823 por HC von Warnsdorf.
En el siglo XX lo utilizó, entre muchos otros, el grupo de escritores Oulipo . El ejemplo más notable es el recorrido del caballero 10 × 10 que establece el orden de los capítulos de la novela La vida, un manual de usuario, de Georges Perec .
En la sexta partida del Campeonato Mundial de Ajedrez de 2010 entre Viswanathan Anand y Veselin Topalov, Anand realizó 13 movimientos de caballo consecutivos (aunque usando ambos caballos); Los comentaristas en línea bromearon diciendo que Anand estaba tratando de resolver el problema del recorrido del caballo durante el juego.
Schwenk [10] demostró que para cualquier tablero de m × n con m ≤ n , siempre es posible un recorrido de caballo cerrado a menos que se cumplan una o más de estas tres condiciones:
Cull et al. y Conrad et al. demostró que en cualquier tablero rectangular cuya dimensión menor sea al menos 5, hay un recorrido de caballo (posiblemente abierto). [4] [11] Para cualquier tablero de m × n con m ≤ n , un recorrido de caballero siempre es posible a menos que se cumplan una o más de estas tres condiciones:
En un tablero de 8 × 8 , hay exactamente 26.534.728.821.064 recorridos cerrados dirigidos (es decir, dos recorridos por el mismo camino que viajan en direcciones opuestas se cuentan por separado, al igual que las rotaciones y las reflexiones ). [14] [15] [16] El número de recorridos cerrados no dirigidos es la mitad de este número, ya que cada recorrido se puede rastrear a la inversa. Son 9.862 recorridos cerrados no dirigidos en un tablero de 6×6 . [17]
Hay varias formas de encontrar el recorrido de un caballo en un tablero determinado con una computadora. Algunos de estos métodos son algoritmos , mientras que otros son heurísticos .
Una búsqueda por fuerza bruta del recorrido de un caballo no es práctica en todos los tableros excepto en los más pequeños. [18] Por ejemplo, hay aproximadamente 4×10 51 secuencias de movimientos posibles en un tablero de 8 × 8 , [19] y está mucho más allá de la capacidad de las computadoras modernas (o redes de computadoras) realizar operaciones en un conjunto tan grande. . Sin embargo, el tamaño de este número no es indicativo de la dificultad del problema, que puede resolverse "mediante el uso de la perspicacia y el ingenio humanos... sin mucha dificultad". [18]
Al dividir el tablero en piezas más pequeñas, construir recorridos en cada pieza y unir las piezas, se pueden construir recorridos en la mayoría de los tableros rectangulares en tiempo lineal , es decir, en un tiempo proporcional al número de casillas del tablero. [11] [20]
La regla de Warnsdorf es una heurística para encontrar el recorrido de un solo caballo. El caballo se mueve de modo que siempre avance hacia la casilla desde la cual el caballo tendrá la menor cantidad de movimientos hacia adelante. Al calcular el número de movimientos posteriores para cada casilla candidata, no contamos los movimientos que vuelven a visitar alguna casilla ya visitada. Es posible tener dos o más opciones para las cuales el número de movimientos posteriores sea igual; Existen varios métodos para romper dichos vínculos, incluido uno ideado por Pohl [21] y otro por Squirrel y Cull. [22]
Esta regla también se puede aplicar de manera más general a cualquier gráfico. En términos de teoría de grafos, cada movimiento se realiza al vértice adyacente con el menor grado . [23] Aunque el problema de la ruta hamiltoniana es NP-difícil en general, en muchos gráficos que ocurren en la práctica esta heurística puede ubicar con éxito una solución en tiempo lineal . [21] La gira del caballero es un caso muy especial. [24]
La heurística fue descrita por primera vez en "Des Rösselsprungs einfachste und allgemeinste Lösung" de HC von Warnsdorf en 1823. [24]
Gordon Horsington escribió un programa de computadora que encuentra el recorrido de un caballo para cualquier posición inicial utilizando la regla de Warnsdorf y lo publicó en 1984 en el libro Century/Acorn User Book of Computer Puzzles . [25]
El problema del recorrido del caballero también se presta a ser resuelto mediante una implementación de red neuronal . [26] La red está configurada de manera que cada movimiento legal del caballero está representado por una neurona , y cada neurona se inicializa aleatoriamente para ser "activa" o "inactiva" (salida de 1 o 0), donde 1 implica que la neurona es parte de la solución. Cada neurona también tiene una función de estado (descrita a continuación) que se inicializa a 0.
Cuando se permite que la red se ejecute, cada neurona puede cambiar su estado y salida en función de los estados y salidas de sus vecinas (aquellas que están exactamente a un caballero de distancia) de acuerdo con las siguientes reglas de transición:
donde representa intervalos de tiempo discretos, es el estado de la neurona que conecta un cuadrado con un cuadrado , es la salida de la neurona desde hasta y es el conjunto de vecinos de la neurona.
Aunque son posibles casos divergentes, la red debería eventualmente converger, lo que ocurre cuando ninguna neurona cambia su estado de vez en cuando . Cuando la red converge, la red codifica un recorrido de caballero o una serie de dos o más circuitos independientes dentro del mismo tablero.
problema del recorrido del caballo es un problema clásico de optimización combinatoria. ... La cardinalidad N x de x (el tamaño del espacio de búsqueda) es superior a 3,3×10 13 (Löbbing y Wegener, 1995). No querríamos intentar resolver este problema usando la fuerza bruta, pero usando el conocimiento y el ingenio humanos podemos resolver el recorrido del caballero sin mucha dificultad. Vemos que la cardinalidad de un problema de optimización combinatoria no es necesariamente indicativa de su dificultad.
Medios relacionados con Knight's Tours en Wikimedia Commons
