Backtracking: Systematic Search with Pruning (Permutations, N-Queens, Sudoku)

Some problems require searching through *all* possible configurations — every permutation, every subset, every way to place queens on a board — to find valid ones or the best one. Brute force enumerates them all, which is astronomically expensive. Backtracking enumerates them *smartly*: it builds candidates one choice at a time and, the instant a partial candidate is doomed, abandons that entire branch and backs up to try something else. This pruning is the difference between feasible and impossible on combinatorial problems.

In plain words — the maze analogy

Think of backtracking as navigating a maze. At every intersection you pick a passage and walk it. The moment you hit a dead end you don't restart from the entrance — you *retreat* to the last intersection and try the next unexplored passage. Brute force would teleport back to the entrance after every dead end and try a completely new path from scratch. Backtracking's efficiency comes from retreating only as far as necessary, then resuming from there. The algorithm works on exactly this logic: it explores a tree of decisions, backs up when a branch is provably fruitless, and continues with siblings.

The mental model: a pruned search tree

Picture the space of all candidate solutions as a tree: the root is 'nothing chosen yet', each level is one decision, and leaves are complete candidates. A brute-force DFS visits every leaf. Backtracking is that same DFS, but at each internal node it checks whether the partial candidate is still viable — and if not, it prunes the whole subtree beneath it, never visiting those leaves at all. On problems with strong constraints, pruning eliminates the vast majority of the tree, which is why backtracking can solve puzzles a naive enumeration never could.

root: []
├── choose 1 → [1]
│   ├── choose 2 → [1,2]
│   │   └── choose 3 → [1,2,3] ✓ RECORD
│   └── choose 3 → [1,3]
│       └── choose 2 → [1,3,2] ✓ RECORD
├── choose 2 → [2]
│   ├── choose 1 → [2,1]
│   │   └── choose 3 → [2,1,3] ✓ RECORD
│   └── choose 3 → [2,3]
│       └── choose 1 → [2,3,1] ✓ RECORD
└── choose 3 → [3]
    ├── choose 1 → [3,1]
    │   └── choose 2 → [3,1,2] ✓ RECORD
    └── choose 2 → [3,2]
        └── choose 1 → [3,2,1] ✓ RECORD

6 leaves = 3! = 6 permutations.
Each level eliminates already-used elements (implicit pruning).

The universal template

Nearly every backtracking solution is the same recursive shape — choose, explore, un-choose:

1. Base case: if the current partial solution is complete, record it (or return success).
2. Iterate choices: for each candidate next choice at this step:
3. a. Prune: skip the choice if it violates a constraint (this is the whole point — the earlier and more aggressively you prune, the faster it runs).
4. b. Choose: apply the choice to the partial solution.
5. c. Explore: recurse to the next step.
6. d. Un-choose (backtrack): undo the choice, restoring state so the next candidate starts clean.

function backtrack(partial, choices, result):
    if isComplete(partial):
        result.add(copy(partial))   // copy! don't store a reference
        return

    for choice in choices:
        if violatesConstraint(partial, choice):
            continue                // PRUNE — skip this branch entirely

        apply(partial, choice)      // CHOOSE
        backtrack(partial, remaining(choices, choice), result)  // EXPLORE
        undo(partial, choice)       // UN-CHOOSE — restore state

That un-choose step is what the name refers to and where beginners stumble: after exploring a branch you must *restore* the state exactly as it was, so sibling branches aren't corrupted by leftovers. Forgetting to undo is the signature backtracking bug.

Worked example 1: generating all subsets

Generate all subsets of [A, B, C]. At each step, for each element not yet decided, make a binary choice: include it or skip it. This produces 2³ = 8 subsets.

root []
├── include A → [A]
│   ├── include B → [A,B]
│   │   ├── include C → [A,B,C] ✓
│   │   └── skip C    → [A,B]   ✓
│   └── skip B  → [A]
│       ├── include C → [A,C]   ✓
│       └── skip C    → [A]     ✓
└── skip A  → []
    ├── include B → [B]
    │   ├── include C → [B,C]   ✓
    │   └── skip C    → [B]     ✓
    └── skip B  → []
        ├── include C → [C]     ✓
        └── skip C    → []      ✓

8 leaves = 2³ subsets.

1. Start with partial = [], index = 0.
2. At index 0 (A): branch 'include A' → partial=[A], recurse with index 1.
3. At index 1 (B): branch 'include B' → partial=[A,B], recurse with index 2.
4. At index 2 (C): branch 'include C' → partial=[A,B,C] — base case, record [A,B,C]. Backtrack.
5. Un-choose C → partial=[A,B]. Branch 'skip C' — base case, record [A,B]. Backtrack.
6. Un-choose B → partial=[A]. Branch 'skip B', recurse similarly. And so on.

Worked example 2: N-Queens (where pruning shines)

Place N queens on an N×N board so none attack each other. Backtracking places one queen per row: for the current row, try each column, but *prune* any column already threatened by a queen in a previous row (same column or diagonal). If no column works, back up to the previous row and move its queen.

Board cols: 0 1 2 3
Row 0: try col 0 → place Q
       . Q . .    row 1: col 0 — same col, PRUNE
       . Q . .    row 1: col 1 — diagonal, PRUNE
       . Q . .    row 1: col 2 — safe, place Q
              row 2: col 0 — diagonal from (1,2), PRUNE
              row 2: col 1 — same col as (0,1)... wait, (0,1) was pruned
              (backtrack: row 1 col 2 exhausted, try col 3 → Q at (0,0),(1,3))
              row 2: col 1 — safe, place Q at (2,1)
                     row 3: all cols pruned (attacked) → BACKTRACK
              row 2: col 2 — col attacked by (1,3)? No. safe.
                     row 3: col 0 — safe → place Q → solution: (0,0),(1,3),(2,1),(3,0)?
                            Check: (0,0)↔(3,0) same col! PRUNE row3 col0
                     row 3: col 1 — (2,1) same col PRUNE
                     ...
(continue — first valid N=4 solution: cols [1,3,0,2] and [2,0,3,1])

For N=8: 92 valid solutions out of 8^8 = 16,777,216 raw board fillings.
Pruning cuts this to ~thousands of nodes explored.

The pruning is dramatic — most partial placements are abandoned immediately — turning an impossible brute force (Nᴺ board fillings) into something that solves N=8 instantly and much larger boards in reasonable time.

Variations: constraint satisfaction, Sudoku, combination sum

• Sudoku: For each empty cell, try digits 1–9, pruning any digit already present in the same row, column, or 3×3 box. The constraint check eliminates most candidates immediately, making real puzzles fast despite the exponential worst case.
• Combination sum: Find all combinations of numbers summing to a target. Prune branches where the running sum already exceeds the target — sorting the choices first means you can break early when a choice already overshoots.
• Word search / path problems: DFS on a grid marking cells visited (the 'choose' step), then unmark on backtrack. The visited set is the state being restored.
• Graph coloring: Assign colors to graph nodes so no adjacent nodes share a color. Try each color per node, prune if a neighbor already has that color.

Under the hood: complexity and the role of pruning

The honest framing: backtracking is worst-case exponential — it's for problems that are genuinely combinatorial, where no polynomial algorithm is known (many are NP-hard, Lesson 29). Its value isn't beating that worst case but *avoiding* it in practice through pruning. Two amplifiers: stronger pruning (detect doomed branches earlier) and better ordering (try the most-constrained choices first — the 'most constrained variable' heuristic — so failures surface fast and prune more). When a problem has overlapping subproblems, memoizing backtracking states blends it into DP.

Common pitfalls

• Forgetting to un-choose. The state must be restored after each branch, or siblings inherit corrupted state. This is *the* backtracking bug — every choose needs a matching un-choose.
• Weak or late pruning. Backtracking without effective constraint checks degenerates into full brute force. Prune as early as constraints allow.
• Storing a reference instead of a copy. When you record a solution, record a copy (e.g., list.copy() or new ArrayList(current)). If you store a reference to the mutable partial solution, all recorded solutions will reflect its final state — usually empty.
• Mutating shared state without care. Appending to a result list, then recursing, then forgetting to pop; or recording a reference to a mutable partial solution instead of a copy (so all recorded 'solutions' end up identical/empty).
• Ignoring choice ordering. Trying the most-constrained options first can prune far more of the tree — order matters for speed even when it doesn't affect correctness.
• Using backtracking where DP fits. If subproblems overlap, plain backtracking re-explores them; add memoization or switch to DP.

When to use backtracking

• Enumerate all valid configurations: permutations, subsets, combinations — any exhaustive listing problem.
• Constraint-satisfaction puzzles: N-Queens, Sudoku, crosswords, map coloring — problems with constraints that let you prune hard.
• Decision problems with exponential search spaces where no greedy or DP approach applies — when the search space is genuinely combinatorial.
• When n is small enough (typically n ≤ 20–25) that even a well-pruned exponential algorithm finishes in time.
• Avoid when subproblems overlap (use DP instead), when n is large (backtracking won't scale), or when the problem has a greedy structure that guarantees optimality.

Practice problems

• Subsets II (with duplicates): Given a list that may contain duplicates, generate all unique subsets. Sort first, then skip duplicate choices at the same recursion level.
• Word Search: Given a 2D grid of characters and a word, determine if the word exists as a path (any direction, no cell reused). Classic DFS + backtrack with a visited set.
• Sudoku Solver: Fill a partially-completed Sudoku board. For each empty cell try digits 1–9, prune via row/column/box constraints, backtrack on failure.

Key takeaways

• Backtracking builds candidates incrementally and prunes doomed partial solutions, exploring a search tree via DFS.
• The template is choose → explore → un-choose; the un-choose (state restoration) is essential and error-prone.
• Pruning is the whole value — it's what separates tractable backtracking from hopeless brute force.
• Worst case is exponential (it targets combinatorial, often NP-hard problems); good pruning and choice ordering keep it practical.
• Use it to enumerate or search combinatorial spaces (permutations, subsets, constraint puzzles); add memoization when subproblems overlap.

The final technique lesson drops from search strategies to the metal — manipulating individual bits for speed and elegance: bit manipulation. Drill backtracking templates in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play