Skip to main content

Backtracking

Backtracking performs depth-first search over a decision tree. It makes a choice, updates state, explores, and restores the exact previous state before trying the next choice.

def search(state):
    if is_solution(state):
        record(state.copy())
        return
    for choice in candidates(state):
        if not feasible(state, choice):
            continue
        apply(state, choice)
        search(state)
        undo(state, choice)

Design checklist​

  1. Define what one search-tree level means.
  2. Decide whether choices are positions, values, edges, or assignments.
  3. Make the solution condition and output ownership explicit.
  4. Pair every mutation with an exact undo, including early-return paths.
  5. Add only pruning rules proven unable to remove a valid required solution.

Pruning types​

  • Feasibility: a constraint is already violated.
  • Symmetry: equivalent choices would generate duplicate states.
  • Bounds: even the best possible completion cannot improve the incumbent.
  • Memoization: the same residual state has already been solved; this begins to overlap with dynamic programming.

Complexity​

Worst-case time is often exponential or factorial because output or search-space size is itself that large. Pruning improves explored instances, not necessarily the worst-case class. Stack depth is usually proportional to the number of decisions, excluding stored outputs.

Use backtracking when a witness or complete enumeration is required and the constraints can reject partial assignments early.

Source​