Recursion & backtracking

The idea

Imagine navigating a maze: you pick a path, walk until you hit a dead end, and then step backward (backtrack) to the last junction to try a different route.

In code, this means we make a choice, recursively explore what happens next, and then "un-choose" (undo) that choice so we can try the next option. If we realize early that a choice is invalid, we stop exploring it entirely—this is called "pruning" the search tree.

See it work

How it works

We write a recursive function that builds up a solution. At each step, we push our state forward (Choose), recurse (Explore), and then revert our state (Un-choose). The implicit call stack tracks our current path.

def solve_n_queens(n):
    board = []
    
    def is_valid(row, col):
        # Check column and diagonals against previously placed queens
        for r, c in enumerate(board):
            if c == col or abs(c - col) == abs(r - row):
                return False
        return True

    def backtrack(row):
        if row == n:
            return True  # Found a valid configuration!
            
        for col in range(n):
            if is_valid(row, col):
                board.append(col)      # 1. Choose
                if backtrack(row + 1): # 2. Explore
                    return True
                board.pop()            # 3. Un-choose (Backtrack)
                
        return False  # No valid placement found in this row

    backtrack(0)
    return board

Cost

The time is factorial because we explore combinatorially, but pruning keeps it manageable; space is tiny, just the depth of the recursion stack.

Watch out for

• Forgetting to "un-choose" (pop or reset state) after returning from the recursive call.
• Doing too much work by failing to prune invalid paths early enough.
• Creating a new deep copy of the state at every step instead of mutating a single shared state, which causes memory to blow up.

Worked example

Solving 4-Queens. We place a queen at (row 0, col 0). Then we try row 1. col 0 and col 1 are attacked, but col 2 is safe, so we place one there. At row 2, every column is attacked! We've hit a dead end. We backtrack to row 1, remove the queen at col 2, and try col 3 instead.