PROFILPELAJAR.COM

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


Una de les rutes més llargues per n = 7 de longitud 24.	Una de les rutes més llargues per n = 8 de 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.