Backtracking

Explore choices, and undo them when they hit a dead end. · 7 min read

Backtracking is recursion that explores choices and undoes them. At each step you try an option, recurse, and if it leads nowhere you backtrack — rewind the choice and try the next. It's how you solve mazes, N-Queens, Sudoku, and generate permutations.

Permutation example

To generate permutations, choose one unused item for the current slot, recurse, then unchoose it before trying the next item:

def permute(path, remaining):
    if not remaining:
        output(path); return
    for x in remaining:
        path.append(x)
        permute(path, remaining - {x})
        path.pop()

For n items there are n! complete arrangements, so the output alone is factorial-sized. Backtracking is powerful, but it is not magic.

def solve(state):
    if complete(state):
        record(state); return
    for choice in options(state):
        apply(choice)     # try
        solve(state)      # recurse
        undo(choice)      # backtrack

Each path from root to leaf in that decision tree is one full attempt; the branching is exactly the recursion tree from the last lesson.

Interactive visualization: The decision tree backtracking explores — step through it frame by frame on this page.

Pruning example

In N-Queens, you do not place a queen and wait until the whole board is full to check. The moment a queen attacks another queen, that partial board can never become valid, so the recursion returns immediately. That early return is pruning: fewer branches, same correct answer.