Backtracking II — Constraint Grids

Review boundary and corrected contracts

Pruning is valid only when no extension can repair the partial violation. It does not make DP impossible. The Word Search code restores the board after both success and failure, assumes a nonempty rectangular board and reserves its marker outside the input alphabet. N-Queens uses distinct column and diagonal constraints.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Prune before recursing rather than after, design O(1) constraint checks with sets instead of scans, and restore mutated board state exactly on the way back out.

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

Why this session exists

A naive placement search is exponential. Restricting to one queen per row gives nⁿ assignments; column and diagonal checks prune partial assignments before exploring their descendants. No fixed wall-clock speedup follows from that structural fact.

Checking before calling avoids constructing an invalid child frame. Checking immediately upon entry can prune the same subtree with one extra call, so it is not in itself an asymptotic improvement.

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. Identify which state must survive a successful solve and which is temporary search state. Undo temporary marks and active constraints exactly; a scratch suffix that is overwritten before use is governed by a weaker invariant.

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: keeping two distinct diagonal keys consistent. Swapping their names everywhere is harmless. Checking with one expression but adding/removing with another, or using the same expression for both sets, breaks the constraint.

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 makes pruning possible; memoization can still help if a sufficient state repeats.

The invariant: at every recursion depth, the partially filled structure satisfies every constraint among the cells filled so far. The N-Queens loop never recurses into an invalid placement. A guard-on-entry version briefly creates a frame but rejects it before expansion; both are exhaustive searches pruned by the same constraints.

This schematic template leaves a successful assignment in place, as an in-place Sudoku solver should. Its helpers and total are problem-specific; it is not a standalone executable solver. A boolean query like Word Search must restore temporary visited marks even on success.

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

The boolean is an internal success signal: it lets a caller stop after finding one solution. A public Sudoku API may return nothing and mutate the board, while its helper returns True/False. For enumeration, the N-Queens helper appends a board and returns to the loop, without propagating a stop signal; the public function returns the list of boards.

N-Queens, with expected O(1) validity checks:

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. Set membership is expected O(1) for these integer keys, so each candidate validity check uses three lookups instead of an O(r) scan of prior rows. Each non-leaf call still loops over n candidate columns: the entire call is not O(1).

The active board state at depth r is board[:r]. Entries from r onward are scratch space: each is overwritten before any complete board is copied. Therefore the three occupancy sets must be undone, but board[r] does not need resetting to −1 in this implementation. That is a prefix invariant, not a restoration bug.

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. Here it removes row-conflicting candidates before generation; the benefit is the reduced candidate space, not a universal ranking of every structural encoding.

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 a sufficient state repeats, memoization can help, including for existence queries. Do not cache Word Search by (r,c,i) alone: two visits can have different used-cell sets and therefore different legal continuations. Include that constraint state or prove it irrelevant. A large state may make memoization impractical, but pruning does not make DP impossible.

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 distinct squares out of n², ignoring attacks. For n=8 this is C(64,8)=4,426,165,368 candidate sets before validity checks.

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. The surviving partial placements shrink sharply. Instrumenting the exact function at n=8 gives 2,057 bt entries, including 92 completed boards. It performs 15,720 candidate-column checks: node count and candidate-check count are different metrics.

Say all three steps out loud under a tight review. A reviewer 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 both identities rather than reciting their names. Consistently swapping which set stores each expression leaves the algorithm unchanged. Using r-c in both sets omits anti-diagonal attacks; using inconsistent expressions for checking and insertion also fails. 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.

For Sudoku, maintain nine row sets, nine column sets and nine box sets. Cell (r,c) uses box index 3*(r//3) + c//3; its legal digits are 1…9 minus the union of those three occupied sets. Initialize from the givens and reject a duplicate given before searching. After choosing a digit, update the board and all three sets; on failure undo all four, while on success retain the solved board.

Minimum remaining values (MRV) chooses an empty cell with the fewest legal digits. Zero candidates proves failure; one candidate forces that choice but still needs assignment and propagation. MRV often cuts the search tree, at the cost of recomputing or maintaining candidate sets. It is a heuristic, not an instant-runtime guarantee. A public in-place solveSudoku can return None while its recursive helper returns a boolean.

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 — make the recursive helper return a success boolean, even if the public API returns nothing and fills the board in place. Decide which mutations survive success and which must be undone on failure.

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

Common failure modes

Confusing check placement with pruning depth. Checking an invalid candidate in the parent avoids one doomed call; checking immediately on child entry rejects the same subtree after that call. It does not add a full expanded level. Deferring validity until complete assignments is the change that explores doomed descendants.

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 an active-state undo. N-Queens must remove the occupied column and both diagonal keys. A forgotten key creates a phantom constraint and drops solutions. The scratch board suffix need not be cleared because only board[:r] is active and the next choice overwrites board[r].

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.

Dropping or inconsistently using a diagonal family. A consistent exchange of r-c and r+c is correct. Replacing every r+c with r-c is not: anti-diagonal collisions are no longer checked. Verify each returned board for both families, not only the output count.

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.

Myth: Backtracking is just brute force with recursion, so it is always exponential and there is nothing to be done about the constant.

Why: Backtracking remains a form of exhaustive search, but sound pruning rejects a partial state whose violations cannot be repaired by extension. At n=8, the row-by-row unpruned tree has sum(8^d,d=0…8)=19,173,961 calls; the column-and-two-diagonal-pruned function has 2,057. These counts compare explicit search trees, not the location of the same validity check and not elapsed time. Worst-case search and output can still be exponential.

Steps 1: Because the constraints of these problems are local and checkable on partial assignments, a partial state can be proven dead before it is complete.

Steps 2: Because a dead partial state cannot lead to any valid completion, every node in its subtree is wasted work.

Steps 3: Checking validity in the parent prevents a rejected candidate’s call frame. Checking immediately on entry prevents the same descendants; the accepted partial states are the same.

Steps 4: The validity check runs for each candidate column. Replacing an O(r) scan with expected O(1) lookups reduces this repeated work, but copying output boards still costs O(n²) each.

Steps 5: Encoding one queen per row removes row conflicts by construction; column and diagonal filters then constrain the remaining choices. Compare candidate spaces rather than assuming every structural encoding must be faster.

Steps 6: The exact n=8 pruned function has 2,057 calls and 92 solutions. The unpruned row-assignment tree has 19,173,961 calls by a geometric sum; to return those same 92 boards it must validate complete assignments. This is a derived comparison, not a timed run of all unpruned assignments.

Picture: You are filling in a crossword in pen. Before writing each letter you check whether it breaks any word that already crosses this square. If it does, you never write it — you do not write it, discover the contradiction three squares later, and erase back. The check happens at the pen, not at the contradiction.

Trigger: Fires on a fixed board plus placement rules plus a small dimension: N-Queens, Sudoku, grid word search, any 'fill this subject to constraints'.

Name: Check validity in the parent loop (prune early)

Gain: Rejects the candidate without a child frame; invalid descendants are avoided, just as with an immediate child-entry guard

Cost: The validity function needs the candidate and current state, so it can require more parameter plumbing

Name: Check validity at the top of the recursive call

Gain: Simpler signature; one guard clause handles bounds and validity together, which is why Word Search is usually written this way

Cost: Each rejected candidate costs a call frame; it does not create another expanded subtree if the guard returns immediately

Name: O(n) board scan for validity

Gain: No auxiliary state to maintain or restore, so no undo bugs; obviously correct and quick to write under pressure

Cost: Each candidate check scans up to n prior rows instead of using expected constant-time occupancy lookups; actual timing depends on the implementation

Pick: Use a parent-loop check when it expresses placement constraints clearly, as in N-Queens. An entry guard naturally combines bounds, character matching and visited checks in Word Search. There is no universal branching-factor crossover at 4; both arrangements can prune at the same logical depth.

Complexity

N-Queens: ignoring diagonals, depth r has at most P(n,r)=n!/(n−r)! valid column prefixes. Summing these gives O(n!) accepted states. The exact implementation scans n columns per non-leaf state, giving the safe search bound O(n·n!) under expected constant-time set operations. If S boards are returned, add O(S·n²) to construct their strings. Thus O(n·n! + S·n²), and since S≤n!, O(n²·n!) is a loose all-output upper bound. At n=8 the measured counts are 2,057 states, 15,720 checks and 92 boards.

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 is a loose fixed-board search bound, not a millisecond guarantee; propagation, clue pattern and variable ordering change actual work. 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.

Self-check (answer follows each question).

Q: What does a parent-loop validity check save compared with checking immediately on child entry?

A: It avoids the rejected child’s call and stack frame. Both checks prevent that child’s descendants, so they explore the same accepted partial states; this is not removal of a full expanded level.

Q: Which expression is constant along a main (north-west to south-east) diagonal, and which along an anti-diagonal?

A: r − c is constant along the main diagonal, because a down-right step increments both r and c. r + c is constant along the anti-diagonal, because a down-left step increments r and decrements c.

Q: In Word Search, what value do you restore to board[r][c] on the way out, and how do you know it without storing it?

A: word[i]. You only descended past the guard because board[r][c] == word[i] was already true, so the original character is recoverable from the word itself.

Q: Why does the Sudoku helper propagate a boolean while the N-Queens enumeration helper does not propagate success?

A: The boolean tells Sudoku callers to stop and retain the successful board; its public API may return None. N-Queens must continue after recording a solution, so its helper returns to the loop without a stop signal, and the public function ultimately returns all boards.

Q: You use a Python list instead of a set for the occupied-columns check. What happens?

A: Nothing visible — the code is still correct — but membership becomes O(n) instead of O(1), which multiplies the cost of every node in the search and can turn a passing solution into a TLE at larger n.

Q: What candidate spaces do one-queen-per-row encoding and diagonal pruning each eliminate?

A: Row-per-depth selects one column for each row, reducing complete candidates from C(n²,n) arbitrary square sets to n^n row assignments. Column and diagonal checks then reject conflicting partial assignments before completing them. Neither observation proves one optimization universally larger: compare the same metric and n.

Stretch: true

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.

• Prune before you recurse. Checking in the parent's loop deletes the subtree; checking at the top of the call still pays for the frame.

• Encode constraints structurally where possible. One queen per row as the recursion depth beats any runtime row check.

• r − c is the main diagonal, r + c is the anti-diagonal. Three sets make N-Queens validity O(1) instead of O(n).

• Restore active state according to its invariant. Undo all three occupancy sets; the N-Queens scratch board suffix is overwritten before use, while Word Search restores characters after both success and failure.

• A success boolean can stop a find-one helper; an enumeration helper records and continues. Public return contracts are separate.

• Pruned backtracking is exhaustive search with impossible subtrees removed. For this n=8 implementation, combined column and diagonal checks reduce 19,173,961 derived unpruned calls to 2,057 measured calls.

Corrective source notes

• Introduction to Dynamic Programming - Algorithms for Competitive Programming — Memoization stores subproblem results so repeated states need not be recomputed. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.