Constraint Satisfaction

Eight queens, four billion boards

Put 8 queens on a chessboard so that no two attack each other: no shared row, column or diagonal. The obvious plan tries every way to choose 8 of the 64 squares and tests each board. That is C(64, 8) = 4,426,165,368 boards. At a million boards a second, you wait about 74 minutes.

Two ideas cut that to almost nothing. First, describe the problem better. Two queens in the same row always attack, so give each row exactly one queen and decide only its column. That leaves 8⁸ = 16,777,216 boards. Second, check early. Place the queens one row at a time and reject a queen the moment it attacks one already on the board. A board that is broken after three queens is never extended to eight. The search now looks at 2,057 partial boards and finds all 92 solutions.

That is this lesson. A constraint satisfaction problem (CSP) is a set of decisions, the options for each decision, and rules that limit which combinations are allowed. You solve it by making one decision at a time and backing up as soon as a rule breaks. Every technique after that is a way to notice failure earlier or more cheaply.

Before you start. This lesson builds on Advanced Recursion & Backtracking: the call stack, base cases and the choose → explore → unchoose template. It uses that template without re-teaching it. From the Foundation lesson you need sets for O(1) membership tests. All code is Python 3.

Move 1: Name the three parts

Smell: the statement says "place", "fill" or "assign", and some pairs of choices are not allowed together.

A CSP has three parts:

• Variables are the decisions you must make.
• Domains are the values each variable may take.
• Constraints are rules over some of the variables that say which combinations are allowed.

A solution is an assignment that is complete, meaning every variable has a value, and consistent, meaning no constraint is broken.

For 8-Queens:

The row rule has disappeared from the constraints. It is built into the variables: one variable per row means one queen per row. That is the first lever you control.

Predict first: model the same puzzle with one yes/no variable per square instead: 64 variables, each either "queen" or "empty". How many complete assignments are there, and how does that compare with the one-variable-per-row model?

Three shapes of constraint

• A unary constraint involves one variable: "this Sudoku cell is already 5", "meeting M1 is not on Monday". Apply it once, before the search, by shrinking that variable's domain.
• A binary constraint involves two variables: Q2 ≠ Q5, or "these two neighbouring regions get different colours".
• A global constraint involves many variables at once. The classic is AllDifferent. Sudoku requires each row, column and 3×3 box to hold different digits. One AllDifferent over 9 cells says the same thing as C(9, 2) = 36 pairwise ≠ rules.

The constraint graph

Draw one node per variable and one edge per binary constraint. This constraint graph shows which decisions can affect which.

In N-Queens every pair of rows is constrained, so every pair of nodes is joined. For 4 queens that is 4 nodes and all 6 edges:

  Q0 ------ Q1
  |  \    /  |
  |    \/    |
  |    /\    |
  |  /    \  |
  Q2 ------ Q3

The textbook example is map colouring. Colour the 7 regions of Australia with red, green and blue so that regions sharing a border get different colours:

 WA ------- NT ------- Q
   \        |        / |
    \       |       /  |
     \      |      /   |
      '---- SA ---'    |
           /   \       |
          /     '---- NSW
         /             |
        V -------------'          T

The 9 edges are WA–NT, WA–SA, NT–SA, NT–Q, SA–Q, SA–NSW, SA–V, Q–NSW and NSW–V. Tasmania (T) has no neighbours.

What the graph tells you:

• Neighbours are what a choice can break. Colouring SA can only affect its 5 neighbours. Moves 5 and 6 do their work along these edges.
• Separate pieces are separate problems. T shares no edge with anything, so colour it on its own. In general, solve each connected component separately: with d values per variable and pieces of a and b variables, that turns d ** (a + b) combinations into d ** a + d ** b.
• Trees are easy. If the graph has no cycles, no backtracking is needed. Pick a root. Working up from the leaves, delete every value of a parent that no value of its child is compatible with. Then assign from the root down: each child always finds a value compatible with its parent. That costs O(n·d²) for n variables with d values each. Australia is not a tree: WA, NT and SA form a triangle.

Your turn: model the Australia problem. How many variables and binary constraints are there, and what is the domain? Which region touches the most others? Why can no 2-colouring exist?

Move 2: Check early. Backtracking is the engine

Smell: the slow code builds a complete candidate and only then asks whether it is valid.

The lazy N-Queens fills all 8 rows and then tests the board: 16,777,216 complete boards.

Predict first: in 8-Queens, the lazy solver has put queens at (0, 0) and (1, 1), which attack along a diagonal. How many complete boards will it build and test before it moves the queen in row 1? How many of them can be solutions?

Backtracking stops that waste. Assign variables one at a time. Before giving a variable a value, check the constraints whose variables would then all have values. If one breaks, skip that value. If no value works, return to the previous variable and let it try its next value.

Here is a generic version. ok(var, value, assignment) answers one question: is var = value consistent with everything assigned so far?

def backtrack(variables, domains, ok, assignment=None):
    """Return one complete, consistent assignment as a dict, or None."""
    if assignment is None:
        assignment = {}                        # fresh dict for every top-level call
    if len(assignment) == len(variables):
        return dict(assignment)                # complete: hand back a copy
    var = next(v for v in variables if v not in assignment)
    for value in domains[var]:
        if ok(var, value, assignment):         # 1. check against assigned variables
            assignment[var] = value            # 2. place
            found = backtrack(variables, domains, ok, assignment)   # 3. recurse
            del assignment[var]                # 4. undo
            if found is not None:
                return found
    return None

The rhythm is check → place → recurse → undo. The check comes first, so the search never stands on a broken partial assignment. The undo puts the dict back exactly as the loop found it, so the next value starts from a clean slate. Because the base case returns a copy, this version can undo on every path, success included. (Move 4 shows a solver where undoing on success would be a bug.)

For N-Queens the variables are the rows, each domain is range(n), and ok compares the new queen with the queens already placed:

def queens_ok(row, col, assignment):
    for r, c in assignment.items():            # queens already on the board
        if c == col or abs(r - row) == abs(c - col):
            return False                       # same column, or same diagonal
    return True

rows = list(range(4))
print(backtrack(rows, {r: range(4) for r in rows}, queens_ok))
# {0: 1, 1: 3, 2: 0, 3: 2}

Here is the whole run. A partial board lists the queens' columns row by row, so [0, 2] means row 0 has its queen in column 0 and row 1 in column 2. Each rejected column shows the first conflict the check found.

. Q . .
. . . Q
Q . . .
. . Q .

26 calls to queens_ok and the first solution is found. The lazy version would have built complete boards from the start: [0, 0, 0, 0], [0, 0, 0, 1], and so on.

Why it works

Two claims, and both matter.

1. It never returns an invalid answer. Invariant: at the start of every call, no constraint whose variables all have values is broken. The check keeps this true when a value is placed, and the undo keeps it true when one is removed. When every variable has a value, every constraint has all of its variables assigned, so the whole assignment is consistent.
2. It never skips a solution. A value is rejected only when it breaks a constraint among variables that already have values. Giving more variables values cannot repair that constraint, so every completion of that partial board is broken too. Everything else is explored.

How big is the search?

Count nodes: one per call, which means one per partial assignment the search looks at, including the empty start. To find all solutions:

Early checking cannot beat exponential time in general. CSPs include problems such as graph 3-colouring, for which no polynomial algorithm is known. What it changes is the tree you actually walk, and that is often the difference between an hour and a millisecond. Each call tries up to n columns (d values in general), and each queens_ok call costs O(n). Extra space is O(n): one stack frame per assigned variable, plus the assignment. The recursion depth equals the number of variables, so Python's default limit of 1,000 frames is no concern for N-Queens (n ≤ 9 on LeetCode) or Sudoku (at most 81 blanks).

Traps

⚠️ The check inside the base case is the lazy version. It must sit inside the loop, before the recursive call.

⚠️ Check a rule only once it can be decided. Rejecting a partial board is safe only if the rule is already broken for every completion. "The row sums to exactly 10" cannot be tested after two of five cells. With non-negative numbers, "the partial sum is at most 10" can. With negative numbers, not even that is safe.

⚠️ A mutable default argument. Writing def backtrack(..., assignment={}) creates that dict once, when Python defines the function. A version that returns the dict itself, instead of a copy, and keeps its values on success leaves a solved assignment in the shared default, and the next call starts out "already complete". Use None and create the dict inside the function, as above.

Your turn: X, Y and Z each take a value from {1, 2, 3}. The constraints are X < Y, Y ≠ Z and X + Z = 4. Run backtrack by hand with variables in order X, Y, Z and values in increasing order. When Y is placed, which constraints can ok check? What is returned, and which values are rejected on the way?

Move 3: N-Queens. Make every check O(1)

Smell: for every candidate, the check loops over all earlier decisions.

queens_ok compares the new queen with every queen already placed, which is O(n) per candidate. But the questions it asks have short answers that change by one item per placement: is this column taken? is this diagonal taken? Keep those answers in sets.

Columns are easy. Diagonals need a key that every cell on the same diagonal shares:

    r - c           r + c
  0 -1 -2 -3       0  1  2  3
  1  0 -1 -2       1  2  3  4
  2  1  0 -1       2  3  4  5
  3  2  1  0       3  4  5  6

A step down and to the right adds 1 to both r and c, so r - c stays the same along every \ diagonal. A step down and to the left adds 1 to r and subtracts 1 from c, so r + c stays the same along every / diagonal (the anti-diagonal). An n × n board has 2n − 1 diagonals of each kind.

Predict first: queens stand at (1, 3) and (3, 1). Do they attack each other, and which key catches it? And what goes wrong if you store abs(r - c) instead of r - c?

This is LeetCode 51: N-Queens, which asks for every board as a list of strings:

def solve_n_queens(n):
    cols, diag, anti = set(), set(), set()   # used columns, r - c keys, r + c keys
    queens = []                              # queens[r] = column of the queen in row r
    boards = []

    def place(r):
        if r == n:                           # every row has a queen
            boards.append(['.' * c + 'Q' + '.' * (n - c - 1) for c in queens])
            return
        for c in range(n):
            if c in cols or r - c in diag or r + c in anti:
                continue                     # attacked: prune before recursing
            cols.add(c); diag.add(r - c); anti.add(r + c); queens.append(c)
            place(r + 1)
            cols.remove(c); diag.remove(r - c); anti.remove(r + c); queens.pop()

    place(0)
    return boards

for board in solve_n_queens(4):
    print(board)
# ['.Q..', '...Q', 'Q...', '..Q.']
# ['..Q.', 'Q...', '...Q', '.Q..']

Why it works. Invariant: when place(r) starts, cols, diag and anti hold exactly the columns and diagonals of the queens in rows 0 to r − 1. The three adds before the call and the three removes after it keep that true for every sibling. So the set test asks the same question as queens_ok, in O(1) instead of O(n). This solver collects all solutions, so the search never stops early, and every placement is undone on every path.

Cost. The column set alone leaves row r at most n − r free columns, so the tree can be no bigger than the tree of permutations: at most n! complete boards and about e · n! nodes, which is 109,601 for n = 8. The diagonal checks cut it much further, to the 2,057 nodes you saw. Each node loops over n columns with O(1) checks, so the time is O(n) per node, and O(n · n!) is a safe (loose) upper bound. Building each answer board costs O(n²). Extra space is O(n) for the sets, queens and the recursion stack, plus O(S · n²) for S output boards.

Traps

⚠️ One missing undo. Delete cols.remove(c) and a column stays "taken" for the rest of the search after its first use. For n = 4 the function returns [], with no error and no hint of why.

⚠️ No diagonal check at all. Drop the diagonal sets and every column permutation passes. For n = 4 you get 4! = 24 boards instead of 2.

⚠️ abs(r - c) as the diagonal key. It merges two different diagonals and rejects safe queens: for n = 8 it finds none of the 92 solutions.

Your turn: LeetCode 52: N-Queens II asks only for the number of solutions. Adapt the solver so it builds no boards, then predict the counts for n = 1 to 8.

def total_n_queens(n):
    cols, diag, anti = set(), set(), set()

    def count(r):
        if r == n:
            return 1                         # one complete placement
        total = 0
        for c in range(n):
            if c in cols or r - c in diag or r + c in anti:
                continue
            cols.add(c); diag.add(r - c); anti.add(r + c)
            total += count(r + 1)
            cols.remove(c); diag.remove(r - c); anti.remove(r + c)
        return total

    return count(0)

print([total_n_queens(n) for n in range(1, 9)])   # [1, 0, 0, 2, 10, 4, 40, 92]

Move 4: Sudoku. The same engine, bigger board

Smell: several overlapping "all different" groups, and blanks to fill.

LeetCode 37: Sudoku Solver gives a 9 × 9 board of characters, with '.' for an empty cell. Fill the board in place so that every row, column and 3 × 3 box holds '1' to '9' exactly once. The judge guarantees exactly one solution.

The given digits are constants. You can leave them out of the variables and put their digits into the row, column and box sets before the search starts (the code below does this), or make them variables with one-value domains. Both are correct. Two versions are wrong: giving a given cell the full domain, so the search can overwrite a clue, and leaving the givens out of the checks, so the search can repeat a clue's digit.

Number the boxes 0 to 8, left to right and top to bottom. The box of cell (r, c) is r // 3 * 3 + c // 3:

            c 0-2   c 3-5   c 6-8
  r 0-2       0       1       2
  r 3-5       3       4       5
  r 6-8       6       7       8

Predict first: which box holds (4, 7)? What goes wrong with r // 3 + c // 3?

def solve_sudoku(board):
    """LeetCode 37: fill board (9 lists of 9 chars, '.' = empty) in place."""
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empty = []
    for r in range(9):
        for c in range(9):
            d = board[r][c]
            if d == '.':
                empty.append((r, c))
            else:
                rows[r].add(d); cols[c].add(d); boxes[r // 3 * 3 + c // 3].add(d)

    def fill(k):
        if k == len(empty):
            return True                      # every empty cell has a digit
        r, c = empty[k]
        b = r // 3 * 3 + c // 3
        for d in '123456789':
            if d in rows[r] or d in cols[c] or d in boxes[b]:
                continue
            board[r][c] = d
            rows[r].add(d); cols[c].add(d); boxes[b].add(d)
            if fill(k + 1):
                return True                  # success: leave the digits in place
            rows[r].remove(d); cols[c].remove(d); boxes[b].remove(d)
            board[r][c] = '.'                # failure: undo everything
        return False

    fill(0)

Compare the success path with Move 2. There the answer was a copied dict, so undoing on every path was harmless. Here the board itself is the answer, so the solver returns True without undoing, and only a failed branch cleans up. Invariant: the three lists of sets always hold exactly the digits currently on the board.

Measured on CPython 3.14 (placements = digits written):

The hard puzzle is 52...6.........7.13...........4..8..6......5...........418.........3..2...87....., read row by row.

Sets versus scanning. A version whose check scans the row, the column and the box for each candidate (up to 27 comparisons instead of at most 3 set lookups) made exactly the same 3,252,580 placements and took about 5 times as long: 10.6 s against 2.0 s. Cheaper checks shrink the cost of each node, a constant factor. They do not shrink the tree. Move 5 does that.

Your turn: two one-character-looking bugs. Predict, for LeetCode's example board, what the board holds after the call and whether Python raises an error.

1. The digit loop is for d in '12345678':.
2. The undo moves above the test: found = fill(k + 1), then the four undo lines, then if found: return True.

Move 5: Fail first. Forward checking and the most constrained variable

Smell: the search fails deep in the tree because of a decision made near the top, and it takes a long time to notice.

In the fixed-order Sudoku solver, a digit placed in row 0 can leave some cell in row 8 with no legal digit at all. The solver does not look at that cell until its turn comes. Before that, it tries every combination for all the cells in between, and each attempt dies at the same cell.

Two fixes work together:

• Forward checking. After each assignment, delete from every unassigned neighbour's domain the values that now conflict. If a domain becomes empty, fail now.
• Minimum remaining values (MRV), also called fail-first or most constrained variable. Assign next the variable with the fewest values left. A variable with one value left is forced, and a variable with none is a dead end found at once.

Predict first: in 4-Queens, place a queen at (0, 0). Which columns are left for rows 1, 2 and 3? Then place a queen at (1, 2).

MRV for Sudoku

In Sudoku, forward checking comes almost for free: a cell's remaining domain is just the digits missing from its row, column and box, so compute it when you need it. MRV then means: look at every empty cell and fill the one with the fewest candidates. If some cell has none, the loop over its candidates runs zero times and the call fails immediately. That is forward checking's empty-domain test.

def solve_sudoku_mrv(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empty = []
    for r in range(9):
        for c in range(9):
            d = board[r][c]
            if d == '.':
                empty.append((r, c))
            else:
                rows[r].add(d); cols[c].add(d); boxes[r // 3 * 3 + c // 3].add(d)

    def candidates(r, c):
        used = rows[r] | cols[c] | boxes[r // 3 * 3 + c // 3]
        return [d for d in '123456789' if d not in used]

    def fill():
        best, options = None, None
        for r, c in empty:                   # MRV: find the most constrained cell
            if board[r][c] == '.':
                opts = candidates(r, c)
                if best is None or len(opts) < len(options):
                    best, options = (r, c), opts
        if best is None:
            return True                      # no empty cell left
        r, c = best
        b = r // 3 * 3 + c // 3
        for d in options:                    # no options: loop skipped, fail now
            board[r][c] = d
            rows[r].add(d); cols[c].add(d); boxes[b].add(d)
            if fill():
                return True
            rows[r].remove(d); cols[c].remove(d); boxes[b].remove(d)
            board[r][c] = '.'
        return False

    fill()

Ties go to the first cell in row-major order. Same puzzles, same machine:

Each MRV step costs more, because it scans every empty cell, and it still wins easily: the tree shrank by a factor of about 1,800.

Forward checking in general

When domains are not free to recompute, store them and record every deletion so it can be put back. This version takes a neighbors map (the constraint graph) and a compatible(x, a, y, b) test that says whether x = a and y = b can coexist. Passing both variable names lets it handle one-way rules such as A < B correctly.

def solve_fc(variables, domains, neighbors, compatible):
    """Backtracking + forward checking + MRV. Returns a dict or None."""
    domains = {v: set(vals) for v, vals in domains.items()}   # private working copy
    assignment = {}

    def forward_check(var, value):
        removed = []                                 # (neighbor, value) pairs
        for nb in neighbors[var]:
            if nb in assignment:
                continue
            for w in list(domains[nb]):
                if not compatible(var, value, nb, w):
                    domains[nb].remove(w)
                    removed.append((nb, w))
            if not domains[nb]:
                return removed, False                # wipe-out: dead end now
        return removed, True

    def search():
        if len(assignment) == len(variables):
            return dict(assignment)
        var = min((v for v in variables if v not in assignment),
                  key=lambda v: len(domains[v]))     # MRV: fewest values left
        for value in sorted(domains[var]):
            removed, alive = forward_check(var, value)
            found = None
            if alive:
                assignment[var] = value
                found = search()
                del assignment[var]
            for nb, w in removed:                    # restore on EVERY path,
                domains[nb].add(w)                   # including the wipe-out
            if found is not None:
                return found
        return None

    return search()

For N-Queens, the variables are rows, every other row is a neighbour, and compatible is lambda x, a, y, b: a != b and abs(x - y) != abs(a - b).

Why no ok check? Invariant: every value left in an unassigned variable's domain is compatible with every assigned neighbour. Forward checking deletes a value the moment it stops being compatible and restores exactly those deletions on the way back. So any value MRV's variable still holds is already known to fit.

⚠️ Restore on every path, including the wipe-out. When a domain empties halfway through the neighbours, values have already been deleted from the earlier neighbours. If you restore only after a successful check, those deletions leak into every sibling branch. With that one change, this solver returns None for 6-Queens and 8-Queens, which both have solutions.

Two more heuristics

• Degree breaks MRV ties: among variables with equally few values left, pick the one constrained with the most unassigned variables. It is useless in N-Queens, where every row is constrained with every other, and useful on maps.
• Least constraining value (LCV) orders the values: try first the one that deletes the fewest values from neighbours. It helps only when you stop at the first solution. When you need all solutions, or none exists, every value gets tried anyway and the tree has the same size. Enumerating all 92 solutions of 8-Queens with forward checking and MRV takes 1,069 nodes with LCV or without it.

How they stack on 20-Queens, stopping at the first solution (nodes = calls, including the start):

Two things to notice. Here MRV did the heavy lifting, while forward checking alone saved a factor of 2.4. And fewer nodes does not always mean less time: LCV and full propagation do more work per node. When in doubt, measure.

Your turn: colour Australia with forward checking, MRV and the degree tie-breaker, trying colours in the order red, green, blue. Start with WA = red. Which region comes next, and does the search ever back up?

Move 6: Let deductions ripple. Constraint propagation

Smell: one forced value forces another, which forces another.

Forward checking looks one step ahead, from the variable just assigned to its neighbours. But a deletion can have consequences of its own. Constraint propagation keeps following them until nothing more follows.

The standard form is arc consistency. The arc X → Y is consistent when every value left in X has at least one partner in Y's domain that satisfies the constraint between them. A value with no partner cannot be part of any solution, so delete it. That deletion may strand a value of some third variable Z that relied on it, so every arc Z → X that points into X must be checked again. AC-3 is this loop, driven by a queue of arcs.

Predict first: A, B and C each take a value from {1, 2, 3}, with A < B and B < C. What survives arc consistency? Now suppose you check only the arcs A → B and B → C, then A → B again, and stop. What do you get?

from collections import deque

def ac3(domains, neighbors, allowed):
    """Shrink domains until every value of every variable has a partner
    in each neighbor's domain. Returns False if some domain empties."""
    queue = deque((x, y) for x in domains for y in neighbors[x])
    while queue:
        x, y = queue.popleft()
        unsupported = {a for a in domains[x]
                       if not any(allowed(x, a, y, b) for b in domains[y])}
        if unsupported:
            domains[x] -= unsupported
            if not domains[x]:
                return False
            queue.extend((z, x) for z in neighbors[x] if z != y)   # recheck arcs into x
    return True

rank = {'A': 0, 'B': 1, 'C': 2}
def less(x, a, y, b):                    # the constraints A < B and B < C
    return a < b if rank[x] < rank[y] else a > b

domains = {v: {1, 2, 3} for v in 'ABC'}
neighbors = {'A': ['B'], 'B': ['A', 'C'], 'C': ['B']}
print(ac3(domains, neighbors, less), domains)
# True {'A': {1}, 'B': {2}, 'C': {3}}

The queue starts as A → B, B → A, B → C, C → B. Every revision that removed something:

Step 5 happens because step 3 shrank B, which put A → B back on the queue.

Why it works. Deleting a value that has no partner never loses a solution. Domains only shrink, so the loop ends. Cost: with e arcs and at most d values per domain, an arc re-enters the queue only when its target domain shrinks, so at most d times, and each revision compares up to d² pairs. That gives O(e · d³) in the worst case.

Sudoku, revisited. For a ≠ constraint, a value v of X loses its only partner in Y exactly when Y's domain is {v}. So arc consistency on Sudoku comes down to one rule, repeated: when a cell has one candidate left, delete that digit from its 20 peers. Human solvers call that a naked single. On LeetCode's example it fills all 51 blanks with no search at all, which is why MRV found every step forced there. On the hard puzzle it fills none. So strong solvers combine the two: propagate after every assignment, and search when propagation stalls. That combination is the "full propagation" row in Move 5's table.

Your turn: X, Y and Z each take a value from {1, 2}, and all three must be different. Run ac3 in your head. What does it return, and what happens when a search takes over?

Move 7: Word Search. A CSP along a path

Smell: the decisions form a path. Each choice must sit next to the previous one, and nothing may be used twice.

LeetCode 79: Word Search: given an m × n grid of letters and a word, return whether the word can be spelled by moving between horizontally or vertically adjacent cells, using each cell at most once. Here 1 ≤ m, n ≤ 6, the word has 1 to 15 letters, and only English letters appear.

The AllDifferent is the constraint that needs an undo. It asks "is this cell already on my path?", and the path changes as the search backs up.

Predict first: on this board, can you spell "SEE"? "ABCB"?

A B C E
S F C S
A D E E

def exist(board, word):
    m, n = len(board), len(board[0])

    def match(r, c, i):               # can word[i:] be spelled starting at (r, c)?
        if not (0 <= r < m and 0 <= c < n) or board[r][c] != word[i]:
            return False              # off the grid, wrong letter, or in use ('#')
        if i == len(word) - 1:
            return True               # the last letter matched
        board[r][c] = '#'             # mark: this cell is on the current path
        found = (match(r + 1, c, i + 1) or match(r - 1, c, i + 1) or
                 match(r, c + 1, i + 1) or match(r, c - 1, i + 1))
        board[r][c] = word[i]         # unmark on the way back up
        return found

    return any(match(r, c, 0) for r in range(m) for c in range(n))

board = [list("ABCE"), list("SFCS"), list("ADEE")]
print(exist(board, "ABCCED"), exist(board, "SEE"), exist(board, "ABCB"))
# True True False

All 13 calls for "ABCCED" (directions are tried down, up, right, left):

Why it works. Invariant: the cells marked '#' are exactly the cells on the current path. A '#' never equals a letter, so the letter check doubles as the "not already used" check, as row 11 of the trace shows. The unmark on the way back up restores the invariant for the next branch. It runs on success too, so the caller gets its board back unchanged.

Cost. There are m · n starting cells. From a start, the first step has up to 4 directions and every later step at most 3, because the cell you came from is marked. So each start explores O(3ᴸ) paths, for O(m · n · 3ᴸ) time in the worst case, where L is the word's length. Extra space is O(L) for the recursion; the marks live in the board itself.

Traps

⚠️ A missing unmark. A branch that fails leaves its cells marked, and every later branch treats them as used. Take the board [["A","A"],["A","B"]] and the word "AAA". Every valid path uses the corner (0, 0) as its middle letter, for example (0, 1) → (0, 0) → (1, 0). The search starts at the corner and fails, since both of its A-neighbours are dead ends. Without the unmark, it leaves (0, 0), (1, 0) and (0, 1) all marked, so every later start fails too. The answer comes out False instead of True.

⚠️ Negative indices wrap. Test the bounds before indexing. If the guard only checks r >= m or c >= n, then board[0][-1] quietly reads the last column. With [["A","B","C"]] and "AC", that version returns True, although A and C are not adjacent.

Prune before you search

LeetCode's follow-up asks for pruning on larger boards. Two cheap checks remove most of the worst cases:

1. Count letters first. If the board has fewer copies of some letter than the word needs, no path exists. On a 6 × 6 board of 'A's with the word 'A' * 14 + 'B', the plain search makes 9,030,868 calls (about a second) before it answers False. The count answers in O(m · n + L).
2. Start from the rarer end. A path that spells the word backwards is the same path, so the answer does not change. If the last letter is rarer on the board than the first, search for the reversed word: fewer starting cells, and doomed paths die sooner. That is MRV again. With one 'B' in the top-left corner (0, 0) of that board and 35 'A's, the word 'A' * 14 + 'B' takes 204,337 calls forwards and 24 reversed.

Your turn: write exist_pruned(board, word), which applies both checks and then calls exist.

from collections import Counter

def exist_pruned(board, word):
    have = Counter(ch for row in board for ch in row)
    if any(have[ch] < k for ch, k in Counter(word).items()):
        return False                     # the board lacks some letter: no search
    if have[word[-1]] < have[word[0]]:
        word = word[::-1]                # start from the rarer end
    return exist(board, word)

When you must find many words in one board (LeetCode 212: Word Search II), running this once per word repeats the same walks. Store the words in a trie and follow it during a single search from each cell. Tries are covered in Trees & Advanced Structures.

Final round: no label on the problem

Real problems don't announce that they are CSPs. Find the variables, domains and constraints, decide what you can check early, and only then write the search.

Challenge 1: Matchsticks to Square

LeetCode 473: Matchsticks to Square. You get the lengths of up to 15 matchsticks, each up to 10⁸. Use every stick exactly once, without breaking any, to form a square. [1, 1, 2, 2, 2] gives true (sides 2, 2, 2 and 1 + 1). [3, 3, 3, 3, 4] gives false.

Before peeking, answer these:

1. What are the variables, domains and constraints?
2. What can you rule out before any search?
3. In which order should the sticks be placed?
4. Two sides currently have the same total. Why try the next stick on only one of them?

def makesquare(matchsticks):
    total = sum(matchsticks)
    if len(matchsticks) < 4 or total % 4:
        return False
    side = total // 4
    sticks = sorted(matchsticks, reverse=True)   # long sticks fit in the fewest places
    if sticks[0] > side:
        return False
    sides = [0] * 4

    def place(i):
        if i == len(sticks):
            return True                          # no side overflowed, so all equal side
        for s in range(4):
            if sides[s] + sticks[i] > side:
                continue                         # would overflow: prune now
            if sides[s] in sides[:s]:
                continue                         # same total as an earlier side: same subtree
            sides[s] += sticks[i]
            if place(i + 1):
                return True
            sides[s] -= sticks[i]
        return False

    return place(0)

print(makesquare([1, 1, 2, 2, 2]), makesquare([3, 3, 3, 3, 4]))   # True False

Challenge 2: Flower Planting With No Adjacent

LeetCode 1042: Flower Planting With No Adjacent. There are n gardens (up to 10⁴), numbered 1 to n, and a list of two-way paths between them. Every garden has at most 3 paths. Plant one of 4 flower types in each garden so that gardens joined by a path get different types, and return any valid answer.

This looks like map colouring, which needed search. How much backtracking does it need?

def garden_no_adj(n, paths):
    neighbors = [[] for _ in range(n + 1)]       # gardens are numbered 1..n
    for x, y in paths:
        neighbors[x].append(y)
        neighbors[y].append(x)
    flower = [0] * (n + 1)                       # 0 = not planted yet
    for g in range(1, n + 1):
        taken = {flower[nb] for nb in neighbors[g]}
        flower[g] = next(f for f in (1, 2, 3, 4) if f not in taken)
    return flower[1:]

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

Is it a search at all? Ask this before you write any backtracker. Flower Planting passed one test: more values than neighbours, so greedy works in any order. A second test: if the only rules say "x must come before y", with no limit on how many things happen at once, a choice can never trap a later one either. Repeatedly take anything whose predecessors are all done; if you get stuck with items left, the rules contain a cycle. That is a topological order, O(V + E) for V items and E rules, and Graph Traversal teaches it. Backtracking earns its exponential worst case only when choices really can trap each other.

Cheat sheet

Before moving on, take N-Queens or Sudoku and explain it aloud from a blank editor: the variables, domains and constraints; the exact line where each constraint is checked and why that line is early enough; what the sets hold at the start of each call; what the undo restores, and why LeetCode 37's solver skips it on success; and which heuristic you would add first for a harder instance, and what you would measure to know it helped.

Next: Permutations & Combinations for the other big backtracking family, Dynamic Programming Mastery for searches whose subproblems repeat, and Graph Traversal for depth-first search on grids and graphs beyond a single path.