Algorithms

Backtracking Algorithms: Solving Constraint Problems with Recursive Search

Backtracking is a systematic way to search through all possible configurations of a problem. It builds solutions one step at a time, and the moment a partial solution violates a constraint, it backtracks and tries a different path — pruning the search tree without having to enumerate every leaf.

Published June 30, 2026

Some problems have no efficient formula. The only way to solve them is to try possible solutions and check whether they work. Brute force tries every possibility, which is often too slow. Backtracking is smarter: it builds a solution incrementally and abandons any partial solution the moment it can be proven that it cannot lead to a valid answer. The result is a search that explores only the promising parts of the solution space.

The Backtracking Template

Every backtracking algorithm follows the same three-step loop at each level of the search:

Choose: Select the next candidate to add to the partial solution. This is typically an item from a set of available options: a number for a Sudoku cell, a queen placement for the next row, or the next character in a string.
Explore: Recurse into the next level of the search with the candidate added to the current partial solution. If the recursion returns (either with success or failure), move on.
Unchoose: Remove the candidate from the partial solution (backtrack) and try the next candidate. This restores the state to what it was before the "choose" step, enabling a clean try of the next option.

In pseudocode:

def backtrack(state, candidates):
    if is_complete(state):
        record(state)
        return

    for candidate in candidates:
        if is_valid(state, candidate):
            state.add(candidate)          # Choose
            backtrack(state, next_candidates(state))  # Explore
            state.remove(candidate)       # Unchoose

N-Queens: A Complete Implementation

The N-queens problem asks: place N queens on an N x N chessboard such that no two queens attack each other. Queens attack along rows, columns, and diagonals. For N=8, there are 92 solutions out of the 4.4 billion ways to place 8 pieces on 64 squares. Backtracking finds them all efficiently by placing one queen per row and immediately checking column and diagonal conflicts before recursing.

def solve_n_queens(n: int) -> list:
    results = []
    queens = []  # queens[row] = column where queen is placed

    def is_safe(row: int, col: int) -> bool:
        for r, c in enumerate(queens):
            if c == col:
                return False  # Same column
            if abs(r - row) == abs(c - col):
                return False  # Same diagonal
        return True

    def backtrack(row: int) -> None:
        if row == n:
            # All queens placed; record the board
            board = []
            for r, c in enumerate(queens):
                board.append("." * c + "Q" + "." * (n - c - 1))
            results.append(board)
            return

        for col in range(n):
            if is_safe(row, col):
                queens.append(col)       # Choose
                backtrack(row + 1)       # Explore
                queens.pop()             # Unchoose

    backtrack(0)
    return results


solutions = solve_n_queens(4)
for board in solutions:
    for row in board:
        print(row)
    print()

# Output (2 solutions for N=4):
# .Q..
# ...Q
# Q...
# ..Q.
#
# ..Q.
# Q...
# ...Q
# .Q..

Pruning: Why Backtracking Beats Brute Force

The is_safe check is the pruning step. When a column or diagonal conflict is detected, the entire subtree rooted at that placement is skipped. For N=8, the brute force approach would examine 8⁸ = 16.7 million leaf nodes. The backtracking search with diagonal pruning examines only a few hundred thousand nodes — a reduction of roughly 98%.

Stronger pruning means more of the tree is cut. In Sudoku, detecting a cell that has no valid digits remaining immediately prunes the entire subtree without placing anything further. The quality of the constraint check directly determines how fast the algorithm runs.

Classic Backtracking Problems

Problem	State	Constraint	Complexity
N-queens	Queen column per row	No shared column or diagonal	O(N!) with pruning much faster
Sudoku solver	Digit per empty cell	No repeated digit in row, column, or 3x3 box	O(9^m) where m = empty cells; pruning critical
Permutations	Ordered selection of elements	Each element used at most once	O(n!) solutions, O(n) space for path
Subset sum	Subset of a list of integers	Elements sum to target	O(2^n) worst case
Word search	Path through a character grid	Adjacent cells, no revisit, spell the word	O(4^L) where L = word length

A Note on Complexity

Backtracking does not escape exponential worst-case complexity. It is a smarter version of exhaustive search, not a polynomial-time algorithm. The key insight is that pruning eliminates large subtrees early, so the effective search space is often many orders of magnitude smaller than the theoretical worst case. When an efficient polynomial algorithm exists (such as dynamic programming for subset sum with bounded integers), prefer it. Backtracking shines for constraint satisfaction problems where no such shortcut is known.