---
title: "Knight's Tour and Warnsdorff's Rule"
summary: A Hamiltonian-cycle problem that is nevertheless constructive — closed tours on every board, and the heuristic that finds one instantly.
difficulty: hard
tags: [hamilton, heuristic, construction]
see: [euler/hamilton-theorems, special/coloring]
---

The knight's tour asks for a path on which a knight visits every square of a $b \times 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.

:::theorem title="Existence (Schwenk, 1991)"
An $m \times n$ board with $m \le n$ has a **closed** knight's tour unless at least one of the following holds:
1. $m$ and $n$ are both odd — the two colour classes then differ by one square;
2. $m \in \{1, 2, 4\}$;
3. $m = 3$ and $n \in \{4, 6, 8\}$.

So $3 \times 14$ has a closed tour but $3 \times 8$ does not, and $5 \times 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.

:::props title="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 $\le 1$ move it must be an endpoint" test,
- $m = 4$: cut arguments (a $4 \times 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 \times 4, 3 \times 6, 3 \times 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**.

```cpp warnsdorff.cpp
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 boards
```

It completes a full tour on square boards $5 \le N \le 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.

:::note title="Why greedy works here at all"
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 \ge 5$ a divide-and-conquer construction is standard: tile the board into $5 \times 6$ and $6 \times 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:

:::steps
1. check the three obstructions (parity, $m \le 2$, $m = 4$);
2. if the answer is "yes", run Warnsdorff with $O(8)$ lookahead from a corner — this finishes in microseconds for $N \le 500$ on an $m \times 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 \le 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).
:::

:::warning title="The connectivity prune is not optional"
Naive DFS counts tours on a $5 \times 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.
:::

:::problems
- [[CSES 1689]] Knight's Tour | https://cses.fi/problemset/task/1689 | hard | backtracking + pruning
- [[CSES 1624]] Chessboard and Queens | https://cses.fi/problemset/task/1624 | easy | same pruning style, smaller state
:::