Backtracking

Backtracking is recursion with one extra discipline: at each step you make a choice, recurse to see where that choice leads, and if it leads nowhere useful, you undo the choice and try the next option. It's how you actually solve "generate all ___" and "find an arrangement that satisfies these constraints" problems — permutations, combinations, subsets, Sudoku, and the classic interview problem this lesson works through end to end: N-Queens. In Python, the "undo" step usually reads as naturally as list.append() followed later by .pop() — choose, recurse, un-choose.

The Try, Check, Undo Pattern

Every backtracking solution follows the same three-step shape at each level of recursion:

• Try: make a choice — place a queen, pick a number, include an element.
• Check: recurse into the rest of the problem with that choice in place. If the recursive call finds a full valid solution, record it (or return, depending on whether you want one answer or all of them).
• Undo: before trying the next choice at this level, remove the choice you just made, restoring the state to what it was before you tried it. This is the step people forget, and it's the one that makes backtracking work — without it, choices from an abandoned branch leak into the next branch you try.

Worked Example: N-Queens

The problem: place N queens on an N x N chessboard so that no two queens attack each other — no two queens share a row, a column, or a diagonal. We'll place one queen per row, working row by row from the top, and at each row try every column until one doesn't conflict with any queen already placed above it. placement is a plain Python list acting as our "choose/un-choose" state: placement[row] holds the column of the queen placed in that row, and we literally append to it when trying a column and pop from it when undoing that try.

def solve_n_queens(n):
    solutions = []
    placement = []  # placement[row] = column index of the queen in that row

    def is_safe(row, col):
        # A new queen at (row, col) is safe if no earlier-placed queen shares
        # its column, or either diagonal.
        for placed_row, placed_col in enumerate(placement):
            if placed_col == col:
                return False                                    # same column
            if abs(placed_col - col) == abs(placed_row - row):
                return False                                    # same diagonal
        return True

    def place(row):
        if row == n:
            solutions.append(placement.copy())        # base case: every row has a queen -> full solution
            return

        for col in range(n):
            if is_safe(row, col):
                placement.append(col)     # TRY: place the queen (choose)
                place(row + 1)         # CHECK: recurse to the next row
                placement.pop()           # UNDO: remove it before trying the next column

    place(0)
    return solutions

print(len(solve_n_queens(4)))  # 2 solutions for a 4x4 board

Tracing solve_n_queens(4): the search tries a queen at row 0, column 0 (placement = [0]), then looks for a safe column in row 1. Columns 0 and 1 conflict (column/diagonal), so it tries column 2 (placement = [0, 2]). Now row 2 has no safe column at all — every column conflicts with one of the two placed queens — so the for loop inside place(2) finds nothing safe and simply returns without recursing further. Control unwinds back to row 1, which pops its own choice (placement back to [0]) and tries column 3 instead (placement = [0, 3]). That eventually leads to the first full solution, [1, 3, 0, 2] (queen in row 0 at column 1, row 1 at column 3, row 2 at column 0, row 3 at column 2). Row 0's loop then also pops its own choice and tries column 1, which — by symmetry — finds the second solution, [2, 0, 3, 1].

Time complexity: O(N!) in the worst case — the first queen has N column choices, the second has at most N−1 remaining, and so on, before pruning is even considered; pruning cuts this enormously in practice but the bound without deeper analysis is still factorial. Space complexity: O(N) — the placement list and the recursion depth are both bounded by the number of rows.

Pruning: The Reason Backtracking Is Usable At All

Look again at is_safe() — it's called before appending a queen, not after finishing the whole board. That's pruning: reject a bad choice the moment it's known to be bad, instead of continuing to build on it and discovering the failure much later (or never, if you forgot to check at all and just generated every full arrangement and filtered afterward).

The Same Pattern, More Generally

N-Queens is one instance of a shape that covers a large family of interview problems, and in Python they all share the same append/recurse/pop skeleton:

# Bonus: permutations, same pattern, much shorter than N-Queens
def permutations(nums):
    result = []
    path = []
    used = [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):
            result.append(path.copy())
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])      # choose
            backtrack()
            path.pop()                # un-choose
            used[i] = False

    backtrack()
    return result

print(permutations([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Time complexity: O(n * n!) — there are n! permutations, and building each one by copying path costs O(n). Space complexity: O(n) for the recursion depth and the used/path state, not counting the O(n * n!) needed to store every output permutation.