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