La ruta de cavall més llarga sense creuaments és un problema d'escacs i matemàtica al qual hi intervé un cavall d'escacs en un escaquer estàndard de 8×8 caselles, o, més generalment, en un tauler de n×n catelles. El problema mira de trobar la ruta més llarga que el cavall pugui fer en el tauler donat, de tal manera que no es creui a ella mateixa. També es pot distingir entre una ruta tancada, que acaba a la mateixa casella on va començar, i una ruta oberta, que acaba en una casella diferent d'aquella en què va començar.
Solucions conegudes Les rutes obertes més llargues es coneixen només per un valor de n ≤ 9. Les seves longituds per n = 1, 2, …, 9 són: 0, 0, 2, 5, 10, 17, 24, 35, 47 seqüència A003192 a l'OEIS
Les rutes tancades més llargues es coneixen només per un valor de n ≤ 10. Les seves longituds per n = 1, 2, …, 10 són: 0, 0, 0, 4, 8, 12, 24, 32, 42, 54 seqüència A157416 a l'OEIS
210px|Ruta per n=7 de longitud 24 240px|Ruta per n=8 de longitud 35 Una de les rutes més llargues per n = 7de longitud 24. Una de les rutes més llargues per n = 8de longitud 35.
Generalitzacions El problema es pot generalitzar per a taulers de n×m caselles, o fins i tot per a taulers de l'estil de qualsevol poliòmino. D'altres peces d'escacs estàndard són menys interessants, però algunes peces d'escacs màgics com el camell ((3,1)-de salt), la girafa ((4,1)-de salt) i la zebra ((3,2)-de salt) produeixen problemes de complexitat semblant.
Vegeu també El problema de la ruta del cavall, un recorregut de cavall visitant totes les caselles de l'escaquer. TwixT, un joc de tauler basat en recorreguts de cavall que no es creuen.
Bibliografia
Enllaços externs George Jelliss, Non-Intersecting Paths Rutes de cavall que no es creuen a euler.free.fr Rutes de cavall que no es creuen a ukt.alex-black.ru
Categoria:Problemes d'escacs i matemàtica