Chapter 5 · Euler Tours and Hamilton Cycles
Knight's Tour and Warnsdorff's Rule
A Hamiltonian-cycle problem that is nevertheless constructive — closed tours on every board, and the heuristic that finds one instantly.
The knight's tour asks for a path on which a knight visits every square of a b × b board exactly once — a Hamiltonian path in the knight graph, hence in principle hopeless. In practice boards are structured, and there are two clean facts plus one heuristic.
An m × n board with m ≤ n has a closed knight's tour unless at least one of the following holds:
- m and n are both odd — the two colour classes then differ by one square;
- m ∈ {1, 2, 4};
- m = 3 and n ∈ {4, 6, 8}.
So 3 × 14 has a closed tour but 3 × 8 does not, and 5 × 5 has open tours only.
The parity obstruction is the instructive one: the knight graph is bipartite (each move changes square colour), so a closed tour needs equally many black and white squares, i.e. an even number of cells. An open tour on an odd-area board must start and end on the majority colour.
Two more obstructions worth knowing
- m = 1, 2: the knight graph is disconnected / has vertices of degree < 2 — no tour, and the degree argument is the general "if a vertex has ≤ 1 move it must be an endpoint" test,
- m = 4: cut arguments (a 4 × n board splits into two halves the knight crosses in balanced pairs) — the reason m=4 is excluded for closed tours while open ones do exist,
- 3 × 4, 3 × 6, 3 × 8: no closed tour although parity is fine — the standard small exceptions; verify by hand once and you will never re-derive them under time pressure.
#Warnsdorff's rule: the heuristic that is basically the algorithm
From the current square, move to the neighbour with the fewest onward moves.
const int dx[8] = {1, 2, 1, -1, -2, -1, 1, 2}, dy[8] = {2, 1, -1, -2, -1, 1, 2, 1};
int deg(int x, int y, bool used[8][8]) {
int c = 0;
for (int k = 0; k < 8; k++) {
int a = x + dx[k], b = y + dy[k];
if (0 <= a && a < N && 0 <= b && b < N && !used[a][b]) c++;
}
return c;
}
// O(N^2) squares, each with 8*8 lookahead -> fine up to huge boardsIt completes a full tour on square boards 5 ≤ N ≤ 76 for every starting square (verified computationally; a proof for all N is open — a nice example of a heuristic with an empirical track record far better than its theory). Tie-breaking matters: prefer the neighbour whose own onward-move count is minimal, or break ties by the largest distance from the board centre; either variant fixes almost all failures.
Squares in a corner have degree 2, edges degree 3–4, the centre degree 8. The constraint "every square must be entered and left" is tightest at the corners, and Warnsdorff's rule is precisely "visit the constrained squares while they are still feasible" — the same reason the arc-consistency heuristic works in constraint programming. Hamiltonicity is NP-complete on general graphs but the knight graph is nowhere near general: bounded degree, planar-ish, and highly symmetric.
#When you must produce a tour (construction, not search)
For N ≥ 5 a divide-and-conquer construction is standard: tile the board into 5 × 6 and 6 × 5 blocks (each of which has a closed tour with an exit edge), splice them along shared edges, and handle the leftover strip by symmetry. Concretely, in a contest the reliable recipe is:
- 1
check the three obstructions (parity, m ≤ 2, m = 4);
- 2
if the answer is "yes", run Warnsdorff with O(8) lookahead from a corner — this finishes in microseconds for N ≤ 500 on an m × n board with the same tie-break,
- 3
if the judge demands determinism, use the block construction, since Warnsdorff is empirically (not provably) complete,
- 4
for "count the tours" on tiny boards (N ≤ 6), do plain DFS with bitsets and a connectivity prune — the prune that matters: abort when the unvisited squares are disconnected (check with one BFS).
Naive DFS counts tours on a 5 × 5 board in tens of seconds; with "abort if the unvisited graph becomes disconnected, or if any unvisited square drops to 0 available neighbours", the same count takes a fraction of a second. Both prunes are the necessary conditions of the propositions above turned into code — that is how theory earns its place in a brute force.