Knight's Tour

Problem. Move a knight over every square of an $n \times n$ board exactly once. A closed tour returns to the start; an open tour need not.

This is a Hamiltonian path problem on the knight-move graph — NP-hard in general, but easy here because the graph is highly structured.

Warnsdorff’s rule — the key heuristic

Always move to the square with the fewest onward moves.

int dx[8] = {2,1,-1,-2,-2,-1,1,2}, dy[8] = {1,2,2,1,-1,-2,-2,-1};
 
int degree(int x, int y, vector<vector<int>>& vis, int n) {
    int c = 0;
    for (int d = 0; d < 8; d++) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx >= 0 && ny >= 0 && nx < n && ny < n && !vis[nx][ny]) c++;
    }
    return c;
}
 
bool tour(int n, int sx, int sy, vector<vector<int>>& vis) {
    vis[sx][sy] = 1;
    int x = sx, y = sy;
    for (int step = 2; step <= n * n; step++) {
        int best = -1, bestDeg = 9, bx = -1, by = -1;
        for (int d = 0; d < 8; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n || vis[nx][ny]) continue;
            int dg = degree(nx, ny, vis, n);
            if (dg < bestDeg) { bestDeg = dg; bx = nx; by = ny; }
        }
        if (bx < 0) return false;
        x = bx; y = by; vis[x][y] = step;
    }
    return true;
}

It almost never backtracks. Warnsdorff’s rule finds tours on boards up to $100 \times 100$ essentially instantly, despite the underlying problem being NP-hard.

The intuition: squares with few remaining exits become unreachable if not visited soon, so visit them first. It is exactly the most-constrained-first heuristic from backtracking.

For robustness, break ties by distance from the centre, and add backtracking as a fallback.

Existence

Board	Open tour	Closed tour
$n \times n$ , $n \geq 5$	yes	yes iff $n$ is even
$n \times n$ , $n$ odd	yes	no
$3 \times 3$	no (the centre is isolated)	no
$4 \times 4$	no	no
$5 \times 5$	yes	no
$m \times n$ , general	Schwenk’s theorem gives the exact conditions

Why no closed tour on odd boards: a knight alternates colours every move. A closed tour has $n^{2}$ moves, so it needs equally many squares of each colour — impossible when $n^{2}$ is odd. A clean parity argument.

Schwenk’s theorem. An $m \times n$ board ( $m \leq n$ ) has a closed tour unless: $m$ and $n$ are both odd; or $m \in {1, 2, 4}$ ; or $m = 3$ and $n \in {4, 6, 8}$ .

Divide and conquer

For large boards, split into quadrants, find a tour in each (recursively or from a base case), and stitch them together by breaking one edge in each and reconnecting. Gives an $O (n^{2})$ construction with a guarantee, rather than relying on a heuristic.

Counting tours

The number of closed tours on $8 \times 8$ is 26 534 728 821 064 — computed by exhaustive search with heavy symmetry reduction. There is no formula, and counting is far harder than finding.

Variants

Variant	Note
Closed tour	needs even $n$
Tour from a specific square	usually possible on large boards
Tour visiting squares in a given order	much harder
Knight’s distance between two squares	a closed form exists, or BFS
Minimum knight moves on an infinite board	a formula based on $∣ Δ x ∣, ∣ Δ y ∣$
Knight moves on a torus / 3D board	different existence conditions
Other pieces (camel, giraffe)	same framework, different move sets

Knight distance on an infinite board is worth knowing: for $(x, y)$ with $x \geq y \geq 0$ , the answer is a small case analysis around $max (⌈ x /2 ⌉, ⌈(x + y) /3 ⌉)$ adjusted for parity, with special cases near the origin. Contest problems often ask exactly this — and a BFS over a bounded region also works.

Why it is worth knowing

It is the standard illustration that a good ordering heuristic can beat exponential search. Warnsdorff’s rule has no proof of correctness, yet it works on every board anyone has tested — a useful reminder that “NP-hard” describes the worst case, not the instances you meet.

See also: Hamiltonian Path · Backtracking · Parity Arguments

whoashish's cp notes

Directory