L32 · Backtracking II — Constraint Grids

Series: LeetCode — From Basics to Interview-Ready · Session 32 / 65 · Phase 1 · Core patterns

Why this session exists

Session 31 gave you the skeleton. This session is about the only thing that makes it usable on real constraint problems: pruning. N-Queens on an 8×8 board has 8^8 placements if you enumerate blindly — about 16 million — and 4,426,165,368 if you allow any square for any queen. With one pruning rule, that collapses to a few thousand nodes and finishes instantly.

The rule is stated in four words: prune before you recurse. Not inside the recursive call, not at the base case, but in the loop before you commit to a choice. Checking validity at the top of the recursive function still explores the doomed node; checking it in the parent's loop means the doomed subtree never comes into existence. The difference is one level of the tree, which is a multiplicative factor.

The second theme is state restoration. In session 31 the state was a list you popped. Here it is a board you mutate, plus auxiliary sets you add to. Every mutation on the way in needs an exact undo on the way out, and "exact" is doing work in that sentence.

Blank-file warm-up

Five minutes, empty file, no notes. Write the pruning shape from memory:

for choice in choices:
    if not valid(choice): continue    # prune BEFORE recursing
    place(choice)
    bt(depth + 1)
    unplace(choice)

Then the specific one: for N-Queens, write the three sets that make validity O(1). Not the loop that scans the board — the sets.

What wobbles: the diagonal identities. Getting r - c and r + c backwards, or using the same expression for both, gives a queen placement that looks plausible and is wrong.

Pattern anatomy

The shape of problem that summons constraint backtracking: fill a fixed structure position by position, subject to rules that can be checked as you go, and stop at the first complete filling — or enumerate all of them. The critical property is that a partial filling can be provably dead before it is complete. That is what makes pruning possible and DP impossible.

The invariant: at every recursion depth, the partially filled structure satisfies every constraint among the cells filled so far. You never descend into an already-invalid state. That is the entire difference between this and brute force.

The template:

def solve(depth):
    if depth == total:
        return True                    # complete and, by the invariant, valid
    for choice in candidates(depth):
        if not is_valid(choice, depth):
            continue                   # PRUNE: subtree never created
        place(choice, depth)
        if solve(depth + 1):
            return True                # first solution wins: unwind immediately
        unplace(choice, depth)         # exact undo of place
    return False                       # every choice at this depth failed

Note the boolean return. When you want one solution — Sudoku, Word Search — returning True up the stack short-circuits the entire remaining search. When you want all solutions — N-Queens returning every board — you return nothing and let the loop run to completion. That distinction changes the function signature, so decide which one the problem wants before writing a line.

N-Queens, with O(1) validity:

def solveNQueens(n):
    res = []
    cols, diag, anti = set(), set(), set()
    board = [-1] * n                   # board[r] = column of the queen in row r
 
    def bt(r):
        if r == n:
            res.append(["." * c + "Q" + "." * (n - c - 1) for c in board])
            return
        for c in range(n):
            if c in cols or (r - c) in diag or (r + c) in anti:
                continue               # prune before placing
            cols.add(c); diag.add(r - c); anti.add(r + c)
            board[r] = c
            bt(r + 1)
            cols.discard(c); diag.discard(r - c); anti.discard(r + c)
    bt(0)
    return res

The three sets are the whole trick. r - c is constant along a north-west-to-south-east diagonal; r + c is constant along a north-east-to-south-west anti-diagonal. Membership in a set is O(1), so validity is three hash lookups instead of an O(n) board scan. That takes the per-node cost from O(n) to O(1) at every one of the thousands of nodes.

Placing one queen per row is itself a pruning decision, and a large one — it encodes "no two queens share a row" structurally so you never generate a violating placement at all. Encoding a constraint into the shape of the search is always better than checking it.

Word Search, where the board itself carries the visited state:

def exist(board, word):
    R, C = len(board), len(board[0])
 
    def bt(r, c, i):
        if i == len(word):
            return True
        if r < 0 or r >= R or c < 0 or c >= C or board[r][c] != word[i]:
            return False
        board[r][c] = "#"              # mark visited in place
        found = (bt(r + 1, c, i + 1) or bt(r - 1, c, i + 1)
                 or bt(r, c + 1, i + 1) or bt(r, c - 1, i + 1))
        board[r][c] = word[i]          # restore the ORIGINAL character
        return found
 
    return any(bt(r, c, 0) for r in range(R) for c in range(C))

board[r][c] = word[i] on restore, not some remembered variable — because we only got here after confirming board[r][c] == word[i], so the original character is exactly word[i]. That is a small correctness argument worth stating aloud; it shows you are reasoning about the invariant rather than pattern-matching.

The cue

You are looking at a constraint-grid backtracking problem when the statement contains one of these tells:

1. A fixed-size board plus placement rules. N-Queens, Sudoku, Crossword filling, Magic Squares. The board dimension is small — 8, 9, 16 — because the search is exponential.
2. "Return the / a valid configuration" or "determine whether a solution exists". A single answer, not an enumeration, which means the boolean short-circuit form.
3. "Each row / column / region must contain exactly one of each". Distinctness constraints over overlapping groups. That is precisely what set-based O(1) validity is for.
4. Path-finding through a grid where cells cannot be reused within one path. Word Search, Rat in a Maze, Unique Paths III. The mark-and-restore is the defining move.
5. Suspiciously small constraints combined with an exponential-looking question. n <= 9, board is 9x9, word.length <= 15. That bound is the problem-setter telling you exponential search is intended.

The negative cue: if the same subproblem recurs with the same state, and you are asked for a count or an optimum rather than an actual configuration, you want memoisation or DP, not backtracking. Constraint problems generally do not have overlapping subproblems, because the state includes the entire board.

Guided solve

N-Queens. Place n queens on an n × n board so that no two attack each other. Return all distinct solutions.

Begin with the search-space reduction, because this is the part that separates a good answer from a working one.

Naive framing: choose n squares out of n². For n = 8 that is 4.4 billion combinations. Unusable.

First reduction: exactly one queen per row. Two queens in the same row always attack, so any valid solution has one per row. Encode that structurally by making row the recursion depth. Search space drops to n^n — 16 million for n = 8. Better, still bad.

Second reduction: prune on column and both diagonals before placing. Now most of those 16 million branches die at depth 2 or 3 and are never expanded. For n = 8 the actual node count is in the low thousands.

Say all three steps out loud in an interview. The interviewer is grading the reasoning, not the code, and "one queen per row" is a structural insight while "check the diagonals" is bookkeeping.

Now the validity check. The naive version scans the board:

def is_valid_slow(board, r, c):
    for prev_r in range(r):
        prev_c = board[prev_r]
        if prev_c == c:
            return False
        if abs(prev_r - r) == abs(prev_c - c):
            return False
    return True

That is O(r) per check, so O(n) at the deepest levels. Correct, and acceptable if you say you would optimise it. The set version is O(1):

Two queens share a north-west diagonal exactly when r1 - c1 == r2 - c2, because moving one step down-right increments both r and c and leaves the difference unchanged. They share an anti-diagonal exactly when r1 + c1 == r2 + c2, because down-left increments r and decrements c. So maintaining a set of occupied r - c values and a set of occupied r + c values makes both checks a hash lookup.

Derive those two identities at the whiteboard rather than reciting them. If you get r - c and r + c swapped the code still runs, produces boards, and those boards are wrong — a queen and its diagonal neighbour both pass the check. Verify with n = 4: the two known solutions are columns [1, 3, 0, 2] and [2, 0, 3, 1]. If your code returns anything else, or returns more than two, the diagonals are wrong.

The full solution is the template above. Trace the first branch for n = 4: place at (0,0). Row 1 rejects c=0 (column), c=1 (diagonal, since 1−1 = 0 = 0−0). Accepts c=2. Row 2 rejects c=0, c=1 (anti-diagonal 2+1 = 3 = 1+2), c=2, c=3 (diagonal 2−3 = −1 = 1−2). All four columns rejected — the branch dies at depth 2, having never expanded rows 3. That death is the pruning doing its job.

Solo timed

Fifteen minutes each, timer visible, no editorial until it fires.

• N-Queens — start with the O(n) scan validity check if that is what comes out first, then rewrite it with the three sets. Doing both is more valuable than jumping straight to the optimal one.
• Word Search — the visited marking is in the board itself. Think about what value to restore and why you already know it without storing it.
• Sudoku Solver — return type is boolean. Ask yourself why, and what happens if you return nothing.

If all three land early, do Combination Sum II, which combines this session's pruning with session 31's duplicate handling.

Common failure modes

Checking validity at the top of the recursive call instead of in the parent's loop. The doomed node is still created, still gets a stack frame, still runs its own base-case checks. You lose a whole multiplicative level of the tree. Prune in the loop.

Restoring the wrong value. In Word Search, restoring board[r][c] = "" or a remembered-but-stale variable corrupts the board for every sibling branch. The correct restore is word[i], and the reason you know that is the earlier equality check.

Forgetting to undo one of several state pieces. N-Queens mutates three sets and one array. Undoing two of the three sets produces a phantom constraint that silently eliminates valid solutions — the output is short, not wrong-looking, so it is hard to spot.

Returning True from a base case when the problem wants all solutions. Short-circuiting terminates the search after the first answer. Conversely, not returning anything in Sudoku means the solver keeps searching after it has already solved the board and eventually unwinds all its work.

Swapping the diagonal identities. r - c for the main diagonal, r + c for the anti-diagonal. Swapped, the code runs and returns wrong boards. Verify against n = 4 having exactly two solutions.

Using a list instead of a set for occupancy. if c in cols_list is O(n) and negates the entire optimisation. It looks identical in Python, which is why it slips through.

Complexity

N-Queens: O(n!) upper bound. Row 0 has n choices, row 1 has at most n−1 (the column constraint alone removes one), and so on, giving n! as a bound on the leaves. The diagonal constraints prune far more than that, so the real node count is dramatically lower — for n = 8 the search touches a few thousand nodes and finds 92 solutions — but there is no clean closed form for the pruned count, so n! is what you state. Copying each solution board costs O(n²), so producing all solutions is O(n! · n²).

Space: O(n) auxiliary — three sets holding at most n entries each, the board array of length n, and a recursion stack of depth n. The output is O(solutions · n²), which is required rather than overhead.

Sudoku: O(9^m) where m is the number of empty cells, since each empty cell has at most 9 candidates. This bound is almost comically loose — real puzzles have enough constraint propagation that the solver finishes in milliseconds — but it is the honest worst case. Space is O(m) for the recursion depth plus O(1) for the fixed 9×9 board.

Word Search: O(R · C · 4^L) where L is the word length. You may start at any of R·C cells, and from each position there are up to 4 directions at each of L steps. The first direction is actually 4 and subsequent ones are 3 (you cannot immediately backtrack into the marked cell), so 4·3^(L−1) is tighter, but 4^L is the standard statement. Space is O(L) for the recursion stack.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

N-Queens enters the queue today. If you had to look up which diagonal is r - c, log it hint — that identity should be derivable in ten seconds by taking one step down-right and observing what stays constant.