Backtracking: N-Queens, subsets, permutations

Build a candidate incrementally; abandon it the moment it's doomed. Depth-first search + PRUNING.

The move: try — recurse — undo

• Make a choice; recurse to make the next; undo it if the recursion fails
• N-Queens: place one queen per column, skip attacked rows (prune)
• Dead-end column → back up, remove a queen, try a higher row
• Subsets & permutations are the same skeleton

Watch it search

Green ♛ = placed on a safe square · red = attacked → pruned · orange = backtrack (undo). Every red square dismisses a whole branch unexamined.

Pruning vs brute force

N=12: brute force 8.9 trillion arrangements, backtracking 10 million nodes → 880,000× fewer.

Pruning is the algorithm

• A conflict at column 3 prunes ALL arrangements of the rest — unexamined
• Stronger pruning: forward checking, constraint propagation, variable ordering
• This skeleton + smart pruning = SAT solvers, constraint programming
• Still exponential worst case — tractable in practice, not polynomial

Takeaway

Don't ask "how do I generate all candidates" — ask "how early can I reject one." Get the UNDO exactly right, or later branches see corrupted state. Next: two pointers & sliding window — O(n²) scans → O(n) passes.