El camino del caballero más largo sin cruzar

El problema matemático de encontrar el camino más largo sin cruzar (o sin intersecarse) para un caballo se plantea en un tablero de ajedrez estándar de 8×8 o, de forma más general, en un tablero cuadrado de n×n. El objetivo es hallar el camino más largo que el caballo puede recorrer en el tablero dado , de manera que dicho camino no se cruce consigo mismo. Cabe destacar que se trata de un camino cerrado , que termina en la misma casilla donde comienza, y un camino abierto , que termina en una casilla diferente.

Los caminos abiertos más largos en un tablero de n × n se conocen solo para n ≤ 9. Sus longitudes para n = 1, 2, ..., 9 son:

0, 0, 2, 5, 10, 17, 24, 35, 47 (secuencia A003192 en el OEIS )

Los caminos cerrados más largos se conocen solo para n ≤ 10. Sus longitudes para n = 1, 2, ..., 10 son:

0, 0, 0, 4, 8, 12, 24, 32, 42, 54 (secuencia A157416 en el OEIS )

El problema puede generalizarse aún más a tableros rectangulares de m × n , o incluso a tableros con la forma de cualquier poliomino . Una forma restringida del problema para tableros de m × n , donde n ≤ 8 y m puede ser muy grande, se presentó en las Finales Mundiales de ICPC de 2018. ^{[ 1 ]} Puede resolverse mediante programación dinámica, aprovechando la idea de que la solución debe exhibir un comportamiento cíclico.

Otras piezas de ajedrez estándar que no sean el caballo son menos interesantes, pero las piezas de ajedrez de fantasía como el camello ((3,1)-saltador), la jirafa ((4,1)-saltador) y la cebra ((3,2)-saltador) dan lugar a problemas de complejidad comparable.

• Un recorrido del caballo es un camino que el caballo recorre todas las casillas del tablero, intersecándose consigo mismo.
• TwixT , un juego de mesa basado en los caminos de caballeros que no se cruzan.

• LD Yarbrough (1968). "Recorridos del caballero sin cruzar". Journal of Recreational Mathematics . 1 (3): 140– 142.
• George Jelliss, Caminos que no se cruzan
• Recorridos de caballeros sin cruces
• Soluciones de la final mundial de la ICPC 2018 (Problema J)

• Recorridos de caballeros sin cruzar