Pruning
Cut branches four ways — feasibility, bound, symmetry, ordering — and quote what each one saves, without claiming the search stopped being exponential.
A backtracking search enumerates an exponential space, and no amount of cleverness changes that. Pruning is what decides whether it finishes: each cut removes a whole subtree rather than a candidate, and a cut near the root removes almost everything below it.
The rule that makes a cut legal is the same every time. A branch may be abandoned only when you can prove nothing inside it is wanted. Four proofs are available.
Feasibility: this branch cannot be completed
Test the partial state against a constraint that can only get worse as the path grows. A partial sum that already exceeds the target, with all values positive. A square already attacked. A cell with no remaining candidate.
The soundness condition is monotonicity: whatever made the partial state illegal stays illegal in every extension of it. Applied to a state that could still recover, the same test silently deletes answers.
Bound: this branch cannot beat the best so far
For optimisation rather than enumeration. Keep the best complete answer found so
far — the incumbent — and cut a branch when partial cost + optimistic remainder
is already at least as bad as it. For a minimum-cost assignment, the optimistic
remainder is the sum of the cheapest entry in each unassigned row.
The bound must be admissible: never worse than the true best completion. Swap "cheapest remaining" for "average remaining" to make the cut fire more often and the search prunes the branch that held the optimum, returns a worse answer, and says nothing about it. A wrong bound looks exactly like a fast search.
The incumbent is the other half. With no incumbent, nothing is worse than infinity and nothing gets cut, so spending the first n² steps on a greedy solution to seed the bound is usually the highest-value line in the file.
Symmetry: this branch is a relabelling of one already tried
The duplicate guard from backtracking
— sort, then skip a[i] == a[i-1] when i > start — is symmetry pruning: the
second copy of a value generates a subtree identical to the first copy's. Board
and graph problems have the same structure at a larger scale.
Ordering: try the most constrained choice first
Ordering removes no branch on its own. It changes when the other three fire, and that is worth more than it sounds, because a cut is worth far more at the top of the tree than at the bottom.
n-queens, with the numbers
Place 8 queens on 64 squares and the candidate space is C(64, 8) = 4,426,165,368, about 4.4 × 10⁹. At roughly 10⁸ simple operations per second, merely walking that list is 44 seconds before any of it is checked.
Two queens on one row always attack, so a row holds exactly one queen. That is feasibility applied to the model, and it costs nothing — no solution has two queens in a row, so none is lost. The space becomes 8⁸ = 16,777,216, a factor of about 260.
The same argument on columns turns the assignment into a permutation: 8! = 40,320, another factor of about 420. Together they are a factor of roughly 110,000, and the code has not been written yet.
What is left is the diagonals, and those get tested during construction rather than after it:
def n_queens(n):
cols, diag, anti = set(), set(), set()
count = 0
def place(row):
nonlocal count
if row == n:
count += 1
return
for c in range(n):
if c in cols or (row - c) in diag or (row + c) in anti:
continue # cut: no completion below here
cols.add(c); diag.add(row - c); anti.add(row + c)
place(row + 1)
cols.remove(c); diag.remove(row - c); anti.remove(row + c)
place(0)
return count
The mission statement for place is "counts every legal completion of rows
row onward, given the queens already placed", and it is
written before the body because a
cut can only be judged against what the call was supposed to return.
row - c is constant along one diagonal direction and row + c along the
other, so two integers name the two diagonals through a square and the whole
legality test is three hash lookups. Instrument place with a counter and it
runs about 2,000 times for n = 8 — against 40,320 complete permutations to
filter, and 4.4 × 10⁹ raw placements. Roughly a factor of two million, end to
end.
Two different wins are hiding in that code and they are worth separating. The three sets make each test O(1) instead of scanning the queens already placed — a constant factor, not a smaller tree: a scan at row r costs up to r comparisons against one probe, and measured in CPython it runs roughly 2–3× slower at n = 8 to 10. The pruning is testing before descending instead of completing and then checking, and that is what removes subtrees.
Where the cut lands decides how much it removes. In the one-queen-per-row model, rejecting a column at row 2 deletes the 8⁵ = 32,768 completions that hung under it; rejecting one at row 6 deletes 8¹ = 8. A cut is worth 4,096 times more at row 2 than at row 6, which is the entire argument for ordering: pay a scan per node to pick the most constrained row, and the cuts move up.
Symmetry closes the last gap. The board has eight symmetries, and left-right mirroring alone means the 92 solutions split evenly: 46 have the first queen in columns 0–3, and the other 46 are their mirror images. Search only the left half of row 0, then reflect. Half the tree, all the answers.
The honest limit
None of this changes the complexity class. The search is still exponential, and for enumeration it provably must be: n = 16 has 14,772,512 solutions, and no algorithm prints 14.8 million answers in polynomial time. What pruning changes is the base and the constant, which shows up as a shift in the largest n you can actually run — brute force stalls around n = 8, feasibility cuts make n = 16 routine, and symmetry plus ordering push it further. Same O, different reach.
Say that out loud rather than claiming a complexity improvement, and quote a measured node count next to the bound, the way the counting method in complexity by counting asks for.
In an interview
State each cut and why it is sound in the same breath: "I cut when the column or either diagonal is taken, which is sound because a queen already placed there cannot be unplaced anywhere inside this subtree." That second clause is the whole test of whether you understand pruning or have memorised a template.
Then give the arithmetic. "C(64, 8) is 4.4 × 10⁹; one queen per row and per column takes it to 8! = 40,320 for free; the diagonal cuts bring the visited nodes to about 2,000." Numbers like that are what turn "I'd use backtracking" into an answer.
The mistake that loses points: saying pruning makes it polynomial. It does not, and the follow-up question is why — the answer being that the output alone is exponential, so the input size never bounds the work. The second mistake is a cut that is not justified, which produces a fast, confident, wrong answer.
Check yourself
Placing 8 queens anywhere on 64 squares is C(64, 8) ≈ 4.4 × 10⁹ candidates. What do the one-per-row and one-per-column restrictions buy, and what do they cost?
8⁸ = 16,777,216, then 8! = 40,320 — factors of about 260 and 420, so roughly 10⁵ overall. They cost nothing: two queens sharing a row or column always attack, so no solution is discarded. Both are feasibility applied to the model before the search starts.
Someone tightens a bound by replacing "sum of the cheapest remaining entries" with "sum of the average remaining entries". What breaks, and how would you notice?
The bound stops being admissible — an average can exceed the true remaining cost, so a branch containing the optimum can be cut. The search gets faster and can return a worse answer. You would only notice by comparing against a brute force on small inputs, which is why the brute force is kept.
In the one-queen-per-row model at n = 8, how many completions does a rejected column remove at row 2 versus row 6, and what does the ratio argue for?
8⁵ = 32,768 against 8¹ = 8, a factor of 4,096. Cuts are worth 8× more per level closer to the root, which is the argument for ordering: trying the most constrained choice first removes no branch by itself, but it makes the cuts happen higher.