Constraint Search: N-Queens & Sudoku

The previous lesson built backtracking as a general tool: explore the tree of partial solutions depth-first, extend a partial solution one choice at a time, and abandon (backtrack) the moment the partial solution cannot possibly be completed. This lesson specializes that machinery to its most natural habitat, the constraint satisfaction problem (CSP), and asks the question that decides whether the search returns in milliseconds or never: how cheaply, and how early, can we detect that a partial assignment is doomed?

A CSP is three things:¹

• a set of variables $x_1,\dots ,x_n$;
• for each variable a domain $D_i$ of values it may take;
• a set of constraints, each forbidding certain combinations of values on some subset of the variables.

A solution assigns every variable a value from its domain so that all constraints hold. Backtracking treats the variables as levels of a search tree: at level $i$ we try each value in $D_i$, check the constraints that involve $x_i$ and the already-assigned variables, and recurse only if none is violated. The single most important design decision is to check constraints incrementally, the moment we place $x_i$, not after a full assignment, so that a violated constraint prunes an entire subtree of ${\prod }_{j>i}|D_j|$ would-be assignments at once. A cheap, early constraint check plus a smart variable ordering is what makes exponential search terminate.

N-Queens: the archetype

Place $n$ queens on an $n\times n$ board so that no two attack each other. A queen attacks along its row, its column, and both diagonals. The first pruning insight is structural: since no two queens may share a row, place exactly one queen per row and let the variable $x_r\in \{0,\dots ,n-1\}$ be the column of the queen in row $r$. That choice bakes the row constraint into the encoding: we never even consider two-in-a-row.

What remains is to check, when placing a queen at $(r,c)$, that it shares no column and no diagonal with an earlier queen. The trick is to notice that the two diagonal families have constant labels. Every square on a $\searrow$ diagonal has the same value of $r-c$; every square on a $\nearrow$ diagonal has the same value of $r+c$. So three boolean sets, one for occupied columns, one for occupied $r+c$ diagonals, one for occupied $r-c$ diagonals, give an $O(1)$ conflict check and an $O(1)$ update.²

The shaded squares are exactly those attacked by the placed queen: its column, its row, and its two diagonals. The marked square ($\times$, in accent) lies on that queen's $\searrow$ diagonal: it has the same $r-c$ value, so the lookup $(r-c)\in dia{g}_{-}$ rejects it in $O(1)$ and the column is pruned before we ever descend to the next row.

Each node does $O(n)$ work over the $n$ columns with $O(1)$ per column, and the recursion is $n$ deep. The number of solutions grows fast and irregularly ($2$ for $n=4$, $10$ for $n=5$, $92$ for $n=8$, $724$ for $n=10$) with no closed form; counting them is exactly N-Queens II. The board's symmetries (rotations and reflections form a group of order $8$) let a solver explore only a fundamental region and multiply, a standard constant-factor speedup. The asymptotic cost is still exponential in the worst case; the constraint sets buy a large constant factor and prune most of the tree, but they do not change the complexity class, and no fast exact algorithm is known.

The whole search fits in one picture for $n=4$. Each level commits the next row's queen to a column, and a clash with the column or a diagonal set prunes the branch immediately. Two of the four opening columns ($0$ and $3$) die in conflicts before the board fills; the other two each lead, by a single surviving path, to one of the board's two solutions, $[1,3,0,2]$ and $[2,0,3,1]$.

Sudoku: propagation and the most-constrained variable

A Sudoku is a CSP with $81$ variables (the cells), each with domain $\{1,\dots ,9\}$, and constraints that the nine cells of every row, column, and $3\times 3$ box are all distinct. Naive backtracking already works: pick an empty cell, try each digit consistent with its row, column, and box, recurse, and undo on failure. As with queens, keep a boolean set per row, per column, and per box so the consistency check and update are $O(1)$.

But naive ordering is slow, and two ideas turn it sharp:

• Constraint propagation. Before branching, repeatedly fill every cell whose candidate set has collapsed to a single value (a naked single), and remove that value from its peers' candidate sets. One forced fill often triggers a cascade, solving easy puzzles with no search at all and shrinking the tree dramatically on hard ones.
• Most-constrained-variable (MRV) heuristic. When you must branch, branch on the empty cell with the fewest remaining candidates. Branching on a cell with two options instead of nine cuts the fan-out where it matters, and it fails fast: a cell that has been narrowed to zero candidates is discovered immediately, pruning that branch at the top instead of after a deep fruitless descent. MRV is the single biggest practical speedup for Sudoku.

Branching on the two-candidate cell forks the search only two ways instead of four or nine; and if propagation later narrows a cell to $|D|=0$, MRV reaches it first and prunes that branch at the top.

Together these collapse a search that is hopeless under naive row-major ordering into one that finishes quickly on every newspaper puzzle. The algorithm (backtracking) is unchanged; the ordering and the propagation are what make it tractable.

Graph $m$-coloring: the same skeleton again

Given a graph $G$ and $m$ colors, assign a color to each vertex so that adjacent vertices differ. This is a CSP whose variables are vertices, whose domains are the $m$ colors, and whose constraints are one inequality per edge. Backtracking colors vertices in some order, trying each color not already used by an assigned neighbor and backtracking when a vertex has no legal color: exactly the queens/Sudoku skeleton with a different constraint. Deciding whether a $3$-coloring exists is NP-complete, so we again expect exponential worst case. The same speedups (order vertices by degree, a form of MRV, and propagate forced colors) are what make real instances solvable.³

General CSP speedups

The techniques above are instances of a small, reusable toolkit. They share one goal: discover failure as early and as cheaply as possible, so that the search never descends into a subtree that cannot contain a solution.

Concretely, forward checking acts on the domains themselves: assigning a value strikes it from every neighbor's remaining choices, and a domain that empties is the signal to backtrack.

The figure below shows forward checking pruning a branch the instant a choice empties a neighbor's domain, long before a constraint check on a complete assignment would have caught it.

Setting $x_2=a$ leaves a neighbor with an empty domain, so forward checking cuts that branch immediately ($\varnothing$); only $x_2=b$ keeps every neighbor non-empty, and the search descends along the accented path.

Word Search and Palindrome Partitioning

The same constraint-pruned backtracking drives grid and string puzzles where the constraint is a property of the partial path rather than a global relation.

• Word Search asks whether a word can be traced through a grid by moving to adjacent cells without reusing a cell. The variables are the successive characters; the domain at each step is the four neighbors; the constraints are matches the next letter and not already visited. Mark a cell visited before recursing and unmark it on backtrack (the canonical make-move/undo-move pair), and prune the instant a neighbor's letter mismatches.
• Palindrome Partitioning cuts a string into substrings that are all palindromes. The choice at each position is where to make the next cut; the constraint is that the prefix you cut off is a palindrome, checked before you recurse on the rest. Rejecting a non-palindromic prefix prunes every partition that would have started with it: early constraint checking, exactly as in the CSPs above.

Takeaways

• A constraint satisfaction problem is variables + domains + constraints; backtracking assigns variables one at a time, checks constraints incrementally, and abandons a partial assignment the moment a constraint breaks, pruning an entire subtree at once.
• N-Queens places one queen per row and tests safety with three boolean sets (columns, $r+c$ diagonals, $r-c$ diagonals) for an $O(1)$ conflict check; solution counts grow fast and irregularly with no closed form.
• Sudoku combines $O(1)$ row/column/box consistency with constraint propagation (fill forced cells, narrow candidates) and the MRV heuristic (branch on the cell with the fewest candidates), the big practical speedup.
• Graph $m$-coloring is the same skeleton: one inequality constraint per edge, solved by the same ordering-and-propagation toolkit.
• Forward checking, MRV + least-constraining-value ordering, and arc consistency / AC-3 all serve one end, detecting failure as early and as cheaply as possible, which is what lets exponential search finish.
• Word Search and Palindrome Partitioning are grid/string backtracking with path constraints (visited cells; palindromic prefixes), pruned by the same early-check principle.