Backtracking — Explained with Examples

In this tutorial, you'll learn about Backtracking. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

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