OFFSET
1,1
COMMENTS
An {r,s}-leaper graph is a chessboard-like graph, with two vertices adjacent when an {r,s}-leaper can leap from one to the other. When r=1 and s=2 we have an ordinary knight's move; in general, an {r,s}-leaper goes from (x,y) to (x +- r, y +- s) or to (x +- s, y +- r). The theory of these graphs is developed in the paper ``Leaper Graphs'', which discusses the values of a(1) through a(7) and gives a quadratic lower bound.
This problem turns out to be an excellent benchmark for the special case of TSP solvers where the intercity distances are just 0 and infinity.
The values of a(2) and a(3) are due to George Jelliss; I found a(4) and a(5); and Michael Juenger found a(6) and a(7).
LINKS
George Jelliss, Knight's Tour Notes [Added by N. J. A. Sloane, Oct 01 2009]
George Jelliss, Knight's Tours on 3 X 10 board [An illustration from the web page Knight's Tour Notes] [Added by N. J. A. Sloane, Oct 01 2009]
George Jelliss, Chronology of Knight's Tours [Added by N. J. A. Sloane, Oct 01 2009]
D. E. Knuth, Leaper Graphs, arXiv:math/9411240 [math.CO], 1994; The Mathematical Gazette, 78 (1994), 274-297. [To be reprinted in a 2010 book, Selected Papers on Fun and Games.]
Mario Velucchi, Knight's Tours [Added by N. J. A. Sloane, Oct 01 2009]
EXAMPLE
We have a(1)=10 because a 3 X 10 chessboard was shown to be Hamiltonian by Bergholt in 1918, while there clearly are no Hamiltonian cycles on a 3 X 8 or 3 X 6 or 3 X 4 or 3 X 2 or 3 X odd.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Don Knuth, Sep 30 2009, Jun 24 2010
STATUS
approved