Backtracking: Solving Constraint Problems

Backtracking is a systematic way of trying all possible solutions to a problem and abandoning partial candidates that cannot possibly lead to a valid solution. It is deeply tied to recursion and depth-first search, and it is the go-to approach for constraint satisfaction problems like N-Queens, sudoku, and generating permutations.

How Backtracking Works

Every backtracking algorithm follows the same high-level pattern: make a choice, recurse on the remaining subproblem, and if that path fails, undo the choice (backtrack) and try the next option. This is often called “choose, explore, un-choose.”

def backtrack(candidate, state):
    if is_solution(candidate):
        output(candidate)
        return
    for next_candidate in generate_candidates(candidate, state):
        if is_valid(next_candidate, state):
            make_choice(next_candidate, state)
            backtrack(next_candidate, state)
            undo_choice(next_candidate, state)

The three core components are:

• Goal test — has the current path produced a complete valid solution?
• Candidate generation — what are the possible next steps from here?
• Constraint check — does the partial solution still satisfy all rules?

Without the constraint check (pruning), backtracking degenerates into a brute-force enumeration. Effective pruning is what separates efficient backtracking from exponential blowup.

N-Queens

Place N queens on an N×N chessboard so that no two queens attack each other. Queens attack along rows, columns, and diagonals.

def solve_n_queens(n):
    cols = set()
    diag1 = set()  # r + c
    diag2 = set()  # r - c
    result = []
    board = [["."] * n for _ in range(n)]

    def backtrack(row):
        if row == n:
            result.append(["".join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row + col) in diag1 or (row - col) in diag2:
                continue
            board[row][col] = "Q"
            cols.add(col)
            diag1.add(row + col)
            diag2.add(row - col)
            backtrack(row + 1)
            board[row][col] = "."
            cols.remove(col)
            diag1.remove(row + col)
            diag2.remove(row - col)

    backtrack(0)
    return result

The key insight for N-Queens is using sets to track occupied columns and diagonals. The O(1) membership test turns the constraint check into a constant-time operation. Two queens share a positive diagonal when r + c is equal, and a negative diagonal when r - c is equal — this trick eliminates the need for a 2D board scan at each step.

For N = 8 there are 92 solutions. Without the diagonal pruning, the search space is 8⁸ = 16 million board arrangements. With pruning, the algorithm visits only about 15,720 nodes — a reduction of three orders of magnitude. Symmetry breaking further reduces the count: fixing the first queen to the first half of the first row eliminates reflected and rotated duplicates, cutting the search space roughly in half.

Sudoku Solver

Fill a 9×9 grid so that each row, column, and 3×3 box contains digits 1–9 exactly once.

def solve_sudoku(board):
    def is_valid(r, c, ch):
        for i in range(9):
            if board[r][i] == ch:
                return False
            if board[i][c] == ch:
                return False
            if board[3 * (r // 3) + i // 3][3 * (c // 3) + i % 3] == ch:
                return False
        return True

    def backtrack():
        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    for ch in "123456789":
                        if is_valid(r, c, ch):
                            board[r][c] = ch
                            if backtrack():
                                return True
                            board[r][c] = "."
                    return False
        return True

    backtrack()
    return board

The backtracking solver finds the first empty cell, tries each digit, and recurses. When no digit fits, it backtracks. For a standard Sudoku puzzle, the solver typically finishes in milliseconds. Expert-level puzzles with minimal clues may take longer — but the worst case is still bounded by the branching factor, which the constraint checks keep low.

In practice, Sudoku solvers benefit from a simple optimization: choose the cell with the fewest remaining candidates first (minimum remaining values heuristic). This dramatically reduces the branching factor early in the search. A Sudoku with 17 clues (the minimum possible) that takes 10 seconds with naive cell ordering can finish in under 100 milliseconds with MRV.

Generating Permutations

Generate all permutations of a given array without duplicates.

def permute(nums):
    result = []

    def backtrack(path, used):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            path.append(nums[i])
            used[i] = True
            backtrack(path, used)
            path.pop()
            used[i] = False

    backtrack([], [False] * len(nums))
    return result

Permutation generation is the simplest backtracking problem: no constraint checks beyond “have I used this element yet?” The total number of permutations is N!, and backtracking visits exactly N! leaves. When the input contains duplicates, sort the array first and skip an element if it matches the previous element and the previous has not been used in the current branch — this ensures each unique permutation is generated exactly once.

Pruning Strategies

Pruning is the heart of backtracking. The more constraints you can check early, the fewer nodes you explore.

Constraint propagation goes beyond simple pruning. Algorithms like AC-3 (arc consistency) propagate the effects of a choice through the entire constraint graph, reducing domains of unassigned variables before the next recursive call. This extra work at each node often pays off by eliminating whole subtrees. In the context of general constraint satisfaction problems, AC-3 iterates over arcs (variable pairs connected by a constraint) and removes values from domains that have no supporting value in the neighboring domain, repeating until the domains stabilize.

Advanced Techniques: Branch and Bound

Branch and bound extends backtracking to optimization problems. Instead of finding any solution, we seek the solution that maximizes or minimizes an objective function. The algorithm maintains the best solution found so far and computes an optimistic bound for each partial solution. If the bound shows that no extension of the current partial solution can beat the best known solution, that branch is pruned.

The classic example is the traveling salesman problem. At each step, the bound might be the cost of the current partial tour plus the minimum possible cost to connect the remaining cities. The tighter the bound, the more pruning occurs. Branch and bound is the workhorse of operations research, used in everything from airline crew scheduling to supply chain optimization.

Complexity

Backtracking has exponential worst-case time complexity, but in practice the constraint checks prune the search space dramatically.

• Time: O(b^d) worst case — b is branching factor, d is maximum depth
• Space: O(d) — the recursion depth and the path being built

The actual number of nodes visited is almost always far lower than the worst case because constraints eliminate large branches early. For many practical problems, backtracking with good pruning is not just acceptable but optimal.

Applications

• Constraint satisfaction: Sudoku, crosswords, logic puzzles
• Combinatorial optimization: Traveling salesman (with branch and bound), knapsack
• Parsing: Recursive descent parsers for context-free grammars
• Pathfinding: Maze solving with backtracking
• AI: Planning and scheduling under constraints
• Cryptography: Solving substitution ciphers by matching letter frequency constraints
• Scheduling: Assigning resources to tasks while respecting time and dependency constraints
• Circuit design: Automatic placement and routing of VLSI components

Backtracking is also the engine behind SAT solvers and constraint programming libraries. The DPLL algorithm that powers most modern SAT solvers is backtracking with unit propagation and pure literal elimination — essentially the same pattern with domain-specific optimizations. Modern CDCL (Conflict-Driven Clause Learning) solvers extend DPLL with clause learning, non-chronological backtracking, and restarts, enabling them to solve industrial SAT instances with millions of variables.

When to Use Backtracking

Reach for backtracking when the problem asks for all solutions, requires satisfying multiple simultaneous constraints, and involves making a sequence of choices. If the problem has overlapping subproblems, dynamic programming may be a better fit. If any solution will do, greedy algorithms or local search may be faster.

The litmus test: can you define a partial solution and check whether it can possibly lead to a valid final solution? If yes, backtracking can solve it.

FAQ

What is the difference between backtracking and brute force? Brute force enumerates all possible solutions without pruning. Backtracking uses constraint checks to abandon partial solutions early, reducing the search space. For N-Queens, brute force generates all 16 million board arrangements, while backtracking visits only about 15,000 nodes.

How do I choose between backtracking and dynamic programming? Use backtracking when you need all solutions satisfying constraints and subproblems do not overlap. Use dynamic programming when the problem has overlapping subproblems and optimal substructure, because DP avoids recomputing the same subproblems.

Can backtracking be parallelized? Yes. Each branch of the search tree is independent and can be explored in parallel. The fork-join model works well — spawn parallel tasks at the top few levels of the recursion tree and collect results when they complete. However, the overhead of parallelism may not pay off for small instances.

What is the minimum remaining values heuristic? MRV selects the variable with the fewest remaining legal values at each step. This reduces the branching factor early in the search, dramatically shrinking the overall search tree. In Sudoku, picking the cell with the fewest candidate digits first is an application of MRV.

How do I handle duplicate elements in permutation generation? Sort the input first, then skip an element if it is the same as the previous element and the previous element has not been used in this recursive branch. This ensures each unique permutation is generated exactly once.

Internal Links

Recursion Guide — Algorithm Design Patterns — Graph Algorithms Guide