xvii. Knight's Tour and N Queens

Two classical chessboard puzzles that are also the standard first examples of backtracking and heuristic search.

N queens

Place $n$ queens so that none attack each other. Count solutions with bitmask backtracking: rows are placed in order, and three masks hold the attacked columns and diagonals for the current row.

long long nQueens(int n) {                         // number of solutions, bitmask backtracking
    long long cnt = 0; int full = (1 << n) - 1;
    auto rec = [&](auto self, int cols, int d1, int d2) -> void {
        if (cols == full) { cnt++; return; }
        for (int free = full & ~(cols | d1 | d2); free; free &= free - 1) {
            int b = free & -free;
            self(self, cols | b, (d1 | b) << 1 & full, (d2 | b) >> 1);
        }
    };
    rec(rec, 0, 0, 0);
    return cnt;
}

$n$	1	2	3	4	5	6	7	8	9	10	11	12
solutions	1	0	0	2	10	4	40	92	352	724	2680	14200

A single solution for any $n\ge 4$ can be written down directly (explicit constructions by residue of $n$ mod 6), so “find one” is $O(n)$ while “count all” is exponential.

Proof: the shifted masks track the diagonals

A queen at column $c$ in row $r$ attacks column $c+t$ and $c-t$ in row $r+t$. Shifting the ”/” mask left by one per row and the "" mask right by one per row moves each recorded attack to the cell it hits in the next row, and masking with full drops attacks that leave the board. So free is exactly the set of safe columns in the current row, and the recursion enumerates every placement once.

Knight’s tour

Visit every square exactly once with knight moves. Warnsdorff’s rule: always move to the square with the fewest onward moves. It finds tours on almost every board in $O(n^2)$; with a bad tie-break it can get stuck, so the code retries with random tie-breaking.

vector<pair<int, int>> knightsTourOnce(int n, int sr, int sc, mt19937* rng) {   // Warnsdorff; ties: farther from centre, or random
    int dr[] = {2, 1, -1, -2, -2, -1, 1, 2}, dc[] = {1, 2, 2, 1, -1, -2, -2, -1};
    vector<vector<int>> seen(n, vector<int>(n, 0)); vector<pair<int, int>> path{{sr, sc}}; seen[sr][sc] = 1;
    auto deg = [&](int r, int c) { int d = 0; for (int k = 0; k < 8; k++) { int x = r + dr[k], y = c + dc[k]; d += x >= 0 && x < n && y >= 0 && y < n && !seen[x][y]; } return d; };
    for (int step = 1; step < n * n; step++) {
        auto [r, c] = path.back(); int br = -1, bc = -1, bd = 9; double bdist = -1;
        for (int k = 0; k < 8; k++) {
            int x = r + dr[k], y = c + dc[k];
            if (x < 0 || x >= n || y < 0 || y >= n || seen[x][y]) continue;
            int d = deg(x, y); double dist = (x - (n - 1) / 2.0) * (x - (n - 1) / 2.0) + (y - (n - 1) / 2.0) * (y - (n - 1) / 2.0);
            if (rng) dist = (*rng)() % 1000;
            if (d < bd || (d == bd && dist > bdist)) bd = d, bdist = dist, br = x, bc = y;
        }
        if (br < 0) return {};
        seen[br][bc] = 1; path.push_back({br, bc});
    }
    return path;
}
vector<pair<int, int>> knightsTour(int n, int sr = 0, int sc = 0) {   // empty if none found (n = 2, 3, 4 have none)
    auto t = knightsTourOnce(n, sr, sc, nullptr);
    mt19937 rng(12345);
    for (int it = 0; it < 200 && t.empty(); it++) t = knightsTourOnce(n, sr, sc, &rng);
    return t;
}

Fact	Value
open tours exist	$n=1$ and $n\ge 5$
closed tours exist ($n\times n$)	even $n\ge 6$ (Schwenk’s theorem gives all $m\times n$ boards)
exact search	backtracking with Warnsdorff ordering, or a Hamiltonian-path DP on tiny boards

Proof: why Warnsdorff works well, and what is guaranteed

A square with few unvisited neighbours is at risk of becoming a dead end; visiting it now spends one of its exits instead of stranding it. This is a heuristic, not a theorem, so the code verifies the result: every consecutive pair is a knight move and all $n^2$ squares are distinct. With deterministic tie-breaking (prefer squares far from the centre) and up to 200 random retries, it produced valid tours for every $5\le n\le 40$ in testing. Non-existence for $n=2,3,4$ was verified by exhaustive backtracking from every start square (on $3\times 3$ the centre has no knight moves at all).