Backtracking

Build a solution incrementally; abandon a partial solution (“backtrack”) as soon as it cannot be completed.

The skeleton

void solve(State& s, int depth) {
    if (complete(s)) { record(s); return; }
    if (!feasible(s)) return;                          // PRUNE
    for (Choice c : candidates(s)) {
        apply(s, c);
        solve(s, depth + 1);
        undo(s, c);                                    // the "backtrack"
    }
}

The undo is what makes it backtracking rather than brute force: state is mutated in place and restored, so no copying is needed.

Pruning — where all the performance is

Without pruning, backtracking is just exponential enumeration. The techniques, in rough order of value:

Technique	Idea
Constraint propagation	after each choice, eliminate now-impossible options
Most-constrained variable first (MRV)	branch on the variable with the fewest remaining options
Least-constraining value	try the value that eliminates the fewest options for others
Bounding	if the best possible completion is worse than the incumbent, prune
Symmetry breaking	fix a canonical order among interchangeable choices
Forward checking	detect a variable with zero remaining options immediately
Memoization	cache equivalent states
Early failure detection	check global feasibility (counts, parity, connectivity)

MRV is the single highest-value heuristic. Branching on the most constrained variable makes the tree narrow at the top, where it matters most. It is what turns a Sudoku solver from seconds to microseconds.

Symmetry breaking

If items are interchangeable, fix a canonical order so each solution is generated once:

// assigning items to groups: item i may only open group g if all groups < g are used
for (int g = 0; g <= usedGroups && g < maxGroups; g++) { ... }

Without this, a partition into $k$ groups is produced $k!$ times. This is often a 10-100× speedup and is the first thing to add.

Other common symmetries: reflections and rotations of a board, permutations of identical pieces, and the choice of which element goes “first”.

Classic backtracking problems

Problem	Key pruning
N-Queens	column/diagonal bitmasks; place row by row
Sudoku	MRV + constraint propagation, or DLX
Graph colouring	order vertices by degree; symmetry-break the colours
Knight’s tour	Warnsdorff’s rule (fewest onward moves first)
Subset sum / partition	sort descending; skip duplicates; bound the remaining sum
Hamiltonian path	prune on degree-0 or two degree-1 vertices remaining
Exact cover (pentominoes)	Dancing Links
Crossword / word placement	MRV on the most constrained slot
Maximum clique	Bron-Kerbosch with a colouring bound

N-Queens with bitmasks

void queens(int row, int cols, int d1, int d2, int n, int& count) {
    if (row == n) { count++; return; }
    int avail = ~(cols | d1 | d2) & ((1 << n) - 1);
    while (avail) {
        int bit = avail & -avail;
        avail ^= bit;
        queens(row + 1, cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1, n, count);
    }
}

Three integers encode all the constraints, and the shifts propagate the diagonals automatically. $n=15$ in well under a second.

Warnsdorff’s rule

For a knight’s tour, always move to the square with the fewest onward moves. This heuristic finds a tour on boards up to $100\times 100$ almost without backtracking — a striking demonstration that a good ordering can dominate everything else.

Skipping duplicates

When the candidate list contains equal values, generate each distinct choice once:

sort(a.begin(), a.end());
for (int i = 0; i < n; i++) {
    if (i > 0 && a[i] == a[i-1] && !used[i-1]) continue;    // skip duplicates
    ...
}

The !used[i-1] condition forces equal elements to be used in index order. This is the standard idiom for “permutations with duplicates” and “subsets with duplicates”.

Backtracking vs the alternatives

Situation	Method
Small $n$, need all solutions	backtracking
Small $n$, need one solution	backtracking with early exit
Optimising, with a good bound	branch and bound
Overlapping subproblems	memoization / DP
$n\le 22$, subset structure	bitmask DP
$n\le 45$, splittable	meet in the middle
Exact cover structure	Dancing Links
Boolean constraints	a SAT solver, or 2-SAT if binary clauses
Too big for exact	heuristics

See also: Branch and Bound · Dancing Links · Exact Cover