stringtranslate.com

Gira del caballero

Un recorrido abierto del caballo por un tablero de ajedrez
Una animación del recorrido de un caballo abierto en un tablero de 5 × 5

El recorrido de un caballo es una secuencia de movimientos de un caballo en un tablero de ajedrez de manera 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 nuevamente de inmediato, siguiendo el mismo camino), el recorrido está cerrado (o reentrante); de lo contrario, está abierto. [1] [2]

El problema del recorrido del caballo es el problema matemático de encontrar el recorrido de un caballo. Crear un programa para encontrar el recorrido de un caballo es un problema común que se les da 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 8 × 8 , así como tableros irregulares (no rectangulares).

Teoría

Gráfico del caballo que muestra todos los caminos posibles para el recorrido de un caballo en un tablero de ajedrez estándar de 8 × 8. Los números en cada nodo indican la cantidad de movimientos posibles que se pueden realizar desde esa posición.

El problema del recorrido del caballo es una instancia del problema de la trayectoria hamiltoniana más general en la teoría de grafos . El problema de encontrar un recorrido del caballo cerrado es de manera similar una instancia 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]

Historia

El recorrido del caballo resuelto por el turco , un engaño de las máquinas de ajedrez. Esta solución en particular es cerrada (circular) y, por lo tanto, puede completarse desde cualquier punto del tablero.

La primera referencia conocida al problema de la vuelta del caballo se remonta al siglo IX d. C. En el Kavyalankara [5] (5.15) de Rudrata , una obra sánscrita sobre poética, el patrón de la vuelta de un caballo sobre un medio tablero se ha presentado como una elaborada figura poética ( citra-alaṅkāra ) llamada turagapadabandha o 'disposición en los pasos de un caballo'. El mismo verso en cuatro líneas de ocho sílabas cada una se puede leer de izquierda a derecha o siguiendo el camino del caballo en la vuelta. Dado que los sistemas de escritura índicos utilizados para el sánscrito son silábicos, cada sílaba puede considerarse como la representación de un cuadrado en un tablero de ajedrez. El ejemplo de Rudrata es el siguiente:

transcrito:

Por ejemplo, la primera línea se puede leer de izquierda a derecha o pasando del primer recuadro 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 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 uno (en métrica Anushtubh ) donde el segundo verso puede derivarse del primer verso realizando un recorrido de Caballo en un tablero de 4 × 8 , comenzando desde la esquina superior izquierda. [6] El verso 19 transcrito es el siguiente:

El verso 20 que se puede obtener al realizar el recorrido del Caballero en el verso anterior es el siguiente:

sEsto es lo que yo quiero

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]

En el quinto libro de Bhagavantabaskaraby, escrito por Bhat Nilakantha, una obra ciclopédica en sánscrito sobre rituales, leyes y política, escrita alrededor de 1600 o 1700, se describen tres recorridos de caballeros. Los recorridos no solo son reentrantes sino también simétricos, y los versos se basan en el mismo recorrido, comenzando desde diferentes cuadrados. [8] La obra de Nilakantha es un logro extraordinario al ser un recorrido cerrado completamente simétrico, anterior al trabajo de Euler (1759) por al menos 60 años.

Un cuadrado semimágico (sus diagonales no suman su constante mágica , 260) que también forma un recorrido de caballo; no existen recorridos completamente mágicos en un tablero de 8x8 (aunque sí existen en tableros más grandes) [9]

Después de Nilakantha, uno de los primeros matemáticos que investigó 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 HC von Warnsdorf.

En el siglo XX, el grupo de escritores Oulipo lo utilizó, entre muchos otros. El ejemplo más notable es la vuelta del caballo 10 × 10 que marca el orden de los capítulos de la novela La vida, manual de instrucciones 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 utilizó ambos caballos); los comentaristas en línea bromearon diciendo que Anand estaba tratando de resolver el problema del recorrido del caballo durante la partida.

Existencia

Un recorrido de caballo cerrado y simétrico radialmente

Schwenk [10] demostró que para cualquier tablero m × n con mn , un recorrido de caballo cerrado siempre es posible a menos que se cumplan 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 o 8.

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

  1. m = 1 o 2
  2. m = 3 y n = 3, 5 o 6 [12]
  3. m = 4 y n = 4. [13]

Número de tours

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 ). [14] [15] [16] 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. [17]

Encontrar tours con computadoras

Existen 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 .

Algoritmos de fuerza bruta

Una búsqueda por fuerza bruta de la vuelta de un caballo es poco práctica en todos los tableros, excepto en los más pequeños. [18] En un tablero de 8 × 8 , por ejemplo, hay13 267 364 410 532 recorridos de caballos, [14] y un número mucho mayor de secuencias de movimientos de caballos de la misma longitud. Está muy por encima 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 "utilizando la perspicacia y el ingenio humanos... sin mucha dificultad". [18]

Algoritmos de divide y vencerás

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 cuadrados del tablero. [11] [19]

La regla de Warnsdorf

Representación gráfica de la regla de Warnsdorf. Cada casilla contiene un número entero que indica el número de movimientos que el caballo puede realizar desde esa casilla. En este caso, la regla nos indica que debemos movernos a la casilla que contenga el número entero más pequeño, es decir, 2.
Un recorrido de caballo abierto de cuadrados muy grandes (130 × 130) creado utilizando la regla de Warnsdorf

La regla de Warnsdorf es una heurística para encontrar el recorrido de un solo caballo. El caballo se mueve de manera que siempre avance hacia la casilla desde la que tendrá menos movimientos hacia adelante. Al calcular el número de movimientos hacia adelante 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 hacia adelante sea igual; existen varios métodos para romper tales empates, incluido uno ideado por Pohl [20] y otro por Squirrel y Cull. [21]

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 . [22] Aunque el problema de la trayectoria hamiltoniana es NP-hard en general, en muchos grafos que ocurren en la práctica esta heurística es capaz de localizar con éxito una solución en tiempo lineal . [20] El recorrido del caballo es un caso especial. [23]

La heurística fue descrita por primera vez en "Des Rösselsprungs einfachste und allgemeinste Lösung" de HC von Warnsdorf en 1823. [23]

Gordon Horsington escribió un programa informático 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 . [24]

Soluciones de redes neuronales

Recorrido cerrado del caballo en un tablero de 24 × 24 resuelto mediante una red neuronal

El problema del recorrido del caballo también se presta a ser resuelto mediante la implementación de una red neuronal . [25] La red está configurada de tal manera que cada movimiento legal del caballo está representado por una neurona , y cada neurona se inicializa aleatoriamente para que sea "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 funcione, 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 movimiento de caballo de distancia) de acuerdo con las siguientes reglas de transición:

donde representa intervalos discretos de tiempo, es el estado de la neurona que conecta el cuadrado con el cuadrado , es la salida de la neurona de a , 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 un tiempo a otro . Cuando la red converge, la red codifica un recorrido de caballo o una serie de dos o más circuitos independientes dentro del mismo tablero.

Véase también

Notas

  1. ^ Brown, Alfred James (2017). Giras de caballo y funciones zeta (tesis de maestría). Universidad Estatal de San José. p. 3. doi : 10.31979/etd.e7ra-46ny .
  2. ^ Hooper, David ; Whyld, Kenneth (1996) [Primera publicación 1992]. "El recorrido del caballero". The Oxford Companion to Chess (2.ª ed.). Oxford University Press . pág. 204. ISBN 0-19-280049-3.
  3. ^ Deitel, HM; Deitel, PJ (2003). Java Cómo programar quinta edición (5ª ed.). Prentice Hall . págs. 326–328. ISBN 978-0131016217.
  4. ^ ab Conrad, A.; Hindrichs, T.; Morsy, H. y Wegener, I. (1994). "Solución del problema de la trayectoria hamiltoniana del caballo en tableros de ajedrez". Matemáticas Aplicadas Discretas . 50 (2): 125–134. doi : 10.1016/0166-218X(92)00170-Q .
  5. ^ Satyadev, Chaudhary. Kavyalankara de Rudrata (texto en sánscrito, con traducción al hindi); . Delhitraversal: Serie Parimal Sánscrito No. 30.
  6. ^ "Instituto Indio de Tecnología de la Información, Bangalore". www.iiitb.ac.in . Consultado el 11 de octubre de 2019 .
  7. ^ Puente-india (5 de agosto de 2011). "Puente-India: Paduka Sahasram de Vedanta Desika". Puente-India . Consultado el 16 de octubre de 2019 .
  8. ^ Una historia del ajedrez por Murray
  9. ^ "Noticias de MathWorld: No hay vueltas mágicas en el tablero de ajedrez".
  10. ^ Allen J. Schwenk (1991). "¿Qué tableros de ajedrez rectangulares tienen un recorrido del caballo?" (PDF) . Revista de Matemáticas . 64 (5): 325–332. doi :10.1080/0025570X.1991.11977627. S2CID  28726833. Archivado desde el original (PDF) el 26 de mayo de 2019.
  11. ^ ab Cull, P.; De Curtins, J. (1978). "Knight's Tour Revisited" (PDF) . Fibonacci Quarterly . 16 : 276–285. Archivado (PDF) desde el original el 2022-10-09.
  12. ^ "Tours de caballeros en 3 por N Boards".
  13. ^ "Tours de caballeros en 4 por N Boards".
  14. ^ ab Löbbing, Martin; Wegener, Ingo (1996). "El número de vueltas del caballo es igual a 33.439.123.484.294, contando con diagramas de decisión binarios". Revista electrónica de combinatoria . 3 (1). Artículo de investigación 5. doi :10.37236/1229. MR  1368332.Consulte el comentario adjunto de Brendan McKay, 18 de febrero de 1997, para el recuento corregido.
  15. ^ Brendan McKay (1997). "Giros del caballo en un tablero de ajedrez de 8 × 8". Informe técnico TR-CS-97-03 . Departamento de Ciencias de la Computación, Universidad Nacional de Australia. Archivado desde el original el 28 de septiembre de 2013. Consultado el 22 de septiembre de 2013 .
  16. ^ Wegener, I. (2000). Programas de ramificación y diagramas de decisión binarios. Sociedad de Matemáticas Industriales y Aplicadas. ISBN 978-0-89871-458-6.
  17. ^ Weisstein, Eric W. "Gráfico de caballero". MathWorld .
  18. ^ ab Simon, Dan (2013), Algoritmos de optimización evolutiva, John Wiley & Sons, págs. 449–450, ISBN 9781118659502El 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 mayor que 3,3×10 13 (Löbbing y Wegener, 1995). No querríamos intentar resolver este problema usando la fuerza bruta, pero usando la perspicacia y el ingenio humanos podemos resolver el recorrido del caballo sin mucha dificultad. Vemos que la cardinalidad de un problema de optimización combinatoria no es necesariamente indicativa de su dificultad.
  19. ^ Parberry, Ian (1997). "Un algoritmo eficiente para el problema del recorrido del caballo" (PDF) . Matemáticas Aplicadas Discretas . 73 (3): 251–260. doi : 10.1016/S0166-218X(96)00010-8 . Archivado (PDF) desde el original el 2022-10-09.
  20. ^ ab Pohl, Ira (julio de 1967). "Un método para encontrar caminos de Hamilton y recorridos de Knight". Comunicaciones de la ACM . 10 (7): 446–449. CiteSeerX 10.1.1.412.8410 . doi :10.1145/363427.363463. S2CID  14100648. 
  21. ^ Squirrel, Douglas; Cull, P. (1996). "Un algoritmo de la regla de Warnsdorff para recorridos de caballos en tableros cuadrados" (PDF) . GitHub . Consultado el 21 de agosto de 2011 .
  22. ^ Van Horn, Gijs; Olij, Richard; Sleegers, Joeri; Van den Berg, Daan (2018). Un análisis predictivo de datos para la dificultad de las instancias del problema del ciclo hamiltoniano (PDF) . DATA ANALYTICS 2018: La séptima conferencia internacional sobre análisis de datos. Atenas, Grecia: XPS. pp. 91–96. ISBN 978-1-61208-681-1. Recuperado el 27 de noviembre de 2018 .
  23. ^ ab Alwan, Karla; Waters, K. (1992). Encontrar vueltas de caballo reentrantes en tableros N por M. Conferencia regional del sudeste de la ACM. Nueva York, Nueva York: ACM . págs. 377–382. doi :10.1145/503720.503806.
  24. ^ Dally, Simon, ed. (1984). Libro de acertijos informáticos para usuarios de Century/Acorn . Century Communications. ISBN 978-0712605410.
  25. ^ Y. Takefuji, KC Lee. "Computación en redes neuronales para problemas de la vuelta del caballo". Neurocomputing , 4(5):249–254, 1992.

Enlaces externos