Problema de la ruta de cavall més llarga sense creuaments

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.

Bibliografia

• L. D. Yarbrough «Uncrossed knight's tours». Journal of Recreational Mathematics, 1, 3, 1969, pàg. 140–142.

Enllaços externs

• George Jelliss, Non-Intersecting Paths Arxivat 2012-03-24 a Wayback Machine.
• Rutes de cavall que no es creuen a euler.free.fr
• Rutes de cavall que no es creuen Arxivat 2013-07-31 a Wayback Machine. a ukt.alex-black.ru