gira de caballeros
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 de caballo desde la casilla inicial (para que pueda recorrer el tablero nuevamente de inmediato, siguiendo el mismo camino), el recorrido se cierra; 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 presenta a los estudiantes de informática . [3] Las variaciones del problema de la vuelta del caballo implican tableros de ajedrez de diferentes tamaños que los habituales de 8 × 8 , así como tableros irregulares (no rectangulares).
El problema del recorrido del caballo es un ejemplo del problema de la ruta hamiltoniana más general en la teoría de grafos . El problema de encontrar un recorrido de caballo cerrado es similarmente 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 primera referencia conocida al problema de la gira del caballero se remonta al siglo IX d.C. En Kavyalankara [5] (5.15) de Rudraṭa , una obra en sánscrito sobre poética, el patrón del recorrido de un caballero en una media tabla se ha presentado como una figura poética elaborada ( citra-alaṅkāra ) llamada turagapadabandha o 'disposición en los pasos de un caballo'. Un mismo verso en cuatro versos de ocho sílabas cada uno se puede leer de izquierda a derecha o siguiendo el camino del caballero en gira. Dado que los sistemas de escritura índicos utilizados para el sánscrito son silábicos, se puede pensar que cada sílaba representa un cuadrado en un tablero de ajedrez. El ejemplo de Rudrata es el siguiente:
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 Vaishnava Vedanta Desika durante el siglo XIV en su obra magna de 1.008 versos alabando las sandalias divinas de Srirangam del Señor Ranganatha , es decir, Paduka Sahasram (en el capítulo 30: Chitra Paddhati ) ha compuesto dos versos sánscritos consecutivos que contienen 32 letras cada uno ( en métrica Anushtubh ) donde el segundo verso se puede derivar del primer verso realizando el recorrido de Knight en un tablero de 4 × 8 , comenzando desde la esquina superior izquierda. [6] El verso 19 transliterado es el siguiente:
| a | B | C | D | mi | F | gramo | h | ||
| 8 |       | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | B | C | D | mi | F | gramo | h | ||
