Backtracking explained: how it works, code and examples

What problem backtracking solves

Some problems ask for every arrangement that satisfies a set of rules, or for any one such arrangement: place 8 queens so that none attack each other, fill a Sudoku grid, list all subsets of a set that sum to a target, find all ways to split a string into dictionary words. There is no clever formula; you have to search. Trying every complete combination blindly is far too slow, but most partial combinations are already invalid after a few choices.

Backtracking checks the rules after every single choice. When a partial solution breaks a rule, it abandons that whole branch of the search tree at once and goes back to try the next option.

The idea in plain words

1. If the current partial solution is complete, record it.
2. Otherwise, for each possible next choice: if the choice is allowed, make it (choose).
3. Recurse to extend the solution further (explore).
4. Undo the choice, so the next option starts from the same state (unchoose).

The search space is a tree: the root is the empty solution, each level adds one choice, and the leaves are complete candidates. Backtracking is depth-first search on this tree, and pruning means cutting off subtrees that cannot contain a solution.

Worked example: 4-Queens

Place 4 queens on a 4 × 4 board, one per row, so that no two share a column or a diagonal. Columns are numbered 0 to 3.

Continuing the search finds the only other solution, 2, 0, 3, 1, which is the mirror image of the first.

Python implementation

Keep sets of used columns and diagonals so that each safety check is O(1). On one diagonal row - col is constant, and on the other row + col is constant.

def solve_n_queens(n):
    solutions, cols = [], []
    used_cols, diag1, diag2 = set(), set(), set()

    def place(row):
        if row == n:
            solutions.append(cols.copy())   # copy, not the live list
            return
        for col in range(n):
            if col in used_cols or row - col in diag1 or row + col in diag2:
                continue                    # prune: square is attacked
            cols.append(col)                # choose
            used_cols.add(col); diag1.add(row - col); diag2.add(row + col)
            place(row + 1)                  # explore
            cols.pop()                      # unchoose
            used_cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)

    place(0)
    return solutions

print(solve_n_queens(4))       # [[1, 3, 0, 2], [2, 0, 3, 1]]
print(len(solve_n_queens(8)))  # 92

The same template generates all subsets and all permutations:

def subsets(items):
    result, current = [], []

    def go(i):
        if i == len(items):
            result.append(current.copy())
            return
        current.append(items[i]); go(i + 1); current.pop()   # take items[i]
        go(i + 1)                                            # skip items[i]

    go(0)
    return result

def permutations(items):
    result, current, used = [], [], [False] * len(items)

    def go():
        if len(current) == len(items):
            result.append(current.copy())
            return
        for i, x in enumerate(items):
            if not used[i]:
                used[i] = True; current.append(x)
                go()
                used[i] = False; current.pop()

    go()
    return result

print(subsets([1, 2, 3]))
# [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
print(permutations([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

For plain subsets and permutations in real code, itertools.combinations and itertools.permutations are faster. Write your own backtracking when you need to prune with problem-specific rules.

Time and space complexity

Backtracking cannot beat the size of the output: if you must list n! permutations, you need at least n! steps. Pruning only helps by skipping branches that produce nothing.

Variants and common mistakes

• Forgetting to undo: if the state is not restored after the recursive call, later branches see stale choices.
• Appending the live list: result.append(current) stores a reference that later changes; append current.copy().
• Duplicates in the input: sort the items and skip an item equal to the previous one at the same depth to avoid duplicate subsets or permutations.
• Stop at the first solution: return True from the recursion and stop the loops when one solution is enough, as in a Sudoku solver.
• Better ordering: try the most constrained choice first (for Sudoku, the empty cell with the fewest candidates). This often shrinks the tree dramatically.

When to use it and real-world uses

• Constraint satisfaction: Sudoku, crosswords, map coloring, timetabling and exam scheduling.
• SAT solvers and Prolog-style logic engines are built on backtracking search with strong pruning.
• Regular expression engines in many languages, including Python's re, use backtracking; badly written patterns can backtrack exponentially ("catastrophic backtracking").
• Interview problems: subsets, permutations, combination sum, N-Queens, word search in a grid, palindrome partitioning, generate parentheses, letter combinations of a phone number.