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[{" src="https://mathworld.wolfram.com/images/equations/KnightGraph/Inline16.svg" style="height:21px; width:6px" />"Knight", {" src="https://mathworld.wolfram.com/images/equations/KnightGraph/Inline17.svg" style="height:21px; width:6px" />m, n}" src="https://mathworld.wolfram.com/images/equations/KnightGraph/Inline18.svg" style="height:21px; width:6px" />}" src="https://mathworld.wolfram.com/images/equations/KnightGraph/Inline19.svg" style="height:21px; width:6px" />].

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

{0 for n<=3; 2(3n^2-18n+26) otherwise" src="https://mathworld.wolfram.com/images/equations/KnightGraph/Inline27.svg" style="height:59px; width:217px" />

(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).

---

EFERENCES

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.

Euler, L. Commentationes Arithmeticae Collectae, Vol. 1. Leningrad, pp. 337-355, 1849.

Friedel, F. "The Knight's Tour." http://www.chessbase.com/columns/column.asp?pid=163.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.

Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 98-100, 1984.

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

Jelliss, G. "Knight's Tour Notes." http://www.ktn.freeuk.com/Jelliss, G. "Chronology of Knight's Tours." http://www.ktn.freeuk.com/cc.htmKaravaev, A. M. "FlowProblem: Statistics of Simple Cycles." http://flowproblem.ru/paths/statistics-of-simple-cycles.Kraitchik, M. "The Problem of the Knights." Ch. 11 in Mathematical Recreations. New York: W. W. Norton, pp. 257-266, 1942.

Kyek, O.; Parberry, I.; and Wegener, I. "Bounds on the Number of Knight's Tours." Discr. Appl. Math. 74, 171-181, 1997.

Lacquière. Bull. Soc. Math. de France 8, 82-102 and 132-158, 1880.

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

Murray, H. J. R. "The Knight's Tour, Ancient and Oriental." British Chess Magazine, pp. 1-7, 1902.

Pegg, E. Jr. "Leapers (Chess Knights and the Like)" http://www.mathpuzzle.com/leapers.htm.Roget, P. M. Philos. Mag. 16, 305-309, 1840.

Rose, C. "The Distribution of the Knight." http://www.tri.org.au/knightframe.html.

 Roth, A. "The Problem of the Knight: A Fast and Simple Algorithm." http://library.wolfram.com/infocenter/MathSource/909/.Rubin, F. "A Search Procedure for Hamilton Paths and Circuits." J. ACM 21, 576-580, 1974.

Ruskey, F. "Information on the  Knight's Tour Problem." http://www.theory.csc.uvic.ca/~cos/inf/misc/Knight.html.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 166, 1990.

Sloane, N. J. A. Sequences A001230, A003192/M1369, A006075/M3224, A033996, A118067, A123935, and A158074 in "The On-Line Encyclopedia of Integer Sequences."Stanley, R. P. Enumerative Combinatorics, Vol. 1. Cambridge, England: Cambridge University Press, 1999.

Steinhaus, H. Mathematical Snapshots, 3rd ed. New York: Dover, p. 30, 1999.

Thomasson, D. "The Knight's Tour." http://www.borderschess.org/KnightTour.htm.van der Linde, A. Geschichte und Literatur des Schachspiels, Vol. 2. Berlin: Springer-Verlag, pp. 101-111, 1874.

Vandermonde, A.-T. "Remarques sur les Problèmes de Situation." L'Histoire de l'Académie des Sciences avec les Mémoires, Année 1771. Paris: Mémoirs, pp. 566-574 and Plate I, 1774.

Velucchi, M. "Knight's Tour: The Ultimate Knight's Tour Page of Links." http://www.velucchi.it/mathchess/knight.htm.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.

Warnsdorff, H. C. von Des Rösselsprungs einfachste und allgemeinste Lösung. Schmalkalden, 1823.

Watkins, J. Across the Board: The Mathematics of Chessboard Problems. Princeton, NJ: Princeton University Press, 2004.Watkins, J. J. and Hoenigman, R. L. "Knight's Tours on a Torus." Math. Mag. 70, 175-184, 1997.

Wegener, I. Branching Programs and Binary Decision Diagrams. Philadelphia, PA: SIAM, 2000.Wegener, I. and Löbbing, M. "The Number of Knight's Tours Equals --Counting with Binary Decision Diagrams." Electronic J. Combinatorics 3, No. 1, R5, 1-4, 1996. http://www.combinatorics.org/Volume_3/Abstracts/v3i1r5.html.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength