OFFSET
1,18
COMMENTS
A Knight graph K_{k, n} (for k, n integers) is the set of squares of a k X n chessboard, where two vertices are adjacent if a knight's move in chess connects the corresponding squares.
A Hamiltonian path in a finite graph G = (V, E) is a sequence of distinct vertices v_1, ..., v_{|V|} such that (v_i, v_{i+1}) is in E for all 1 <= i < |V|.
An undirected Hamiltonian path is an equivalence class under reversal of the path; i.e., v_1, ..., v_{|V|} and v_{|V|}, ..., v_1 are considered equivalent.
REFERENCES
Donald E. Knuth, The Art of Computer Programming, Vol. 4, section 7.1.4, Addison-Wesley, 2009.
Donald E. Knuth, Selected papers on fun and games, ch. 42. Long and Skinny Knight's Tours, The University of Chicago Press, 2011.
Donald E. Knuth, Hamiltonian paths and cycles, Prefascicle 8a of The Art of Computer Programming (work in progress, 2025).
LINKS
Peter Luschny, Table of n, a(n) for n = 1..136. The first 16 antidiagonals of the array; the values are taken from the original sequences.
Alfred James Brown, Knight's Tours and Zeta Functions, 2017, Master's Theses.
Leonhard Euler, Solution d'une question curieuse que ne paroit soumise à aucune analyse, 1766. Euler Archive - All Works, 309. [Caveat: In §43 Euler makes a mistake.]
George Jelliss, Introducing Knight's Tours, 2004.
Donald E. Knuth, Adventures with Knight's Tours, Christmas lecture Dec. 2025.
Peter Luschny, Illustrating Knight's Tours, SageMath notebook.
Peter Luschny, Counting Knight's Tours, C++ implementation.
Eric Weisstein's World of Mathematics, Hamiltonian Path.
Eric Weisstein's World of Mathematics, Knight Graph.
Wikipedia, Knight's tour.
EXAMPLE
Array begins:
[k\n] 1 2 3 4 5 6 7
------------------------------------------------------------------------
[1] 0, 0, 0, 0, 0, 0, 0, ... A000004
[2] 0, 0, 0, 0, 0, 0, 0, ... A000004
[3] 0, 0, 0, 8, 0, 0, 52, ... A169696
[4] 0, 0, 8, 0, 82, 744, 6378, ... A079137
[5] 0, 0, 0, 82, 864, 18784, 622868, ... A083386
[6] 0, 0, 0, 744, 18784, 3318960, 389969466, ... A306281
[7] 0, 0, 52, 6378, 622868, 389969466, 82787609160, ... A306283
[8] 0, 0, 396, 31088, 18061054, 24964893804, 20666425060328, ... A389760
[9] 0, 0, 560, 189688, 264895640, 1770631206422, 2903212163753000, ... A391009
.
Seen as a triangle:
[ 1] 0;
[ 2] 0, 0;
[ 3] 0, 0, 0;
[ 4] 0, 0, 0, 0;
[ 5] 0, 0, 0, 0, 0;
[ 6] 0, 0, 8, 8, 0, 0;
[ 7] 0, 0, 0, 0, 0, 0, 0;
[ 8] 0, 0, 0, 82, 82, 0, 0, 0;
[ 9] 0, 0, 52, 744, 864, 744, 52, 0, 0;
.
A knight's tour on the squares 1-12 of a 3 X 4 board in linear numbering:
1 -> 7 -> 9 -> 2 -> 8 -> 10 -> 3 -> 12 -> 6 -> 4 -> 11 -> 5.
The same tour in coordinate notation:
a1 -> c2 -> a3 -> b1 -> d2 -> b3 -> c1 -> d3 -> b2 -> d1 -> c3 -> a2.
A knight's tour on the squares 1-12 of a 4 X 3 board:
1 -> 8 -> 3 -> 4 -> 11 -> 6 -> 7 -> 12 -> 5 -> 10 -> 9 -> 2.
a1 -> b3 -> c1 -> a2 -> b4 -> c2 -> a3 -> c4 -> b2 -> a4 -> c3 -> b1.
MATHEMATICA
AllHamiltonianPaths[G_] := Module[{n = VertexCount[G], verts = VertexList[G]},
Flatten[Table[FindPath[G, u, v, {n - 1}, All], {u, verts}, {v, verts}], 2]];
KnightHamiltonianPaths[k_Integer, n_Integer] := Module[{G, paths},
G = KnightTourGraph[k, n]; paths = AllHamiltonianPaths[G];
Select[paths, First[#] < Last[#] &]];
A[k_Integer, n_Integer] := Length[KnightHamiltonianPaths[k, n]];
Print["(3, 4) -> ", A[3, 4]]; Print["(5, 4) -> ", A[5, 4]]; Print["(3, 7) -> ", A[3, 7]];
PROG
(C++) // Cf. links.
(SageMath)
# The function shown outlines the general method, but is only effective for small k and n.
# The computation by brute-force is unusable for larger boards.
def hamiltonian_paths(G: Graph):
n = G.num_verts()
vertices = list(G.vertices())
def backtrack(path, visited):
if len(path) == n:
yield path
return
for v in G.neighbors(path[-1]):
if v not in visited:
yield from backtrack(path + [v], visited | {v})
for v in vertices:
yield from backtrack([v], {v})
def knight_hamiltonian_paths(k: int, n: int):
G = graphs.KnightGraph([k, n])
for path in hamiltonian_paths(G):
if path[0] < path[-1]:
yield path
def A(k: int, n: int) -> int:
return sum(1 for _ in knight_hamiltonian_paths(k, n))
print("(3, 4) -> ", A(3, 4)); print("(5, 4) -> ", A(5, 4)); print("(3, 7) -> ", A(3, 7))
CROSSREFS
KEYWORD
AUTHOR
Peter Luschny, Nov 21 2025
STATUS
approved