Backtracking — Explained with Examples

Backtracking incrementally builds candidates and abandons them when they cannot lead to a valid solution, pruning the search space.

Backtracking is a brute-force algorithmic technique that explores all potential solutions but stops exploring a path as soon as it determines the path cannot lead to a valid solution (pruning). It uses recursion with three steps: choose (make a decision), explore (recursively try from that state), and unchoose (undo the decision to try alternatives). Classic problems include N-Queens, Sudoku solver, maze solving, and generating permutations.

Think of backtracking like solving a maze with a ball of string. You walk forward, trailing string. When you hit a dead end, you follow the string back to the last intersection and try a different path. You never re-enter passages you already know are dead ends.

Backtracking is effectively DFS on a state-space tree. Its time complexity is often exponential (O(2ⁿ) or O(n!)), but pruning can make it practical for moderate-sized inputs.

# N-Queens: place N queens on N×N board without conflicts
def solve_n_queens(n):
    def is_safe(board, row, col):
        # Check column
        for i in range(row):
            if board[i] == col:
                return False
            # Check diagonals
            if abs(board[i] - col) == abs(i - row):
                return False
        return True

    def backtrack(row):
        if row == n:
            solutions.append(board[:])
            return
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col
                backtrack(row + 1)
                # No explicit unchoose needed — board[row] is overwritten

    solutions = []
    board = [-1] * n
    backtrack(0)
    return solutions

solutions = solve_n_queens(4)
print(f"Found {len(solutions)} solutions")
for sol in solutions:
    print(sol)  # [1, 3, 0, 2], [2, 0, 3, 1]

Backtracking is the method of last resort when no polynomial-time algorithm exists. It is related to depth-first search and the branch-and-bound optimization technique.

Recursion, DFS, Divide and Conquer, Greedy Algorithm

Recursion for Backtracking