Tour de caballeros

El recorrido de un caballero abierto por un tablero de ajedrez.

Una animación de la gira de un caballero abierto en un tablero de 5 × 5.

Un problema del caballo es una secuencia de movimientos de un caballero en un tablero de ajedrez de tal manera que las visitas caballero todas las plazas exactamente una vez. Si el caballo termina en una casilla que es el movimiento de un caballo desde la casilla inicial (para que pueda recorrer el tablero de nuevo inmediatamente, siguiendo el mismo camino), el recorrido se cierra; de lo contrario, está abierto. ^{[1] [2]}

El problema del recorrido del caballero es el problema matemático de encontrar el recorrido de un caballero. La creación de un programa para encontrar el recorrido de un caballero es un problema común que se les da a los estudiantes de ciencias de la computación . ^[3] Las variaciones del problema del recorrido del caballo involucran tableros de ajedrez de diferentes tamaños que los habituales 8 × 8 , así como tableros irregulares (no rectangulares).

Teoría

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

El problema del recorrido del caballero es un ejemplo del problema de la trayectoria hamiltoniana más general en la teoría de grafos . El problema de encontrar un recorrido cerrado de caballeros 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]

Historia

La gira del caballero resuelta por el turco , un engaño de una máquina de jugar al ajedrez. Esta solución particular es cerrada (circular), por lo que se puede completar desde cualquier punto del tablero.

La primera referencia conocida al problema de la gira del caballero se remonta al siglo IX d.C. En Kavyalankara de Rudraṭa ^[5] (5.15), una obra en sánscrito sobre poética, el patrón de la gira de un caballero en media pensión se ha presentado como una elaborada figura poética ( citra-alaṅkāra ) llamada turagapadabandha o 'arreglo 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 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:

से	ना	ली	ली	ली	ना	ना	ली
ली	ना	ना	ना	ना	ली	ली	ली
न	ली	ना	ली	ले	ना	ली	ना
ली	ली	ली	ना	ना	ना	ना	ली

transcrito:

se	n / A	lī	lī	lī	n / A	n / A	lī
lī	n / A	n / A	n / A	n / A	lī	lī	lī
n / A	lī	n / A	lī	le	n / A	lī	n / A
lī	lī	lī	n / A	n / A	n / A	n / A	lī

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 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 el metro de 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 versículo 19 transcrito es el siguiente:

sThi (1)	real academia de bellas artes (30)	Georgia (9)	sAm (20)	sa (3)	dhA (24)	real academia de bellas artes (11)	dhyA (26)
vi (dieciséis)	decir ah (19)	THA (2)	ka (29)	eso (10)	THA (27)	mamá (4)	THA (23)
sa (31)	thpA (8)	dhu (17)	kE (14)	sa (21)	real academia de bellas artes (6)	sa (25)	mamá (12)
corrió (18)	Georgia (15)	real academia de bellas artes (32)	ja (7)	Pensilvania (28)	dha (13)	nna (22)	ya (5)

El vigésimo verso que se puede obtener realizando la gira 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 corrió ha sAm sa nna thA dhA

sA dhyA thA pa ka rA sa rA ||

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

Una gira reportada en el quinto libro de Bhagavantabaskaraby por Bhat Nilakantha, una obra ciclopédica en sánscrito sobre ritual, ley y política, escrita alrededor de 1600 o alrededor de 1700 describe las giras de tres caballeros. Los recorridos no solo son reentrantes sino también simétricos, y los versos se basan en el mismo recorrido, partiendo de diferentes plazas. ^[8] El trabajo de Bhat Nilakantha es un logro extraordinario al ser un recorrido cerrado completamente simétrico, anterior al trabajo de Euler (1759) en al menos 60 años.

Uno de los primeros matemáticos en investigar la gira del caballero fue Leonhard Euler . El primer procedimiento para completar la gira de los caballeros fue la regla de Warnsdorff, descrita por primera vez en 1823 por HC von Warnsdorff.

En el siglo XX lo utilizó el grupo de escritores Oulipo , entre muchos otros. El ejemplo más notable es la gira del caballero 10 × 10 que establece el orden de los capítulos de la novela Life a User's Manual de Georges Perec .

La sexta partida del Campeonato Mundial de Ajedrez 2010 entre Viswanathan Anand y Veselin Topalov vio a Anand haciendo 13 movimientos de caballo consecutivos (aunque usando ambos caballos); Los comentaristas en línea bromearon diciendo que Anand estaba tratando de resolver el problema de la gira del caballero durante el juego.

Existencia

Un recorrido de caballero cerrado radialmente simétrico

Schwenk ^[9] demostró que para cualquier tablero m × n con m ≤ n , siempre es posible un recorrido cerrado 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 yn = 4, 6 u 8.

Cull y col. y Conrad et al. demostró que en cualquier tablero rectangular cuya dimensión más pequeña sea al menos 5, hay un recorrido de caballero (posiblemente abierto). ^{[4] [10]}

Numero de recorridos

En una placa 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 los giros y los reflejos ). ^{[11] [12] [13]} El número de recorridos cerrados no dirigidos es la mitad de este número, ya que cada recorrido se puede rastrear al revés. Hay 9,862 recorridos cerrados no dirigidos en un tablero 6 × 6 . ^[14]

norte	Número de recorridos dirigidos (abiertos y cerrados) en un tablero n × n (secuencia A165134 en la OEIS )
1	1
2	0
3	0
4	0
5	1,728
6	6,637,920
7	165,575,218,320
8	19,591,828,170,979,904

Encontrar recorridos con computadoras

Hay varias formas de encontrar el recorrido de un caballero 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 de fuerza bruta para el recorrido de un caballero no es práctica en todos los tableros excepto en los más pequeños. ^[15] Por ejemplo, hay aproximadamente 4 × 10 ⁵¹ posibles secuencias de movimiento en una placa de 8 × 8 , ^[16] y está mucho más allá de la capacidad de las computadoras modernas (o redes de computadoras) para 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 intuición y el ingenio humanos ... sin mucha dificultad". ^[15]

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. ^{[10] [17]}

Regla de Warnsdorff

	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

Una representación gráfica de la regla de Warnsdorff. Cada casilla contiene un número entero que indica el número de movimientos que el caballo podría realizar desde esa casilla. En este caso, la regla nos dice que nos movamos al cuadrado con el número entero más pequeño, es decir, 2.

Un recorrido de caballero cuadrado abierto muy grande (130 × 130) creado usando la Regla de Warnsdorff

La regla de Warnsdorff es una heurística para encontrar el recorrido de un solo caballero. El caballo se mueve de manera que siempre proceda a la casilla desde la cual el caballo tendrá la menor cantidad de movimientos hacia adelante. Al calcular el número de movimientos hacia adelante para cada casilla candidata, no contamos los movimientos que vuelven a visitar cualquier casilla ya visitada. Es posible tener dos o más opciones para las cuales el número de movimientos hacia adelante es igual; Hay varios métodos para romper esos lazos, incluido uno ideado por Pohl ^[18] y otro por Squirrel y Cull. ^[19]

Esta regla también se puede aplicar de manera más general a cualquier gráfico. En términos de la teoría de los gráficos, cada movimiento se realiza al vértice adyacente con el menor grado . ^[20] 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 es capaz de localizar con éxito una solución en tiempo lineal . ^[18] La gira del caballero es un caso tan especial. ^[21]

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

Gordon Horsington escribió un programa de computadora que encuentra el recorrido de un caballero para cualquier posición inicial utilizando la regla de Warnsdorff y lo publicó en 1984 en el libro Century / Acorn User Book of Computer Puzzles . ^[22]

Soluciones de redes neuronales

Tour de caballero cerrado en un tablero 24 × 24 resuelto por una red neuronal

El problema de la gira del caballero también se presta a ser resuelto mediante una implementación de red neuronal . ^[23] La red está configurada de manera que cada movimiento de caballero legal está representado por una neurona , y cada neurona se inicializa aleatoriamente para ser "activa" o "inactiva" (salida de 1 o 0), con 1 implicando 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 en 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 vecinos (aquellos que se alejan exactamente de un caballo) de acuerdo con 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{if}}\,\,U_{t+1}(N_{i,j})>3\\0&{\mbox{if}}\,\,U_{t+1}(N_{i,j})<0\\V_{t}(N_{i,j})&{\mbox{otherwise}},\end{array}}\right.}$

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

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

Ver también

• Abu Bakr bin Yahya al-Suli
• George Koltanowski
• El camino del caballero más largo sin cruzar
• Rompecabezas de las ocho reinas
• Caminar para evitar uno mismo

Notas

1. Brown, Alfred James (2017). "Recorridos de Knight y funciones Zeta" (PDF). Universidad Estatal de San José. pag. 3. Consultado el 13 de abril de 2019.
2. Hooper, David ; Whyld, Kenneth (1996) [Primera publicación. 1992]. "gira del caballero". The Oxford Companion to Chess (2ª ed.). Prensa de la Universidad de Oxford . pag. 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. Conrad, A .; Hindrichs, T .; Morsy, H. y Wegener, I. (1994). "Solución del problema de la ruta hamiltoniana del caballero 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 sánscrito, con traducción al hindi); . Delhitraversal: Serie sánscrita parimal 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. Bridge-India (5 de agosto de 2011). "Puente-India: Paduka Sahasram por Vedanta Desika" . Puente-India . Consultado el 16 de octubre de 2019 .
8. Una historia del ajedrez por Murray
9. Allen J. Schwenk (1991). "¿Qué tableros de ajedrez rectangulares tienen un recorrido de caballero?" (PDF) . Revista de matemáticas : 325–332. Archivado desde el original (PDF) el 26 de mayo de 2019.
10. Cull, P .; De Curtins, J. (1978). "Tour del caballero revisitado" (PDF) . Fibonacci Quarterly . 16 : 276-285.
11. Martin Loebbing; Ingo Wegener (1996). "El número de giras de Knight es igual a 33,439,123,484,294 - contando con diagramas de decisión binarios" . La Revista Electrónica de Combinatoria . 3 (1): R5. doi : 10.37236 / 1229 . Observación: Los autores admitieron más tarde que el número anunciado es incorrecto. Según el informe de McKay, el número correcto es 13.267.364.410.532 y este número se repite en el libro de Wegener de 2000.
12. Brendan McKay (1997). "Tours de caballeros 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 .
13. 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.
14. Weisstein, Eric W. "Gráfico de caballero" . MathWorld .
15. Simon, Dan (2013), Algoritmos de optimización evolutiva , John Wiley & Sons, págs. 449–450, ISBN 9781118659502, El 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 ¹³ (Löbbing y Wegener, 1995). No quisiéramos 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 indicativo de su dificultad.
16. "Enumeración de la gira del caballero" .^{[ enlace muerto ]}
17. Parberry, Ian (1997). "Un algoritmo eficiente para el problema de la gira del caballero" (PDF) . Matemáticas aplicadas discretas . 73 (3): 251–260. doi : 10.1016 / S0166-218X (96) 00010-8 .
18. 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 . 
19. Ardilla, Douglas; Cull, P. (1996). "Un algoritmo de reglas de Warnsdorff para recorridos de caballeros en tableros cuadrados" (PDF) . Consultado el 21 de agosto de 2011 .
20. Van Horn, Gijs; Olij, Richard; Sleegers, Joeri; Van den Berg, Daan (2018). Un análisis de datos predictivos para la dureza de los casos de problemas de ciclo hamiltoniano (PDF) . DATA ANALYTICS 2018: La Séptima Conferencia Internacional sobre Análisis de Datos. Atenas, grecia: XPS . págs. 91–96. ISBN  978-1-61208-681-1. Consultado el 27 de noviembre de 2018 .^{[ enlace muerto permanente ]}
21. Alwan, Karla; Waters, K. (1992). Encontrar recorridos de caballeros reentrantes en tableros N-by-M . Conferencia Regional Sureste de ACM. Nueva York, Nueva York: ACM . págs. 377–382. doi : 10.1145 / 503720.503806 .
22. Dally, Simon, ed. (1984). Century / Acorn User Book of Computer Puzzles . ISBN 978-0712605410.
23. Y. Takefuji, KC Lee. "Computación de redes neuronales para problemas de gira de caballeros". Neurocomputing , 4 (5): 249-254, 1992.

enlaces externos

Wikimedia Commons tiene medios relacionados con Knight's Tours .

• Secuencia OEIS A001230 (Número de vueltas de caballero cerradas no dirigidas en un tablero de ajedrez 2n X 2n)
• HC von Warnsdorf 1823 en Google Books
• Introducción a las giras de Knight por George Jelliss
• Knight's tours notas completas de George Jelliss
• Philip, Anish (2013). "Algoritmo de recorrido de un pseudo-caballero generalizado para el cifrado de una imagen". Potenciales IEEE . 32 (6): 10–16. doi : 10.1109 / MPOT.2012.2219651 .