Knight's Tour

$\begin{figure}\begin{center}\BoxedEPSF{KnightsTour6.epsf}\end{center}\end{figure}$

$\begin{figure}\begin{center}\BoxedEPSF{KnightsTours.epsf scaled 700}\end{center}\end{figure}$

A knight's tour of a Chessboard (or any other grid) is a sequence of moves by a knight Chess piece (which may only make moves which simultaneously shift one square along one axis and two along the other) such that each square of the board is visited exactly once (i.e., a Hamiltonian Circuit). If the final position is a knight's move away from the first position, the tour is called re-entrant. The first figure above shows a knight's tour on a $6\times 6$ Chessboard. The second set of figures shows six knight's tours on an $8\times 8$ Chessboard, all but the first of which are re-entrant. The final tour has the additional property that it is a Semimagic Square with row and column sums of 260 and main diagonal sums of 348 and 168.

Löbbing and Wegener (1996) computed the number of cycles covering the directed knight's graph for an $8\times 8$ Chessboard. They obtained $\alpha^2$ , where $\alpha=2,849,759,680$ , i.e., 8,121,130,233,753,702,400. They also computed the number of undirected tours, obtaining an incorrect answer 33,439,123,484,294 (which is not divisible by 4 as it must be), and so are currently redoing the calculation.

The following results are given by Kraitchik (1942). The number of possible tours on a $4k\times 4k$ board for , 4, ... are 8, 0, 82, 744, 6378, 31088, 189688, 1213112, ... (Kraitchik 1942, p. 263). There are 14 tours on the $3\times 7$ rectangle, two of which are symmetrical. There are 376 tours on the $3\times 8$ rectangle, none of which is closed. There are 16 symmetric tours on the $3\times 9$ rectangle and 8 closed tours on the $3\times 10$ rectangle. There are 58 symmetric tours on the $3\times 11$ rectangle and 28 closed tours on the $3\times 12$ rectangle. There are five doubly symmetric tours on the $6\times 6$ square. There are 1728 tours on the $5\times 5$ square, 8 of which are symmetric. The longest ``uncrossed'' knight's tours on an $n\times n$ board for , 4, ... are 2, 5, 10, 17, 24, 35, ... (Sloane's A003192).

References

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 175-186, 1987.

Chartrand, G. ``The Knight's Tour.'' §6.2 in Introductory Graph Theory. New York: Dover, pp. 133-135, 1985.

Gardner, M. ``Knights of the Square Table.'' Ch. 14 in Mathematical Magic Show: More Puzzles, Games, Diversions, Illusions and Other Mathematical Sleight-of-Mind from Scientific American. New York: Vintage, pp. 188-202, 1978.

Guy, R. K. ``The Queens Problem.'' §C18 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 133-135, 1994.

Kraitchik, M. ``The Problem of the Knights.'' Ch. 11 in Mathematical Recreations. New York: W. W. Norton, pp. 257-266, 1942.

Madachy, J. S. Madachy's Mathematical Recreations. New York: Dover, pp. 87-89, 1979.

Ruskey, F. ``Information on the Knight's Tour Problem.'' http://sue.csc.uvic.ca/~cos/inf/misc/Knight.html.

Sloane, N. J. A. Sequences A003192/M1369 and A006075/M3224 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

van der Linde, A. Geschichte und Literatur des Schachspiels, Vol. 2. Berlin, pp. 101-111, 1874.

Volpicelli, P. ``Soluzione completa e generale, mediante la geometria di situazione, del problema relativo alle corse del cavallo sopra qualunque scacchiere.'' Atti della Reale Accad. dei Lincei 25, 87-162, 1872.

Wegener, I. and Löbbing, M. ``The Number of Knight's Tours Equals 33,439,123,484,294--Counting with Binary Decision Diagrams.'' Electronic J. Combinatorics 3, R5 1-4, 1996. http://www.combinatorics.org/Volume_3/volume3.html#R5.