Gira de caballeros

Una gira de caballero abierto de un tablero de ajedrez

Una animación de una gira de caballeros abiertos en un tablero de 5 × 5

El recorrido de un caballo es una secuencia de movimientos de un caballo en un tablero de ajedrez tal 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 de nuevo inmediatamente, siguiendo el mismo camino), el recorrido se cierra (o vuelve a entrar); de lo contrario, está abierto.

El problema del recorrido del caballero es el problema matemático de encontrar el recorrido del caballero. Crear un programa para encontrar el recorrido de un caballero es un problema común que se presenta a los estudiantes de informática. Las variaciones del problema de la vuelta del caballo implican tableros de ajedrez de diferentes tamaños que los habituales 8 × 8, así como tableros irregulares (no rectangulares).

Teoría

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

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.

Historia

El recorrido del caballero resuelto por el turco, una máquina de juego de ajedrez. Esta solución particular está cerrada (circular), por lo que puede completarse desde cualquier punto en el tablero.

La primera referencia conocida al problema del recorrido del caballero se remonta al siglo IX d.C. En Kavyalankara de Rudrata (5.15), una obra en sánscrito sobre poética, el patrón de un El recorrido del caballero en media pensión se ha presentado como una figura poética elaborada (citra-alaṅkāra) llamado 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:

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 Vaishnava Vedanta Desika durante el siglo XIV en su obra maestra de 1008 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 primero realizando un Caballero&# 39;s recorrido en un tablero de 4 × 8, comenzando desde la esquina superior izquierda. El verso 19 transliterado es el siguiente:

El verso 20 que se puede obtener al realizar 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 ran 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.

Un recorrido del que se informa en el quinto libro de Bhagavantabaskaraby de Bhat Nilakantha, una obra enciclopédica en sánscrito sobre rituales, leyes y política, escrita alrededor de 1600 o alrededor de 1700, describe tres recorridos de caballeros. Los recorridos no solo son reentrantes sino también simétricos, y los versos parten de un mismo recorrido partiendo de diferentes plazas. El trabajo 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.

Una plaza semimagica (sus diagonales no suman su constante mágica, 260) también formando una gira de caballero – no existen tours mágicos completos

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 caballero fue la regla de Warnsdorf, descrita por primera vez en 1823 por H. C. von Warnsdorf.

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

En la sexta partida del Campeonato Mundial de Ajedrez de 2010 entre Viswanathan Anand y Veselin Topalov, Anand hizo 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.

Existencia

Un recorrido radialmente simétrico del caballero cerrado

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

1. m y n ambos son raros
2. m = 1, 2, 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 más pequeña sea al menos 5, hay un caballo (posiblemente abierto)'s gira.

Número de recorridos

En un tablero 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 reflexiones). 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. Hay 9862 recorridos cerrados no dirigidos en un tablero de 6 × 6.

Buscar recorridos con computadoras

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ísticas.

Algoritmos de fuerza bruta

Una búsqueda de fuerza bruta para el recorrido de un caballo no es práctica en todos los tableros excepto en los más pequeños. Por ejemplo, hay aproximadamente 4 × 10⁵¹ secuencias de movimientos posibles en un tablero de 8 × 8, 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 perspicacia y el ingenio humanos... sin mucha dificultad".

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 a la cantidad de cuadrados en el tablero..

Regla de Warnersdorff

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Una representación gráfica de la Regla de Warnsdorff. Cada cuadrado contiene un entero dando el número de movimientos que el caballero podría hacer de esa plaza. En este caso, la regla nos dice que nos mudemos a la plaza con el más pequeño entero en ella, a saber 2.

Una gira muy grande (130 × 130) de caballero abierto cuadrado creado con la Regla de Warnsdorff

La regla de Warnersdorff es una heurística para encontrar el recorrido de un solo caballo. El caballo se mueve de modo que siempre proceda a la casilla desde la cual el caballo tendrá el menos movimiento hacia adelante. Al calcular el número de movimientos hacia adelante para cada cuadro candidato, no contamos los movimientos que vuelven a visitar ningún cuadro ya visitado. 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 esos lazos, incluido uno ideado por Pohl y otro por Squirrel y Cull.

Esta regla también puede aplicarse 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. Aunque el problema del camino hamiltoniano es NP-difícil en general, en muchos gráficos que ocurren en la práctica, esta heurística es capaz de ubicar con éxito una solución en tiempo lineal. La gira del caballero es un caso tan especial.

La heurística se describió por primera vez en "Des Rösselsprungs einfachste und allgemeinste Lösung" por HC von Warnsdorff en 1823.

Gordon Horsington escribió un programa de computadora que encuentra el recorrido de un caballo para cualquier posición inicial usando la regla de Warnsdorff y se publicó en 1984 en el libro Century/Acorn User Book of Computer Puzzles.

Soluciones de redes neuronales

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

El problema del recorrido del caballero también se presta a ser resuelto mediante la implementación de una red neuronal. La red está configurada de tal manera que cada movimiento legal del caballero está representado por una neurona, y cada neurona se inicializa aleatoriamente para que esté 'activa' o 'activa'. o "inactivo" (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 en 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 vecinos (aquellos que se alejan exactamente de un caballero) de acuerdo con las siguientes reglas de transición:

Ut+1()Ni,j)=Ut()Ni,j)+2− − .. N▪ ▪ G()Ni,j)Vt()N){displaystyle U_{t+1}(N_{i,j})=U_{t}(N_{i,j})+2-sum ¿Qué?

3\0&{mbox{if}},,U_{t+1}(N_{i,j})Vt+1()Ni,j)={}1siUt+1()Ni,j)■30siUt+1()Ni,j).0Vt()Ni,j)de otra manera,{displaystyle {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {f} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}

3\0&{mbox{if}},,U_{t+1}(N_{i,j})

Donde t{displaystyle t} representa intervalos discretos de tiempo, U()Ni,j){displaystyle U(N_{i,j})} es el estado de la neurona plaza de conexión i{displaystyle i} cuadrado j{displaystyle j}, V()Ni,j){displaystyle V(N_{i,j})} es la salida de la neurona de i{displaystyle i} a j{displaystyle j}, y G()Ni,j){displaystyle G(N_{i,j})} es el conjunto de vecinos de la neurona.

Aunque los casos divergentes son posibles, la red debe eventualmente converger, que ocurre cuando ninguna neurona cambia su estado a partir del tiempo t{displaystyle t} a t+1{displaystyle t+1}. Cuando la red converge, ya sea la red codifica el recorrido de un caballero o una serie de dos o más circuitos independientes dentro del mismo tablero.