Backtracking & Recursive Search

Backtracking is what brute force looks like when it grows up. The naive approach to "find all valid arrangements" builds every possible arrangement and throws away the bad ones at the end. Backtracking builds arrangements one choice at a time, checks as it goes, and the instant a partial choice cannot possibly lead anywhere, it abandons that whole branch and steps back. It is a disciplined walk through a tree of decisions: make a choice, explore what follows, then undo the choice and try the next one.

That undo is the heartbeat of the pattern, and the single most common place people get it wrong. You mutate some shared state to record a choice, recurse, and then you must faithfully un-mutate it on the way back up, or every later branch inherits a decision it never made. Choose, explore, un-choose. Miss the last step and the whole search quietly corrupts.

Choose, explore, un-choose

Generating every permutation of a list is the skeleton in its purest form. Add an element to the current path, recurse on what remains, then pop it back off before trying the next.

def permutations(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:                  # a complete arrangement
            result.append(path[:])         # copy, the path keeps mutating
            return
        for i in range(len(remaining)):
            path.append(remaining[i])                      # choose
            backtrack(path, remaining[:i] + remaining[i+1:])  # explore
            path.pop()                                     # un-choose
    backtrack([], nums)
    return result

For [1, 2, 3] it yields all six orderings. Notice the path[:] copy when recording a result, because path itself is a single list mutated throughout the search, and the path.pop() that restores it. That pop is the backtrack. Without it, the second branch would start from a dirty path and the output would be nonsense.

In the wild: solving Sudoku

The same skeleton, plus one crucial ingredient, solves real constraint problems. A Sudoku solver walks empty cells, tries each digit, recurses, and backtracks when it hits a wall. The ingredient that makes it fast rather than astronomically slow is pruning: before recursing on a digit, check that it does not already violate a row, column, or box. That check kills doomed branches before they explode.

def solve(board):                          # board is 9x9, 0 means empty
    def ok(r, c, v):
        for i in range(9):
            if board[r][i] == v or board[i][c] == v:
                return False
            if board[3*(r//3) + i//3][3*(c//3) + i%3] == v:
                return False
        return True
    def backtrack():
        for r in range(9):
            for c in range(9):
                if board[r][c] == 0:
                    for v in range(1, 10):
                        if ok(r, c, v):
                            board[r][c] = v            # choose
                            if backtrack():            # explore
                                return True
                            board[r][c] = 0            # un-choose
                    return False                       # no digit fits, dead end
        return True                                    # no empty cell left, solved
    backtrack()
    return board

It is the permutation skeleton in disguise: choose a value for a cell, explore, and undo it (board[r][c] = 0) when the branch fails. What turns an impossible 9^81 search into something that finishes instantly is the ok check pruning the tree. That is the real lesson of backtracking, and the same shape solves N-Queens, word search in a grid, and the constraint solvers inside schedulers and dependency resolvers, where a package manager tries version combinations and backs out of conflicts.

A backtracking decision tree building length-three binary strings by choosing 0 or 1 at each step; any branch that would place two 1s in a row, like 11, is pruned immediately, so five valid strings survive and the doomed branches are cut before they are ever explored.

The trigger

The problem asks for all solutions, or any valid configuration, of something built from a sequence of choices under constraints. Permutations, combinations, subsets, board-filling, path-finding through a maze of decisions. If you can describe it as "make a choice, then solve the rest," and choices can fail, backtracking is the frame.

Where it shows up

  • Enumeration: all permutations, combinations, subsets, or parenthesizations.
  • Constraint satisfaction: Sudoku, N-Queens, graph coloring, cryptarithms.
  • Path and parsing search: word search in a grid, regular-expression matching, splitting a string into valid pieces.

Where it bites

Two failures dominate. Forgetting to undo state, the missing pop or reset, so branches leak into each other. And skipping the pruning, which leaves a correct but hopelessly slow search: the difference between a Sudoku solver that returns in a blink and one that never finishes is entirely the early constraint check. Deep recursion can also overflow the stack on large instances.

When it is the wrong tool

If the branches revisit the same subproblem, pure backtracking recomputes it exponentially, and you should add memoization, which is exactly the door into Dynamic Programming. If a proven Greedy rule or a direct construction yields a valid answer, enumerating the whole tree to find one is wasteful. And if the space is enormous with no structure to prune on, exact backtracking may simply be intractable, and heuristics, randomized search, or approximation become the realistic path.

Its neighbors

Backtracking is really Depth-First Search on an implicit tree of choices, so it shares everything with graph traversal. It becomes Dynamic Programming the moment you memoize overlapping subproblems, and it leans on plain recursion as its control structure. Pruning, its make-or-break feature, is a Greedy-flavored judgment about which branches are worth entering.

References