Backtracking is one of those concepts that sounds intimidating until you realize it's just a recursive search with a "cleanup" phase. I've seen a lot of developers struggle here because they try to treat it like a standard loop. In reality, it's more like exploring a maze: you walk down a path until you hit a wall, then you physically step back to the last junction to try a different turn.

Wait, isn't this just recursion?

Essentially, yes, but with a specific intent. Standard recursion often just breaks a problem down into smaller pieces (like calculating a factorial). Backtracking, however, is about state management. You make a choice, recurse to see if that choice leads to a solution, and if it doesn't, you explicitly undo that choice before trying the next one.

I like to think of it as a "Try, Check, Undo" loop. If you don't do the "Undo" part, your program will carry the baggage of failed attempts into the next branch of the search, and you'll end up with a mess of incorrect data.

Where exactly does the "backtracking" happen in the code?

The magic happens immediately after the recursive call. Look at this example where we're trying to find all possible paths through a grid from the top-left to the bottom-right, avoiding obstacles (marked as 1).

def find_paths(grid, r, c, path, visited):
    rows, cols = len(grid), len(grid[0])
    
    # Base case: We reached the destination
    if (r, c) == (rows - 1, cols - 1):
        print(f"Found path: {path + [(r, c)]}")
        return

    # Mark the current cell as visited and add to path
    visited.add((r, c))
    path.append((r, c))

    # Explore neighbors (Down, Up, Right, Left)
    for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0 and (nr, nc) not in visited:
            find_paths(grid, nr, nc, path, visited)

    # --- THE BACKTRACK ---
    # We've explored all paths from this cell. 
    # Now we remove it so other potential paths can use it.
    path.pop()
    visited.remove((r, c))

If I didn't include path.pop() and visited.remove((r, c)), the first path the algorithm found would "lock" all those cells forever. Any other potential routes would see those cells as already visited and simply give up. That's the crux of backtracking: leaving the room exactly how you found it.

Why do I keep getting "maximum recursion depth exceeded"?

This usually happens because your base case is missing, or your state isn't actually changing, leading to an infinite loop. In backtracking, you must ensure that every recursive call moves you closer to a termination point or consumes a limited resource.

In the grid example above, the visited set prevents the algorithm from bouncing back and forth between two cells forever. If you forget to track visited nodes in a graph or grid, you'll hit that recursion limit in milliseconds. I always suggest printing the current state (like print(f"Visiting {r,c}")) at the start of the function when you're debugging. If you see the same coordinates repeating in a cycle, you've found your leak.

How do I handle "pruning" to make it faster?

Pure backtracking is essentially brute force. If the search space is huge, your code will be slow. "Pruning" is just a fancy word for "stopping a path as soon as you know it's a dead end."

Imagine you're solving a puzzle where the sum of numbers must be exactly 100. If your current path sum is already 105, there's no point in adding more numbers. You should return immediately. I've seen this reduce runtime from minutes to milliseconds in complex constraint problems. Always ask yourself: "Is there a condition that makes this path impossible?" If yes, kill the branch early.

📋 Practical Task

The N-Queens Constraint Solver

Your task is to implement a backtracking algorithm to solve the "N-Queens" problem. The goal is to place N chess queens on an N×N chessboard so that no two queens threaten each other. This means no two queens can share the same row, column, or diagonal.

Requirements:

• Write a function solve_n_queens(n) that returns a list of all valid board configurations.
• Represent the board as a list of strings, where 'Q' is a queen and '.' is an empty space.
• Use a backtracking pattern: place a queen in a row, check if it's valid, recurse to the next row, and then remove the queen (backtrack) to try the next column.
• Challenge: Use sets to track which columns and diagonals are already occupied to avoid checking the entire board every time you place a queen.

Example Output for n=4:

[
 ['.Q..', 
  '...Q', 
  'Q...', 
  '..Q.'],
 
 ['..Q.', 
  'Q...', 
  '...Q', 
  '.Q..']
]