Knight Graph


The m×n knight graph is a graph on mn vertices in which each vertex represents a square in an m×n 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 (1,2)-leaper graph.

The 3×3 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 n×n knight graph is 4(n-2)(n-1) (8 times the triangular numbers), so for n=1, 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.

(2,3)-knight graph(2,3)-queen graph
(3,3)-knight graph(3,3)-queen graph

The m×n 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 c_k of k-graph cycles of the n×n knight graph are given by c_k=0 for k odd and

c_4={0 for n<=3; 2(3n^2-18n+26) otherwise

(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 n×n board iff n>=5.


The above figures show six knight's paths on an 8×8 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 n×n board iff n>=6 and n 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 76×76, 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 n>=5. 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 n×n boards with n=5 to 8.

The numbers of (undirected) closed knight's tours (i.e., Hamiltonian cycles) on a (2n)×(2n) chessboard for n=1, 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 m×m boards with m odd. Kraitchik (1942, pp. 264-265) also notes that there are 1728 total paths on the 5×5 square, 8 of which are symmetric, and there are five doubly symmetric paths on the 6×6 square. The number of cycles covering the directed knight's graph for an 8×8 chessboard was computed by Wegener and Löbbing (1996) as 8121130233753702400. They also computed the number of undirected tours, obtaining an incorrect answer 33439123484294 (which is not divisible by 4 as it must be). The correct value of 13267364410532 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 n×n board for n=3, 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.


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


with corresponding closed-form generating function




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 4×k board for k=3, 4, ... are 16, 0, 164, 1488, 12756, 62176, 379376, 2426224, ... (OEIS A123935; Kraitchik 1942, p. 263). Like the 3×(2n) 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 m×n knight graph is Hamilton-laceable iff m>=6, n>=6, and at least one of m, n is even (Dupuis and Wagon 2014).

See also

Antelope Graph, Bishop Graph, Black Bishop Graph, Camel Graph, Chess, Fiveleaper Graph, Giraffe Graph, Hamiltonian Cycle, Hamiltonian Path, King Graph, Kings Problem, Knights Problem, Leaper Graph, Magic Tour, Queen Graph, Queens Problem, Rook Graph, Tour, White Bishop Graph, Zebra Graph

Explore with Wolfram|Alpha


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, Polignac. Comtes Rendus Acad. Sci. Paris, Apr. 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.", 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 n Queens Problem." §C18 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 133-135, 1994.Update a linkJelliss, G. "Knight's Tour Notes." a linkJelliss, G. "Chronology of Knight's Tours.", A. M. "FlowProblem: Statistics of Simple Cycles.", 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)", P. M. Philos. Mag. 16, 305-309, 1840.Rose, C. "The Distribution of the Knight." Roth, A. "The Problem of the Knight: A Fast and Simple Algorithm.", F. "A Search Procedure for Hamilton Paths and Circuits." J. ACM 21, 576-580, 1974.Ruskey, F. "Information on the n Knight's Tour Problem.", 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." 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.", 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 33439123484294--Counting with Binary Decision Diagrams." Electronic J. Combinatorics 3, No. 1, R5, 1-4, 1996.

Cite this as:

Weisstein, Eric W. "Knight Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications