---
title: "Constraint Search: N-Queens & Sudoku"
module: Backtracking & Search
moduleNumber: 9
lessonNumber: 2
order: 902
summary: |
  Many hard puzzles are **constraint satisfaction problems**: assign each
  variable a value from its domain so that every constraint holds. Backtracking
  solves them by assigning variables one at a time and rejecting a partial
  assignment the instant a constraint breaks. We make the rejection cheap — $O(1)$
  conflict checks for N-Queens via column and diagonal sets — and prune harder
  with **forward checking**, **MRV** ordering, and **constraint propagation**,
  which is what lets an exponential search actually finish.
topics: [Backtracking]
sources:
  - book: Skiena
    ref: "§ — Combinatorial Search"
  - book: Erickson
    ref: "Ch. — Backtracking"
  - book: CLRS
    ref: "Ch. — (constraint search)"
practice:
  - title: 'N-Queens'
    slug: n-queens
    difficulty: Hard
  - title: 'N-Queens II'
    slug: n-queens-ii
    difficulty: Hard
  - title: 'Sudoku Solver'
    slug: sudoku-solver
    difficulty: Hard
  - title: 'Word Search'
    slug: word-search
    difficulty: Medium
  - title: 'Palindrome Partitioning'
    slug: palindrome-partitioning
    difficulty: Medium
---

The previous lesson built [backtracking](/algorithms/backtracking/backtracking-fundamentals)
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 main application,
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 cannot be completed?_

A CSP is three things:[^erickson-bt]

- 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 two diagonal families
each carry a constant label.

> **Property (diagonals 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$. Hence two queens share a diagonal iff they agree
> on $r - c$ or on $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.[^skiena-cs]

$$
% caption: $O(1)$ conflict check via column \& diagonal sets ($r{+}c$, $r{-}c$); the
%          conflict is highlighted
\begin{tikzpicture}[
  scale=0.8,
  cell/.style={draw, minimum size=8mm, inner sep=0},
  q/.style={fill=black!12},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % draw 5x5 grid
  \foreach \x in {0,...,4} {
    \foreach \y in {0,...,4} {
      \draw (\x,\y) rectangle ++(1,1);
    }
  }
  % queen at column 1 in the top row (board cell x=1, y=4): shade what it attacks
  \foreach \y in {0,1,2,3} { \fill[black] (1,\y) rectangle ++(1,1); } % its column
  \foreach \x in {0,2,3,4} { \fill[black] (\x,4) rectangle ++(1,1); } % its row
  \fill[black] (0,3) rectangle ++(1,1); % up-left diagonal (off-board beyond)
  \fill[black] (2,3) rectangle ++(1,1); % its down-right diagonal:
  \fill[black] (3,2) rectangle ++(1,1); \fill[black] (4,1) rectangle ++(1,1);
  % placed queen (safe), top row, column 1
  \node at (1.5,4.5) {$Q$};
  % conflict square: column 3, row index 2 lies on that queen's down-right diagonal
  \fill[acc!25] (3,2) rectangle ++(1,1);
  % drawn X (not $\times$, which garbles)
  \draw[acc, very thick] (3.25,2.25) -- (3.75,2.75);
  \draw[acc, very thick] (3.25,2.75) -- (3.75,2.25);
  % redraw grid lines on top
  \foreach \x in {0,...,4} { \foreach \y in {0,...,4} { \draw (\x,\y) rectangle ++(1,1); } }
\end{tikzpicture}
$$

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 diag_{-}$ rejects it in $O(1)$ and the column is pruned
before we ever descend to the next row.

```algorithm
caption: $\textsc{Queens}(r)$ — place one queen per row using column \& diagonal sets
if $r = n$ then
  record a solution; return
for $c \gets 0$ to $n-1$ do
  if $c \in cols$ or $(r+c) \in diag_{+}$ or $(r-c) \in diag_{-}$ then
    continue // conflict — prune
  add $c$ to $cols$; add $r+c$ to $diag_{+}$; add $r-c$ to $diag_{-}$
  $place[r] \gets c$
  $\textsc{Queens}(r+1)$
  remove $c$ from $cols$, $r+c$ from $diag_{+}$, $r-c$ from $diag_{-}$ // undo
```

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 the problem known as **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.

For example, follow the $O(1)$ sets through the winning line.
Starting the $n=4$ search from column $1$ in row $0$ and taking the first surviving
branch at each row builds the solution $[1, 3, 0, 2]$:

| Row $r$ | try col $c$ | $c \in cols$? | $r{+}c \in diag_+$? | $r{-}c \in diag_-$? | verdict |
| --- | --- | --- | --- | --- | --- |
| 0 | 1 | no | no | no | place; $cols\{1\}$, $diag_+\{1\}$, $diag_-\{-1\}$ |
| 1 | 0 | no | $1{\in}\{1\}$ yes | — | reject (diag with row-0 queen) |
| 1 | 3 | no | no | no | place; $cols\{1,3\}$, $diag_+\{1,4\}$, $diag_-\{-1,-2\}$ |
| 2 | 0 | no | $2$ no | $2$ no | place; $cols\{0,1,3\}$, $diag_+\{1,2,4\}$, $diag_-\{-1,-2,2\}$ |
| 3 | 2 | no | $5$ no | $1$ no | place; board full — **solution** $[1,3,0,2]$ |

Every rejection is a single set-membership test; the queen at row $1$, column $0$
is rejected because $r{+}c = 1$ already sits in $diag_+$ from the row-$0$ queen,
which shares its $\nearrow$ diagonal. 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]$.

::impl{algo="n_queens"}

$$
% caption: The complete $n=4$ search tree drawn as partial boards — each level places the
%          next row's queen; a conflict prunes the branch ($\times$), and only two paths
%          fill the board (in acc)
\begin{tikzpicture}[scale=0.9, >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \newcommand{\bd}[4]{%
    \begin{scope}[shift={(#1,#2)}]
      \fill[white] (-0.7,-0.7) rectangle (0.7,0.7);
      \foreach \i in {0,...,3} \foreach \j in {0,...,3}
        \draw[black, line width=0.15pt] (-0.7+\j*0.35,0.7-\i*0.35) rectangle ++(0.35,-0.35);
      \foreach \r/\c in {#3} \fill[black!78] (-0.525+\c*0.35,0.525-\r*0.35) circle (0.082);
      \draw[#4, line width=0.6pt] (-0.7,-0.7) rectangle (0.7,0.7);
    \end{scope}}
  % edges first; the boards' white fill hides the overlaps
  \draw[black] (0,0)--(-6.75,-2.6); \draw[black] (0,0)--(6.75,-2.6);
  \draw[black] (-6.75,-2.6)--(-8,-5.2); \draw[black] (-6.75,-2.6)--(-5.5,-5.2);
  \draw[black] (-5.5,-5.2)--(-5.5,-7.8);
  \draw[black] (6.75,-2.6)--(5.5,-5.2); \draw[black] (6.75,-2.6)--(8,-5.2);
  \draw[black] (5.5,-5.2)--(5.5,-7.8);
  \draw[acc, line width=1pt] (0,0)--(-2.2,-2.6)--(-2.2,-5.2)--(-2.2,-7.8)--(-2.2,-10.4);
  \draw[acc, line width=1pt] (0,0)--(2.2,-2.6)--(2.2,-5.2)--(2.2,-7.8)--(2.2,-10.4);
  % boards: \bd{x}{y}{queen list r/c}{frame color}
  \bd{0}{0}{}{black}
  \bd{-6.75}{-2.6}{0/0}{black}
  \bd{-2.2}{-2.6}{0/1}{acc}
  \bd{2.2}{-2.6}{0/2}{acc}
  \bd{6.75}{-2.6}{0/3}{black}
  \bd{-8}{-5.2}{0/0,1/2}{black}
  \bd{-5.5}{-5.2}{0/0,1/3}{black}
  \bd{-2.2}{-5.2}{0/1,1/3}{acc}
  \bd{2.2}{-5.2}{0/2,1/0}{acc}
  \bd{5.5}{-5.2}{0/3,1/0}{black}
  \bd{8}{-5.2}{0/3,1/1}{black}
  \bd{-5.5}{-7.8}{0/0,1/3,2/1}{black}
  \bd{-2.2}{-7.8}{0/1,1/3,2/0}{acc}
  \bd{2.2}{-7.8}{0/2,1/0,2/3}{acc}
  \bd{5.5}{-7.8}{0/3,1/0,2/2}{black}
  \bd{-2.2}{-10.4}{0/1,1/3,2/0,3/2}{acc}
  \bd{2.2}{-10.4}{0/2,1/0,2/3,3/1}{acc}
  % dead ends: drawn X (not $\times$, which garbles)
  \foreach \dx/\dy in {-8/-6.42, -5.5/-9.02, 8/-6.42, 5.5/-9.02} {
    \draw[red!75!black, line width=1pt] (\dx-0.18,\dy-0.18) -- (\dx+0.18,\dy+0.18);
    \draw[red!75!black, line width=1pt] (\dx-0.18,\dy+0.18) -- (\dx+0.18,\dy-0.18);
  }
  % solutions (spaces, not commas, which garble in node text)
  \node[text=acc, font=\scriptsize] at (-2.2,-11.45) {$[1\;3\;0\;2]$};
  \node[text=acc, font=\scriptsize] at (2.2,-11.45) {$[2\;0\;3\;1]$};
\end{tikzpicture}
$$

## 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; two ideas improve it:

- **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.

$$
% caption: Propagation cascade: filling a naked single ($\{4\}$) strikes $4$ from a peer,
%          collapsing it to a new naked single ($\{7\}$) — one forced fill triggers the
%          next
\begin{tikzpicture}[
  >=stealth, font=\small,
  cell/.style={draw, minimum size=11mm, inner sep=1pt},
  cand/.style={draw=none, font=\scriptsize},
  stp/.style={draw=none, font=\scriptsize, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-1.2,1.5) rectangle (9.6,-2.5);
  % ----- a naked single, filled -----
  \node[stp] at (0.6,1.2) {\texttt{naked single}};
  \node[cell, fill=acc!15, draw=acc, very thick] (c1) at (0.6,0) {$4$};
  \node[cand, acc] at (0.6,-0.95) {cand. \texttt{[4]}: f\/ill};
  % propagation arrow 1: strike 4 from the peer
  \draw[->, red!75!black, very thick] (1.35,0) -- node[above, draw=none, font=\footnotesize, text=red!75!black, align=center] {\texttt{strike 4}\\ \texttt{from peer}} (3.6,0);
  % ----- the peer before/after the strike -----
  \node[stp] at (4.35,1.2) {\texttt{peer's candidates}};
  \node[cell] (c2) at (4.35,0) {};
  \node[cand] at (4.35,0.28) {\texttt{[4 7]}};
  \node[cand, text=red!75!black] at (4.35,-0.3) {= \texttt{[7]}};
  % propagation arrow 2: now a forced single
  \draw[->, red!75!black, very thick] (5.1,0) -- node[above, draw=none, font=\footnotesize, text=red!75!black, align=center] {\texttt{collapses to}\\ \texttt{a single}} (7.35,0);
  % ----- the new forced fill -----
  \node[stp] at (8.1,1.2) {\texttt{forced next}};
  \node[cell, fill=acc!15, draw=acc, very thick] (c3) at (8.1,0) {$7$};
  \node[cand, acc] at (8.1,-0.95) {cand. \texttt{[7]}: f\/ill};
  % cascade note
  \node[draw=none, font=\footnotesize, align=center] at (4.35,-2.0)
    {\texttt{the cascade can solve easy puzzles with no search}};
\end{tikzpicture}
$$

$$
% caption: MRV branches on the empty cell with the smallest candidate set ($|D|{=}2$, in
%          acc), minimizing fan-out and failing fast
\begin{tikzpicture}[
  >=stealth, font=\small,
  cell/.style={draw, minimum size=12mm, inner sep=1pt},
  cand/.style={font=\scriptsize, draw=none}]
  \definecolor{acc}{HTML}{2348F2}
  \node[cell] (c1) at (0,0) {};
  \node[cand] at (0,0.28) {\texttt{[3 5 7 9]}};
  \node[cand] at (0,-0.3) {size 4};
  \node[cell, draw=acc, very thick] (c2) at (2.4,0) {};
  \node[cand, acc] at (2.4,0.28) {\texttt{[2 8]}};
  \node[cand, acc] at (2.4,-0.3) {size 2};
  \node[cell] (c3) at (4.8,0) {};
  \node[cand] at (4.8,0.28) {\texttt{[1 4 6]}};
  \node[cand] at (4.8,-0.3) {size 3};
  \node[draw=none, acc, font=\footnotesize] at (2.4,-1.2) {MRV: branch here};
\end{tikzpicture}
$$

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.

::impl{algo="sudoku_solver"}

## Graph $m$-coloring: the same skeleton again

Given a [graph](/algorithms/graphs/representations-and-traversal) $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: the same
queens/Sudoku skeleton with a different constraint. Deciding whether a $3$-coloring
exists is [NP-complete](/algorithms/intractability/np-completeness), 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.[^skiena-color]

$$
% caption: $3$-coloring as a CSP: vertex $v$ sees neighbors using all three colors
%          $\{1,2,3\}$, so its domain is empty — no legal color, backtrack
\begin{tikzpicture}[
  >=stealth, font=\small,
  vtx/.style={draw, circle, minimum size=8mm, inner sep=1pt, font=\small},
  cur/.style={draw=red!75!black, very thick, circle, minimum size=8mm, inner sep=1pt, font=\small, text=red!75!black},
  lbl/.style={draw=none, font=\scriptsize},
  every edge/.style={draw, black}]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-2.0,1.6) rectangle (6.6,-2.6);
  % three already-colored neighbors fanned around v
  \node[vtx] (a) at (-1.4,1.0) {$1$};
  \node[vtx] (b) at (-1.7,-0.9) {$2$};
  \node[vtx] (c) at (0.4,-1.6) {$3$};
  % the vertex being colored
  \node[cur] (v) at (0,0) {$v$};
  \draw (v) edge (a) (v) edge (b) (v) edge (c);
  % its (now empty) domain
  \node[lbl, align=left] at (2.75,0.55) {\texttt{neighbors use [1 2 3]}};
  \node[lbl, text=red!75!black, align=left] at (2.65,-0.15) {\texttt{D(v) empty}};
  \node[lbl, text=red!75!black, align=left] at (2.6,-0.85) {\texttt{no legal color}};
  \node[lbl, text=red!75!black, align=center] at (1.6,-2.15) {\texttt{$\Rightarrow$ backtrack}};
\end{tikzpicture}
$$

## 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. Every one of them is
a [sound](/algorithms/foundations/what-is-an-algorithm) prune — it cuts only
branches a violated constraint has already doomed — so the backtracking search
remains [complete](/algorithms/foundations/what-is-an-algorithm): no satisfying
assignment is ever pruned away.

> **Remark (Forward checking).** When you assign $x_i$, immediately remove the now-illegal
> values from the domains of every _unassigned_ neighbor. If any neighbor's
> domain becomes **empty**, this assignment is already dead: backtrack now,
> before descending. Forward checking turns a violation that naive search would
> only notice levels later into an immediate cutoff.
>
> **Variable & value ordering.** Pick the next variable by **MRV** (smallest
> remaining domain, failing fast where the tree is narrowest); break ties by the
> **degree heuristic** (most constraints on unassigned variables). Order the
> _values_ you try by **least-constraining-value** (the value that rules out the
> fewest choices for neighbors, leaving the most options open).
>
> **Arc consistency (AC-3).** Go further than forward checking: repeatedly enforce
> that for every constraint between $x$ and $y$, every value of $x$ has _some_
> compatible value of $y$, deleting any that does not, until nothing changes. Run
> as preprocessing or after each assignment, AC-3 prunes domains globally and can
> solve some CSPs with no search at all.

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.

$$
% caption: Forward checking after $x_1{=}r$: $r$ is struck from each neighbor's domain;
%          $D(x_3)$ collapses to $\varnothing$, so the branch is dead before descending
\begin{tikzpicture}[
  >=stealth, font=\small,
  var/.style={draw, fill=acc!12, minimum size=7mm, font=\small},
  val/.style={draw, minimum size=6mm, inner sep=1pt, font=\scriptsize},
  gone/.style={draw, minimum size=6mm, inner sep=1pt, font=\scriptsize, text=red!70}]
  \definecolor{acc}{HTML}{2348F2}
  \node[var, fill=acc!15, draw=acc, very thick] (x1) at (0,0) {$x_1{=}r$};
  \node[draw=none] at (-1.0,-1.3) {$D(x_2)$:};
  \node[val] (g2) at (0.3,-1.3) {$g$};
  \node[gone] (r2) at (0.95,-1.3) {$r$};
  \node[val] (b2) at (1.6,-1.3) {$b$};
  \draw[red!70] (0.7,-1.05)--(1.2,-1.55);
  \node[draw=none] at (-1.0,-2.4) {$D(x_3)$:};
  \node[gone] (r3) at (0.3,-2.4) {$r$};
  \draw[red!70] (0.05,-2.15)--(0.55,-2.65);
  \node[draw=none, text=red!70] at (1.55,-2.4) {\texttt{= empty (dead)}};
  \draw[->, acc] (x1) -- (-0.3,-1.05);
  \draw[->, acc] (x1) -- (-0.3,-2.15);
\end{tikzpicture}
$$

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.

$$
% caption: forward checking prunes dead branches before descending; the surviving path is
%          in accent
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=1pt, font=\small},
  level distance=13mm, sibling distance=22mm, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-4.2,0.6) rectangle (4.2,-3.2);
  \node[acc, very thick] {$x_1$}
    child {node {$x_2{=}a$}
      child {node[draw=red!75!black, text=red!75!black, dashed, inner sep=0pt] {\scriptsize dead}}
    }
    child {node[acc, very thick] {$x_2{=}b$}
      child {node[acc, very thick] {$x_3$}}
    };
  % annotate the pruned branch
  \node[draw=none, font=\footnotesize, align=center, text=red!75!black] at (-3.0,-2.6)
    {$x_2{=}a$ empties\\ \texttt{D(x3): prune}};
  \node[draw=none, font=\footnotesize, acc] at (3.0,-2.6) {\texttt{survives}};
\end{tikzpicture}
$$

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.

::impl{algo="csp_solver"}

## 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.

::impl{algo="word_search,palindrome_partition_search"}

## The CSP toolbox that industry actually runs

The heuristics above — forward checking, MRV, AC-3 — are the textbook core of a
much larger, and heavily deployed, constraint-programming stack.

**Backjumping and learning.** Plain backtracking undoes _one_ decision at a time,
even when the real culprit is many levels up. **Conflict-directed backjumping**
(Prosser, 1993) records _which_ earlier assignments caused a dead end and leaps
straight back to the deepest one, skipping the irrelevant levels between — the CSP
cousin of the non-chronological backjumping that makes SAT solvers
fast.[^backjump] Combined with **no-good learning** (remember the conflicting
partial assignment so it is never retried), it can prune large parts of the tree.

**Local search: min-conflicts.** For huge, loosely constrained instances, a
different strategy wins outright. **Min-conflicts** (Minton et al., 1992) abandons
tree search entirely: start from a complete but invalid assignment, then
repeatedly pick a conflicted variable and reassign it to the value that violates
the _fewest_ constraints. It solves the _million-queens_ problem in seconds — far
past anything systematic backtracking reaches — though, being a hill-climber, it is
incomplete and can stall in local minima.[^minconf] The same
min-conflicts/random-restart idea underlies **WalkSAT** for satisfiability.

$$
% caption: Two ways to attack a CSP. Systematic backtracking (left) walks a tree of partial
%          assignments, complete but exponential; local search / min-conflicts (right) hops
%          between complete assignments toward zero conflicts — fast but incomplete.
\begin{tikzpicture}[font=\small, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % left: tree
  \node[draw, circle, minimum size=4mm, inner sep=0] (r) at (0,1.4) {};
  \node[draw, circle, minimum size=4mm, inner sep=0] (a) at (-0.9,0.4) {};
  \node[draw, circle, minimum size=4mm, inner sep=0] (b) at (0.9,0.4) {};
  \node[draw, circle, minimum size=4mm, inner sep=0] (c) at (-1.4,-0.6) {};
  \node[draw, circle, minimum size=4mm, inner sep=0] (d) at (-0.4,-0.6) {};
  \draw[black] (r)--(a) (r)--(b) (a)--(c) (a)--(d);
  \node[font=\footnotesize, anchor=north] at (0,-1.1) {backtracking: tree of partials};
  % right: hops among complete states
  \foreach \i/\x/\y/\lab in {0/4.0/1.2/3, 1/5.2/0.4/1, 2/4.6/-0.5/0} {
    \node[draw, minimum size=6mm, inner sep=1pt, font=\footnotesize,
      fill=acc!12] (s\i) at (\x,\y) {\lab};
  }
  \draw[->, acc, thick] (s0) -- node[right, font=\scriptsize] {} (s1);
  \draw[->, acc, thick] (s1) -- (s2);
  \node[font=\footnotesize, anchor=north] at (4.7,-1.1) {min-conf\/licts: hop, cut conf\/licts};
\end{tikzpicture}
$$

**Where it ships.** These techniques underlie production constraint
solvers — Google's OR-Tools CP-SAT, IBM CP Optimizer, MiniZinc back-ends — which
schedule airline crews, route delivery fleets, lay out silicon, and timetable
tournaments. The newspaper Sudoku of this lesson is a small special case of the
same prune-early principle.

## 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.

[^erickson-bt]: **Erickson**, Ch. — Backtracking: CSPs as variables/domains/constraints solved by recursive, incrementally-checked assignment.
[^skiena-cs]: **Skiena**, § — Combinatorial Search: N-Queens with column and diagonal occupancy sets for $O(1)$ pruning, and pruning as the core of practical backtracking.
[^skiena-color]: **Skiena**, § — Combinatorial Search: graph coloring as a CSP and the role of vertex ordering and propagation.
[^backjump]: **Prosser, P.** (1993), "Hybrid algorithms for the constraint satisfaction problem," _Computational Intelligence_ 9(3), 268–299 — conflict-directed backjumping and its combination with forward checking.
[^minconf]: **Minton, S., Johnston, M. D., Philips, A. B. & Laird, P.** (1992), "Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems," _Artificial Intelligence_ 58(1–3), 161–205 — the min-conflicts local-search heuristic solving million-queens instances.