N-Queens & backtracking

Overview

Backtracking is recursion that makes a choice, explores the consequences, and then undoes the choice before trying the next one. N-Queens is the canonical example: place a queen in the current row, recurse to the next row, and on return remove her so the next column can be tried. What makes it fast enough to be practical is pruning — never recursing into a placement that is already known to be attacked. The bitmask formulation makes that check a single AND, and the undo free, because the state is passed by value rather than mutated.

Why it matters

Backtracking is the general technique for constraint-satisfaction problems: Sudoku, graph colouring, scheduling with conflicts, crossword filling, and puzzle solvers of all kinds. The place-recurse-undo skeleton is identical across all of them, so learning it once transfers widely. And pruning is what separates a solver that finishes from one that does not — the difference is often many orders of magnitude.

Core concepts

The skeleton. For each candidate: if it is valid, apply it, recurse, then undo it. The undo is what makes the search a tree rather than a one-way walk.

Pruning is the point. Testing a placement before recursing cuts an entire subtree. Without pruning, N-Queens on an 8x8 board would explore an astronomically larger space; with it, the search finishes instantly.

Bitmask state. Represent the threatened columns and the two diagonal families as three integers. A queen at column c sets bit c in cols; the diagonals shift by one each row, so passing (d1 | bit) << 1 and (d2 | bit) >> 1 to the next row automatically expresses "this diagonal threat moves over by one".

Pass-by-value is the undo. Because the masks are passed as arguments rather than mutated in place, returning from a call restores the previous state for free — no explicit cleanup and no possibility of forgetting it.

The available-squares trick. free = ~(cols | d1 | d2) & full gives every safe column at once; iterating with bit = free & -free (isolate the lowest set bit) and free &= free - 1 (strip it) reuses exactly the bit-manipulation idioms from earlier in the curriculum.

Complexity. Still exponential in the worst case — backtracking prunes, it does not change the class.

Syntax notes

/* count solutions; cols/d1/d2 are the threatened columns and diagonals */
static int solve(int n, int row, int cols, int d1, int d2) {
    if (row == n) return 1;                       /* all rows placed - one solution */
    int full = (1 << n) - 1;
    int free_sq = ~(cols | d1 | d2) & full;       /* every safe column at once */
    int count = 0;
    while (free_sq) {
        int bit = free_sq & -free_sq;             /* isolate lowest safe column */
        free_sq &= free_sq - 1;                   /* strip it for the next iteration */
        /* state is passed BY VALUE, so the undo is automatic on return */
        count += solve(n, row + 1,
                       cols | bit,
                       (d1 | bit) << 1,           /* diagonals shift as we move down */
                       (d2 | bit) >> 1);
    }
    return count;
}
/* call: solve(n, 0, 0, 0, 0) */

Key points:

• Passing masks by value is the backtracking undo — nothing to reset manually.
• (1 << n) - 1 requires n < 32; guard it, since 1 << 32 is undefined.
• One row per recursion level means the row constraint is satisfied by construction.

Lesson

Backtracking explores a tree of choices: place a queen, recurse to the next row, and undo the placement to try the next column. A safe predicate prunes attacked squares. This place-recurse-undo pattern solves constraint puzzles in general.

Code examples

#include <stdio.h>
static int solve(int n,int row,int cols,int d1,int d2){
    if(row==n) return 1;
    int c=0;
    for(int col=0;col<n;col++){ int cb=1<<col,b1=1<<(row+col),b2=1<<(row-col+n-1);
        if((cols&cb)||(d1&b1)||(d2&b2)) continue;
        c+=solve(n,row+1,cols|cb,d1|b1,d2|b2); }
    return c;
}
int main(void){
    printf("solutions to the N-Queens puzzle:\n");
    for(int n=1;n<=8;n++) printf("  %d-queens: %d\n", n, solve(n,0,0,0,0));
    return 0;
}

Line by line

Common mistakes

Not undoing state on return; incomplete attack checks (missing diagonals).

Debugging tips

Compiler errors and warnings:

• warning: left shift count >= width of type when n reaches 32 — guard the board size.
• -Wsign-compare or unexpected sign extension if the masks are signed and bit 31 is touched; keep n small or use unsigned.

Runtime symptoms:

• Counts are far too high. Pruning is wrong — you are not masking one of the diagonals, or full is miscomputed so phantom columns appear.
• Counts are far too low or zero. The diagonal shifts are the wrong way round; d1 shifts left, d2 shifts right as the row advances.
• Infinite recursion. You forgot free_sq &= free_sq - 1, so the same column is tried forever.
• Works for n = 4 but wrong for n = 8. Usually the diagonal handling; verify against the known sequence 1, 0, 0, 2, 10, 4, 40, 92.
• In a mutable-array version, results drift between runs. You forgot to undo a placement — the classic backtracking bug the bitmask version avoids entirely.

Technique: check against the known solution counts for n = 1..8. Any deviation pinpoints which constraint is mishandled.

Memory safety

• Board size versus type width. (1 << n) - 1 is undefined for n >= 32; validate n before use. This is the same undefined-shift hazard from the bit-manipulation track.
• Signed shifts. (d1 | bit) << 1 on a signed int can overflow into the sign bit for large n. Use unsigned masks if you intend to support wide boards.
• Depth is bounded by n, so the stack is safe — backtracking's cost is time, not memory.
• Mutable-state versions need discipline. If you use an array instead of masks, every return path must undo the placement; an early return that skips the undo corrupts all later branches. The by-value approach removes that entire class of bug.
• Exponential runtime is the real hazard. Accepting n from untrusted input without a cap is a denial-of-service risk.

Real-world uses

Concrete uses: Sudoku and puzzle solvers, graph colouring, exam and shift timetabling with conflict constraints, register allocation in compilers, crossword and word-fill generation, and SAT-style search. The place-recurse-undo skeleton is shared by all of them; only the validity test changes.

Professional best practices:

Beginner:

• Write the undo immediately after the recursive call, before you add anything else.
• Prune before recursing, never after.

Intermediate:

• Prefer passing state by value (or using immutable masks) so the undo cannot be forgotten.
• Order candidate choices to fail fast — most-constrained-variable heuristics dramatically shrink the tree.
• Cap the input size; backtracking is exponential and elegant code hides that fact.

Practice tasks

1. (Beginner) Count N-Queens solutions. Implement solve(n, 0, 0, 0, 0) with bitmasks. Example: n = 4 -> 2; n = 8 -> 92. Concepts: place-recurse-undo, pruning.

2. (Beginner) Verify the sequence. Print solution counts for n = 1..8 and compare with 1, 0, 0, 2, 10, 4, 40, 92. Concepts: validating against a known oracle.

3. (Intermediate) Print one solution. Modify the search to record the column chosen per row and print the first complete board. Concepts: capturing state during backtracking.

4. (Intermediate) Array-based version. Reimplement with an explicit int cols[n] array and a safe() check, making the undo explicit. Requirements: it must agree with the bitmask version. Concepts: explicit undo, why by-value is safer.

Summary

Backtracking is choose, recurse, undo — and the undo is what turns a walk into a search tree. Pruning invalid choices before recursing is what makes it finish: it removes whole subtrees rather than exploring and rejecting them. The bitmask formulation of N-Queens keeps threatened columns and both diagonal families in three integers, shifting the diagonals by one per row, and because that state is passed by value the undo happens automatically on return — eliminating the single most common backtracking bug. Guard the board size against undefined shifts, and remember the algorithm is still exponential.

Practice with these exercises

• Count N-Queens solutions
• Queen-safe check