El camino de caballo más largo sin cruzar (o sin intersección ) es un problema matemático que involucra un caballo en el tablero de ajedrez estándar de 8 × 8 o, más generalmente, en un tablero cuadrado de n × n . El problema es encontrar el camino más largo que el caballero puede tomar en el tablero dado, de manera que el camino no se cruce. Se puede hacer una distinción adicional entre un camino cerrado , que termina en el mismo campo donde comienza, y un camino abierto , que termina en un campo diferente de donde comienza.
Los caminos abiertos más largos en un tablero n × n se conocen solo para n ≤ 9. Sus longitudes para n = 1, 2,…, 9 son:
Los caminos cerrados más largos se conocen sólo para n ≤ 10. Sus longitudes para n = 1, 2,…, 10 son:
El problema se puede generalizar aún más a tableros rectangulares de n × m , o incluso a tableros con la forma de cualquier poliominó . El problema para tableros n × m , donde n no supera 8 y m puede ser muy grande, se planteó en las Finales Mundiales del ICPC de 2018. La solución utilizó programación dinámica y aprovecha el hecho de que la solución debe exhibir un comportamiento cíclico.
Otras piezas de ajedrez estándar además del caballo son menos interesantes, pero piezas de ajedrez mágicas como el camello ((3,1)-saltador), la jirafa ((4,1)-saltador) y la cebra ((3,2)-saltador) lideran a problemas de complejidad comparable.