Knight Graph

The  knight graph is a graph on  vertices in which each vertex represents a square in an  chessboard, and each edge corresponds to a legal move by a knight (which may only make moves which simultaneously shift one square along one axis and two along the other). It is therefore a -leaper graph.

The  knight graph consists of an 8-cycle together with an (unreachable from all of the other squares) isolated central vertex.

The number of edges in the  knight graph is  (8 times the triangular numbers), so for , 2, ..., the first few values are 0, 0, 8, 24, 48, 80, 120, ... (OEIS A033996).

Knight graphs are bipartite and therefore are perfect.

The following table summarizes some named graph complements of knight graphs.

-knight graph	-queen graph
-knight graph	-queen graph

The  knight graph is implemented in the Wolfram Language as KnightTourGraph[m, n], and precomputed properties are available in using GraphData["Knight", m, n].

Closed formulas for the numbers  of -graph cycles of the  knight graph are given by  for  odd and

(1)

(E. Weisstein, Nov. 16, 2014).

A knight's path is a sequence of moves by a knight such that each square of the board is visited exactly once. It is therefore a Hamiltonian path on the corresponding knight graph. Conrad et al. (1994) shows that a knight's path exists on an  board iff .

The above figures show six knight's paths on an  chessboard, all but the first of which are re-entrant. The final path 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 (Steinhaus 1999, p. 30).

If the final position of such a path is a knight's move away from the initial position of the knight, the path is called re-entrant or closed and corresponds to a Hamiltonian cycle on the underlying knight graph. Conrad et al. (1994) shows that a knight's tour exists on an  board iff  and  is even.

Backtracking algorithms (in which the knight is allowed to move as far as possible until it comes to a blind alley, at which point it backs up some number of steps and then tries a different path) can be used to find knight's tours, but such methods can be very slow. Warnsdorff (1823) proposed an algorithm that finds a path without any backtracking by computing ratings for "successor" steps at each position. Here, successors of a position are those squares that have not yet been visited and can be reached by a single move from the given position. The rating is highest for the successor whose number of successors is least. In this way, squares tending to be isolated are visited first and therefore prevented from being isolated (Roth). The time needed for this algorithm grows roughly linearly with the number of squares of the chessboard, but unfortunately computer implementation show that this algorithm runs into blind alleys for chessboards bigger than , despite the fact that it works well on smaller boards (Roth).

Conrad et al. (1994) discovered another linear time algorithm and proved that it solves the Hamiltonian path problem for all . The Conrad et al. algorithm works by decomposition of the chessboard into smaller chessboards (not necessarily square) for which explicit solutions are known. This algorithm is rather complicated because it has to deal with many special cases, but has been implemented in the Wolfram Language by A. Roth. Example tours are illustrated above for  boards with  to 8.

The numbers of (undirected) closed knight's tours (i.e., Hamiltonian cycles) on a  chessboard for , 2, ... are 0, 0, 9862, 13267364410532, ... (OEIS A001230; Ball and Coxeter 1987; Wegener 2000, p. 369; Elkies and Stanley 2003). There are no closed tours for  boards with  odd. Kraitchik (1942, pp. 264-265) also notes that there are 1728 total paths on the  square, 8 of which are symmetric, and there are five doubly symmetric paths on the  square. The number of cycles covering the directed knight's graph for an  chessboard was computed by Wegener and Löbbing (1996) as . They also computed the number of undirected tours, obtaining an incorrect answer  (which is not divisible by 4 as it must be). The correct value of  appears in Wegener's subsequent book (Wegener 2000), and also agrees with unpublished calculations of B. D. McKay.

The longest "uncrossed" knight's tours on an  board for , 4, ... are 2, 5, 10, 17, 24, 35, ... (OEIS A003192).

The following table extends and corrects some additional results given by Kraitchik (1942, pp. 264-265). Here, DHP means geometrically distinct Hamiltonian paths, DSHP means geometrically distinct symmetric paths, HP means total (directed) Hamiltonian paths, DHC means geometrically distinct Hamiltonian cycles, and HC means total (directed) Hamiltonian cycles.

size	DHP	DSHP	HP	DHC	HC
Sloane			A118067		A158074
	0	0	0	0	0
	0	0	0	0	0
	3		16	0	0
	0		0	0	0
	0		0	0	0
	14	2	104	0	0
	104		792	0	0
	146	16	1120	0	0
	773		6096	8	32
	2698	58	21344	0	0
	14350		114496	28	352
	32296		257728	0	0
					3072
				0	0
					30848

Amazingly, the number of Hamiltonian cycles on the  knight graph is given by the 21st-order linear recurrence equation

(2)

with corresponding closed-form generating function

			(3)
			(4)

where

			(5)
			(6)

This result was obtained independently by D. E. Knuth and N. D. Elkies in April 1994, both using the so-called transfer-matrix method (Stanley 1999, Ch. 4.7; Elkies and Stanley 2003).

The numbers of possible (directed) closed tours on a  board for , 4, ... are 16, 0, 164, 1488, 12756, 62176, 379376, 2426224, ... (OEIS A123935; Kraitchik 1942, p. 263). Like the  case, this sequence is known to be given by a linear recurrence relation with constant coefficients, although it appears this recurrence has not yet been explicitly computed.

The  knight graph is Hamilton-laceable iff , , and at least one of ,  is even (Dupuis and Wagon 2014).

REFERENCES

Ahrens, W. Mathematische Unterhaltungen und Spiele. Leipzig, Germany: Teubner, p. 381, 1910.

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.

Conrad, A.; Hindrichs, T.; Morsy, H.; and Wegener, I. "Solution of the Knight's Hamiltonian Path Problem on Chessboards." Discr. Appl. Math. 50, 125-134, 1994.

de Polignac. Comtes Rendus Acad. Sci. Paris, Apr. 1861.

de Polignac. Bull. Soc. Math. de France 9, 17-24, 1881.

Dudeney, H. E. Amusements in Mathematics. New York: Dover, pp. 96 and 102-103, 1970.

Dupuis, M. and Wagon, S. "Laceable Knights." To appear in Ars Math Contemp.Elkies, N. D. and Stanley, R. P. "The Mathematical Knight." Math. Intell. 25, No. 1, 22-34, Winter 2003.

Euler, L. "Solution d'une question curieuse qui ne paroit soumise a aucune analyse." Mémoires de l'Académie Royale des Sciences et Belles Lettres de Berlin, Année 1759 15, 310-337, 1766.