TLDR: Backtracking is "Recursion with Undo." You try a path, explore it deeply, and if it fails, you undo your last decision and try the next option. It explores the full search space but prunes invalid branches early, making it far more efficient than brute force.

---

📖 Solving a Maze by Walking Backward

When solving a maze, you don't try every possible path simultaneously. You pick one corridor, follow it until you hit a dead end, then backtrack to the last junction and try the next corridor.

Backtracking algorithms apply exactly this logic to decision trees:

1. Choose a candidate.
2. Recurse deeper with that candidate applied.
3. If the recursion fails or the constraint is violated, undo the choice and try the next one.

This differs from brute force: you don't generate all combinations and filter at the end. You prune the moment you know a branch can't work.

---

🔢 The Backtracking Template: Choose → Explore → Un-Choose

Every backtracking solution fits this skeleton:

def backtrack(state, choices):
    if is_solution(state):
        record(state)
        return

    for choice in choices:
        if is_valid(state, choice):
            apply(state, choice)          # CHOOSE
            backtrack(state, next_choices(state, choice))  # EXPLORE
            undo(state, choice)           # UN-CHOOSE

The critical line is undo — this is what makes it backtracking rather than plain recursion. Without undo, earlier choices would permanently pollute later branches.

---

⚙️ N-Queens: A Step-by-Step Walkthrough

Place N queens on an N×N chessboard so no two attack each other (no shared row, column, or diagonal).

4×4 Board:

The algorithm never reaches invalid states — it prunes at the moment a constraint is violated.

def solve_n_queens(n):
    results = []
    board = [-1] * n  # board[row] = col of queen in that row

    def backtrack(row):
        if row == n:
            results.append(board[:])
            return
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col
                backtrack(row + 1)
                board[row] = -1   # undo

    def is_safe(board, row, col):
        for r in range(row):
            c = board[r]
            if c == col or abs(c - col) == row - r:
                return False
        return True

    backtrack(0)
    return results

---

🧠 When to Use Backtracking

---

⚖️ Time Complexity and Pruning Importance

Without pruning, N-Queens has $O(N!)$ candidates. With pruning (column + diagonal checks), the effective branching factor drops dramatically:

• $N=8$: 8! = 40,320 raw nodes; with pruning ~1,965 nodes explored
• $N=12$: brute force = 479M; pruned ≈ 320K nodes

Effective pruning is the difference between unusable and practical. The earlier you detect a constraint violation, the more of the search tree you skip.

---

📌 Key Takeaways

• Backtracking = recursion + undo. The undo step is what allows the algorithm to explore multiple branches from the same state.
• Template: Choose → Explore → Un-Choose.
• Pruning makes backtracking practical: reject invalid states as early as possible.
• N-Queens is the canonical example: place by row, prune on column and diagonal conflict.
• Use backtracking for constraint satisfaction, combinations, and permutations — not for shortest-path problems (use DP or BFS there).

---

🧩 Test Your Understanding

1. What is the difference between backtracking and depth-first search?
2. In the N-Queens Python solution, what does board[row] = -1 on the undo line accomplish?
3. Why does early pruning dramatically reduce the number of nodes explored?
4. You want all permutations of [1, 2, 3]. Which part of the backtracking template handles swapping and unswapping?

---

🔗 Related Posts

• Exploring Different Types of Binary Trees
• Understanding KISS, YAGNI, and DRY
• What are Hash Tables?