El recorrido del caballo
Un recorrido del caballo es una serie de saltos de caballo que visita cada casilla de un tablero de ajedrez exactamente una vez. Es uno de los rompecabezas más antiguos de las matemáticas recreativas: un recorrido sobre medio tablero aparece en un poema indio del siglo IX, y Leonhard Euler estudió el rompecabezas en 1759.
Un rompecabezas antiguo
En el Kavyalankara, escrito por el poeta indio Rudrata en el siglo IX, un verso está dispuesto sobre medio tablero de ajedrez de modo que puede leerse siguiendo el camino de un caballo. Leonhard Euler escribió el primer estudio matemático del recorrido del caballo en 1759, con formas de construir recorridos y de convertirlos en cerrados.
Un camino a través de un grafo
Imagina cada casilla como un punto y cada salto de caballo como una línea entre dos puntos. Un recorrido del caballo es entonces un camino que visita cada punto exactamente una vez, lo que los matemáticos llaman un camino hamiltoniano; un recorrido cerrado es un ciclo hamiltoniano. En la mayoría de las redes es muy difícil encontrar un camino así. La red del caballo es generosa: tiene tantos recorridos que una buena regla encuentra uno enseguida.
La regla de Warnsdorff
H. C. von Warnsdorff describió su regla en 1823: saltar siempre a la casilla que deja menos movimientos siguientes. Las casillas del borde tienen pocas vecinas, así que la regla las visita pronto en lugar de dejarlas aisladas. Cuando dos casillas empatan hay que elegir, y una mala elección todavía puede dejar atascado al caballo. En la app, los números dorados marcan las casillas que elegiría la regla.
Búsqueda con vuelta atrás
Resolver sigue el orden de Warnsdorff, pero no se fía de él a ciegas. Busca en profundidad y, en cuanto una casilla sin visitar ya no se puede alcanzar, abandona esa rama y prueba el siguiente movimiento. En tableros de hasta 10×10 suele encontrar un recorrido al instante. Cuando tu propio camino ha encerrado al caballo, primero retrocede unos cuantos movimientos.
Colores y recorridos cerrados
Cada salto de caballo cambia el color de la casilla. En un tablero de lado impar como el de 5×5 hay una casilla más del color de las esquinas que del otro, así que un recorrido debe empezar y terminar en el color de las esquinas. Ahí un recorrido cerrado es imposible, porque un circuito que alterna colores tiene tantas casillas de un color como del otro. En los tableros de lado par hay recorridos cerrados a partir de 6×6.
Pruébalo en PictorX
Abre Recorrido del caballo y haz clic en una casilla para empezar. Las casillas resaltadas son los saltos válidos, el número dorado es la elección de Warnsdorff y el tablero guarda el orden de tus movimientos. Tamaño ajusta el tablero de 5×5 a 10×10, «Recorrido cerrado» pide a Resolver un circuito y Deshacer retira cualquier movimiento. Guarda el trazado terminado como PNG.
Preguntas frecuentes
¿Quién fue el primero en estudiar el recorrido del caballo?
Los recorridos se conocían mucho antes de que alguien los estudiara matemáticamente. Leonhard Euler escribió el primer tratamiento matemático en 1759, y Warnsdorff dio su regla en 1823.
¿Hay un recorrido en todos los tableros?
Los tableros cuadrados a partir de 5×5 tienen recorridos abiertos, y los de lado par a partir de 6×6 también tienen recorridos cerrados. Los tableros de 2×2, 3×3 y 4×4 no tienen ningún recorrido.
¿Cuántos recorridos tiene un tablero de ajedrez?
Hay 26.534.728.821.064 recorridos cerrados si un recorrido y el mismo recorrido hecho al revés se cuentan por separado. El número de recorridos abiertos es de unos 19,6 mil billones.
¿PictorX sube algo?
No. El tablero se dibuja en un lienzo en tu navegador. Guardar descarga un PNG y Editar abre esa imagen en el editor de PictorX.
Herramientas relacionadas
Recorrido del caballo
Haz saltar un caballo de ajedrez a cada casilla del tablero exactamente una vez. Juega tú mismo con las pistas de Warnsdorff, o mira cómo Resolver termina un recorrido abierto o cerrado. Guarda el trazado como PNG.
Ocho reinas
Coloca ocho reinas en un tablero de ajedrez de modo que ninguna ataque a otra. Pruébalo tú mismo, mira cómo la búsqueda con vuelta atrás encuentra una solución paso a paso y recorre las 92 soluciones.
El problema de las ocho reinas
La historia y las matemáticas del problema de las ocho reinas: Max Bezzel y Gauss, las 92 soluciones en 12 familias, el problema de las n reinas y la vuelta atrás.
Torre de Hanói
Mueve una torre de discos entre tres varillas en tu navegador. Un disco cada vez, nunca uno grande sobre uno pequeño. La solución más corta son 2ⁿ − 1 movimientos.
Torre de Hanói
La Torre de Hanói: tres varillas, un disco cada vez y nunca uno grande sobre uno pequeño. La solución más corta son 2ⁿ−1 movimientos. Édouard Lucas presentó el rompecabezas en 1883.
Hormiga de Langton
Ejecuta la hormiga de Langton en tu navegador. Observa la simetría, el caos y la autopista de 104 pasos, y luego prueba reglas de varios colores, varias hormigas, una cuadrícula hexagonal y turmitas.
¿Listo para probarlo?
Abra PictorX en su navegador: no requiere instalación ni tarjeta de crédito para comenzar.
Probar el recorrido del caballo