Backtracking: The Algorithm of "No Regrets" (But Many U-Turns)

Prologue: The Maze Runner

Imagine you are in a maze. There is no map. How do you find the exit?

1. Pick a path (Left).
2. Walk until you hit a wall.
3. Go back to the intersection.
4. Pick the next path (Right).

This simple behavior—going forward, hitting a dead end, and coming back—is the essence of Backtracking. It is a Refined Brute Force. It tries everything, but it's smart enough to stop early if a path is clearly wrong.

I remember the first time I encountered the N-Queen problem in an algorithm challenge. "Place 8 Queens on an 8x8 chessboard so no two queens attack each other." My first thought was: "Can't I just try all combinations?" So I wrote a brute-force solution. I ran it. It froze. Three minutes passed. No answer. I checked the calculator—there were over 4.4 billion combinations. That's when I realized: I needed to learn the art of giving up early.

That's Backtracking.

The Struggle: Wait, Isn't This Just DFS?

When I first learned Backtracking, I was confused. "Isn't this just DFS (Depth-First Search)?" It looked similar—recursive calls, stack-based, going deep. But there's a subtle difference. DFS says, "Go wherever you can go." Backtracking says, "If this path looks hopeless, don't even bother."

That difference is Pruning. Without pruning, it's dumb brute force. With pruning, it's elegant backtracking. Once I understood this, everything clicked.

Key Concept: Pruning (The Art of Giving Up)

The difference between a dumb Brute Force and smart Backtracking is Pruning.

• Brute Force: Tries every single possible combination, even the ones that make no sense.
• Backtracking: Checks a condition ("Is this promising?"). If it fails, it cuts off that entire branch of probability.

Analogy: Finding a Date

You want to find a partner who is (1) Kind, (2) Smart, (3) Likes Pizza.

• Brute Force: You date 8 billion people on Earth one by one.
• Backtracking: You meet someone.
  • Are they Kind? No. → Stop immediately (Prune). Don't ask if they are smart. Next person.
  • Are they Kind? Yes. → Are they Smart? No. → Stop (Prune).
  • Are they Kind? Yes. → Smart? Yes. → Like Pizza? Yes. → Found!

Pruning saves you from wasting time on hopeless paths. This is the core philosophy of Backtracking.

State Space Tree: The Mental Model

Every problem can be visualized as a giant tree.

• Root Node: Empty board. No decisions made yet.
• Branches: Your choices (Option A, B, C...).
• Leaf Nodes: Final result (Success or Failure).

Backtracking traverses this tree Depth-First. But it doesn't blindly visit every node. At each node, it asks: "Is this path promising?"

• Yes: Continue to child nodes.
• No: Return to parent immediately (This is Pruning).

The quality of your isPromising() function determines the algorithm's performance. A good pruning function can reduce a 4.4 billion search space to a few thousand.

Classic Problem: N-Queen

The "Hello World" of Backtracking. Goal: Place N Chess Queens on an N×N board so no two queens attack each other.

The Algorithm

1. Start at Row 0.
2. Try placing a Queen in each Column (0 to N-1).
3. Check Constraint: Is this safe? (No queen in same column or diagonals).
   • Yes: Place it. Move to Row + 1 (Recursive Call).
   • No: Don't place it. Try next column.
4. If we reach Row N, we found a solution!
5. If we are stuck (can't place anywhere in this row), return (Backtrack) to previous row and move that queen.

Code Example (Python)

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

    def is_safe(row, col):
        for prev_row in range(row):
            prev_col = board[prev_row]
            # Check column or diagonals
            if prev_col == col or abs(prev_col - col) == abs(prev_row - row):
                return False
        return True

    def backtrack(row):
        if row == n:
            results.append(list(board))  # Found one!
            return

        for col in range(n):
            if is_safe(row, col):
                board[row] = col
                backtrack(row + 1)  # Go deeper
                board[row] = -1  # Backtrack

    backtrack(0)
    return results

The key here is is_safe(). This function performs the "promising check". If placing a queen in a certain cell conflicts with already-placed queens, we don't even try it. That's pruning.

And the other critical line: board[row] = -1. When the recursive call returns, we must restore the state (Clean up). Otherwise, it affects the next search. This is the most common mistake junior developers make. I spent three hours debugging this once.

Real World Application: Sudoku Solver

How does a computer solve Sudoku instantly? Backtracking.

1. Find an empty cell.
2. Try putting '1'.
3. Is it valid? (Row/Col/Box check).
   • Yes: Move to next empty cell.
   • No: Try '2'.
4. If '1' to '9' all fail, it means the previous cell was wrong. Backtrack!

It fills the board, realizes "Oops, this makes the last cell impossible," erases it, and tries a different number. It does this thousands of times per second.

def solve_sudoku(board):
    empty = find_empty(board)
    if not empty:
        return True  # No empty cells = Done!
    row, col = empty

    for num in range(1, 10):
        if is_valid(board, num, (row, col)):
            board[row][col] = num  # Try

            if solve_sudoku(board):  # Recurse
                return True

            board[row][col] = 0  # Failed! Backtrack

    return False  # 1-9 all failed -> Go back

board[row][col] = 0 is the Backtracking step. Without this line, the algorithm gets stuck forever at a dead end.

Advanced: Bitmask Optimization (10x Faster)

I once got "Time Limit Exceeded" on an N-Queen problem. The array-based approach had limits. That's when I learned Bitmask optimization. At first, I thought, "Bit operations? Too hard." But once I tried it, it was incredibly fast—over 10 times faster than the array approach.

def solve(row, cols, d1, d2):
    if row == N:
        return 1

    count = 0
    # Calculate available positions using bitwise operations
    available = ~(cols | d1 | d2) & ((1 << N) - 1)

    while available:
        # Get the rightmost 1 bit (position)
        curr = available & -available
        available -= curr

        # Recursive call (bit shift for diagonal handling)
        count += solve(row + 1, cols | curr, (d1 | curr) << 1, (d2 | curr) >> 1)

    return count

This approach minimizes memory access and maximizes CPU's ALU (Arithmetic Logic Unit) usage. I didn't understand it at first, but once I realized "cols = column occupancy", "d1 = left diagonal occupancy", "d2 = right diagonal occupancy", the code made sense. After experiencing this optimization, I fell in love with bit manipulation.

Real World: Regex and ReDOS Attack

We use Backtracking every day without knowing it. Regular Expression engines. When matching a*b, the engine tries to match as many as as possible (Greedy), then if there's no b, it backs off (Backtrack) one a at a time and retries.

But here's the danger. If you write a pattern like (a+)+b, the Backtracking cases explode exponentially (Exponential Blowup). An attacker sends aaaaaaaaa... and your server's CPU hits 100% and freezes. This is ReDOS (Regular Expression Denial of Service) attack.

This actually caused Cloudflare to show 502 Bad Gateway errors worldwide. The backtracking-based regex engine went haywire. After learning this, I became cautious with regex. "Does this pattern cause excessive backtracking?" That's why Go and Rust's regex engines use Thompson's Construction (NFA) instead of backtracking, guaranteeing $O(N)$ time.

Backtracking vs DFS

They are often confused because they look similar (both use Recursion).

Feature	DFS	Backtracking
Goal	Reach target or traverse all	Find valid configuration
Focus	Connectivity / Reachability	Feasibility / Combinatorics
Pruning	Rarely prunes	Heavily prunes invalid branches
Example	Maze Pathfinding, Components	Sudoku, N-Queen, Puzzles

Essentially, Backtracking is DFS with Constraints and Pruning.

Fun History: Gauss vs The Queens

The 8-Queen problem was first published in 1848 by chess composer Max Bezzel. But it became famous when the "Prince of Mathematics", Carl Friedrich Gauss, took interest in 1850.

Gauss tried to solve it by hand. Back then, there were no computers. He used his brain (the original CPU). He found 72 solutions. Later, it was proven that there are 92 distinct solutions (or 12 if you exclude rotations/reflections).

Even the greatest mathematician missed a few because he didn't have Backtracking! This shows why algorithmic thinking is a superpower. We can solve in milliseconds what took Gauss weeks.

After learning this story, I felt comforted. "If Gauss couldn't find them all, it's okay that I can't." But I also realized: "But I have a computer." If we understand and implement algorithms properly, we can surpass even Gauss.

The Limit: P vs NP

Backtracking is great but not a silver bullet. In the worst case (if pruning doesn't help much), you must check all combinations anyway—$O(2^N)$ or $O(N!)$. These are called NP-Complete problems (like Traveling Salesman Problem).

If N exceeds 100, the answer won't come before the universe ends. In such cases, you must abandon perfect solutions and use "Good Enough" approaches like Genetic Algorithms or Metaheuristics. Give up perfection (Optimum), gain speed.

I accepted this trade-off and realized: "I don't need to solve every problem perfectly."

Backtracking vs Dynamic Programming (DP)

I confused these two when learning. "Both use recursion, what's different?" But after organizing, the purpose is completely different.

Feature	Backtracking	DP
Purpose	Find all possible solutions	Find optimal solution or count
Approach	Try and go back if wrong	Store and reuse subproblem answers
Memory	Stack only. Low	Table creation. High
Examples	N-Queen, Maze	Fibonacci, Knapsack, LCS

Backtracking is "Pathfinding". DP is "Optimization". The 0/1 Knapsack can be solved by both, but usually DP is used for performance. However, if weight W is huge and N is small, Backtracking might be faster. That's the beauty of algorithms.

Summary

1. Backtracking = DFS + Pruning. Pruning is everything.
2. The one who gives up quickly wins. Don't walk down hopeless paths.
3. Don't forget State Restoration (Undo). One line like board[row] = -1 saves the algorithm.
4. Regex engines use Backtracking. Beware of ReDOS attacks.
5. If perfect answer is too slow, find approximation. Give up perfectionism, gain speed.

"Life is like Backtracking. Sometimes you have to step back to find the right way forward."