El problema del movimiento del caballo

El problema del movimiento del caballo  es el problema de encontrar la ruta de un caballo de ajedrez pasando por todas las casillas del tablero una vez.

Este problema se conoce al menos desde el siglo XVIII . Leonhard Euler le dedicó una gran obra "La solución de una cuestión curiosa, que parece no ser objeto de ninguna investigación", fechada en 1759 [1] . En una carta a Goldbach [2] informó:

... El recuerdo de un problema que me fue propuesto una vez me sirvió recientemente como una ocasión para una investigación sutil, en la que el análisis ordinario, al parecer, no sirve de nada ... Finalmente encontré una manera clara de encontrar tantos soluciones a mi gusto (su número, sin embargo, no es infinito), sin hacer pruebas.

Planteamiento del problema

En términos de teoría de grafos, cada recorrido del caballo por todas las casillas del tablero corresponde a un camino hamiltoniano (o un ciclo si el recorrido es cerrado) en un grafo cuyos vértices son las casillas del tablero, y dos cuadrados están conectados por un borde si uno puede pasar de uno a otro en el movimiento de un caballo.

Para un tablero de 8 × 8, el número de todas las rutas de caballero cerradas (ciclos hamiltonianos) sin tener en cuenta la dirección del bypass es 13 267 364 410 532 [3] . El número de todas las rutas abiertas (teniendo en cuenta la dirección de circunvalación) es 19 591 828 170 979 904.

Métodos de solución

Método de Euler

El método de Euler es que primero el caballo se mueve a lo largo de una ruta arbitraria hasta agotar todos los movimientos posibles. Luego, las celdas restantes que no han sido pasadas se agregan a la ruta realizada, después de una permutación especial de sus elementos.

Considere la siguiente ruta como ejemplo:

55 58 29 40 27 44 19 22
60 39 56 43 treinta 21 26 45
57 54 59 28 41 Dieciocho 23 veinte
38 51 42 31 ocho 25 46 17
53 32 37 a 47 dieciséis 9 24
cincuenta 3 52 33 36 7 12 quince
una 34 5 48 b catorce C diez
cuatro 49 2 35 6 once d 13

Primero, intentemos hacer una ruta cerrada a partir de una ruta abierta. Para ello, considera a dónde puedes ir desde los campos 1 y 60. Desde el campo 1 puedes pasar a los campos 2, 32 y 52, y desde el 60 al 29, 51 y 59. En estos dos conjuntos hay campos que difieren en uno , a saber, - 51 y 52. ​​Gracias a esto, puede cerrar la ruta invirtiendo parte de ella. Para ello, renumera los campos del 52 al 60 en orden inverso. Después de eso, obtenemos una ruta cerrada:

57 54 29 40 27 44 19 22
52 39 56 43 treinta 21 26 45
55 58 53 28 41 Dieciocho 23 veinte
38 51 42 31 ocho 25 46 17
59 32 37 a 47 dieciséis 9 24
cincuenta 3 60 33 36 7 12 quince
una 34 5 48 b catorce C diez
cuatro 49 2 35 6 once d 13

Ahora puede incluir algunas de las celdas no recorridas en la ruta. Dado que nuestra ruta está cerrada, se puede romper en un lugar arbitrario y se puede unir una cadena adecuada de celdas no recorridas a uno de los extremos. Por ejemplo, si rompemos la cadena en la celda 51 (renumerando las celdas y haciéndola la última, y ​​la 52 primero), podemos extender nuestra cadena por las celdas a , b y d , que se convertirán en las celdas 61, 62 y 63.

Método de Vandermonde

Vandermonde trató de reducir el problema a la aritmética. Para hacer esto, denotó la ruta del caballo a lo largo del tablero como una secuencia de fracciones x / y , donde x e y  son las coordenadas del campo en el tablero. Evidentemente, en la secuencia de fracciones correspondientes a las jugadas del caballo, la diferencia entre los numeradores de dos fracciones vecinas sólo puede ser 1 o 2, a pesar de que la diferencia entre sus denominadores sea 2 o 1, respectivamente. el numerador y el denominador no pueden ser menor que 1 y mayor que 8 .

Su método para encontrar una secuencia adecuada es similar al método de Euler, pero solo permite encontrar los caminos del caballo para tableros de dimensiones pares.


Regla de Warnsdorf

La regla de Warnsdorf , que es una especie de algoritmo codicioso para encontrar la ruta del caballo, se formula de la siguiente manera:

Al dar la vuelta al tablero, el caballo sigue el campo desde el que es posible pasar al número mínimo de campos que aún no se han pasado. Si hay varios campos de este tipo, puede ir a cualquiera de ellos.

Durante mucho tiempo se creyó que la regla de Warnsdorff funciona perfectamente. Más tarde, con la ayuda de computadoras, se estableció una imprecisión en la segunda parte: si hay varios campos adecuados, entonces no todos son iguales, y la elección arbitraria de un campo puede llevar al caballo a un callejón sin salida. Sin embargo, en la práctica, la probabilidad de llegar a un callejón sin salida es pequeña incluso con el uso libre de la segunda parte de la regla de Warnsdorff. [cuatro]

Rutas destacadas

Ruta Janisch

cincuenta once 24 63 catorce 37 26 35
23 62 51 12 25 34 quince 38
diez 49 64 21 40 13 36 27
61 22 9 52 33 28 39 dieciséis
48 7 60 una veinte 41 54 29
59 cuatro 45 ocho 53 32 17 42
6 47 2 57 44 19 treinta 55
3 58 5 46 31 56 43 Dieciocho
Ruta Janish

La ruta del caballo, encontrada por K. A. Yanish , forma un cuadrado semimágico , y cuando se gira el tablero 180°, la primera mitad de la ruta (números del 1 al 32) pasa a la segunda (números del 33 al 64). ). El recorrido, que es un auténtico cuadrado mágico, no existe para el tablero 8×8 [5] .

Ruta del Turco

La máquina de ajedrez "Turk" demostró la ruta cerrada del caballo, que se muestra en el diagrama de la derecha.

Poema mnemotécnico

Puedes recorrer todas las casillas de ajedrez con el caballo una vez, además, puedes hacerlo “a ciegas”, comenzando o terminando en cualquier casilla a petición del “espectador”, puedes seguir el poema: [6]

enrojece el otoño con valiosos regalos,
Otro día que da vida.
Pan Rojos Cordones Amarillos,
Pabellón filosófico de Crystal Waters.

Dos tardes aferrándose capullos
Artista escribió, Bezdonna Sineva.
Gusanos de beso de escoria de carretera,
Todavía cubierto con Phlox Grass.

Fuma Té Eficaz Chocolate,
Tazas de porcelana obtener tres,
Chica rubia dana alegría
Forshmak Divide con un borde frío.

esposa empujando novia frágil
Quiere disparar este fin de semana
Apreciando la Ventisca Ártica Misma,
Lanza una Bola de Sandía a Cuatro.

Cicada Heel, apenas ventrílocuo,
Le da Sandman Window a Ficus.
Aunque los sedientos de té estén satisfechos,
El propietario dona ruidosamente vino.

foxtrot seis chicas cautivadas,
Los bailes variados son más fantásticos que Pa,
Apenas pisó pollo salió,
Y el draco errante se ha ido.

El cuerpo del álamo temblón se vuelve rojo,
Reigns Shadows Calado Largo.
Silencioso que los neumáticos de un coche
El viento del pantano da semillas.

Linterna Ocho Quimeras Brilla,
Beetle llega, aplaudiendo, allí.
Otoño deseable, si se completa
El descanso más valioso del trabajo alegre.

Las primeras letras establecen las coordenadas de los movimientos:

Aleet Otoño = A1; Regalos valiosos = C2; etc.

Se inserta una pista en cada estrofa para ayudar a no confundir la secuencia de estrofas: UNO más, DOS tardes, TRES lo consigue, etc.

Generalización a tableros arbitrarios

Rutas cerradas

El número de rutas cerradas, teniendo en cuenta la dirección, es el doble. Existen rutas cerradas en tableros para todos los pares (secuencia A001230 en OEIS ).

Rutas abiertas

Para tableros no cuadrados, existe un paseo de caballo no cerrado solo si se cumplen las siguientes condiciones: si un lado del tablero es 3, entonces el otro lado debe ser 4 o al menos 7; si ambos lados son mayores que 3, entonces el caballo se puede pasar por alto en todos los tableros excepto 4 × 4. En particular, existen rutas no cerradas en tableros cuadrados para todos . [7] El número de caminos abiertos en los tableros forman la secuencia A165134 en OEIS .

Véase también

Notas

  1. ↑ Euler, Leonhard, Solution d'une question curieuse que ne paroit soumise à aucune analyse Archivado el 30 de septiembre de 2017 en Wayback Machine , Mémoires de l'académie des sciences de Berlin, 15 (1759) 1766, p. 310-337.
  2. ↑ How Euler Did It Archivado el 8 de agosto de 2017 en Wayback Machine .
  3. ↑ Brendan McKay. Giros del Caballo sobre un Tablero de Ajedrez 8x8  (indefinido)  // Informe Técnico TR-CS-97-03. — Departamento de Ciencias de la Computación, Universidad Nacional de Australia, 1997. Archivado desde el original el 28 de septiembre de 2013.
  4. ↑ E. Friki. Capítulo 2. Caballo Camaleón // Ajedrez y Matemáticas . - M. : Nauka, 1983. - (Biblioteca "Quantum").
  5. ↑ Eric W. Weisstein, There Are No Magic Knight's Tours on the Chessboard Archivado el 8 de septiembre de 2017 en Wayback Machine , MathWorld Headline News.
  6. ↑ V. Panov. El secreto de un truco  // Ciencia y Vida . - 1969. - Nº 5 .
  7. ↑ A. Conrad, T. Hindrichs, H. Morsy, I. Wegener. Solución del problema del camino hamiltoniano del caballo en tableros de ajedrez   // Discr . aplicación Matemáticas. : diario. - 1994. - vol. 50 . - P. 125-134 . - doi : 10.1016/0166-218X(92)00170-Q .

Enlaces