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 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:¹

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.

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

O (1)

conflict check via column & diagonal sets (

r + c

r - c

); the conflict is highlighted

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 $↘$ diagonal: it has the same $r - c$ value, so the lookup $(r - c) \in d ia g_{-}$ rejects it in $O (1)$ and the column is pruned before we ever descend to the next row.

Algorithm:

\textsc{Queens}(r)

— place one queen per row using column \& diagonal sets

1
if $r = n$ then
2
record a solution; return
3
for $c \gets 0$ to $n-1$ do
4
if $c \in cols$ or $(r+c) \in diag_{+}$ or $(r-c) \in diag_{-}$ then
5
continue
conflict — prune
6
add $c$ to $cols$ ; add $r+c$ to $diag_{+}$ ; add $r-c$ to $diag_{-}$
7
$place[r] \gets c$
8
$\textsc{Queens}(r+1)$
9
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 co l s$ ?	$r + c \in d ia g_{+}$ ?	$r - c \in d ia g_{-}$ ?	verdict
0	1	no	no	no	place; $co l s {1}$ , $d ia g_{+} {1}$ , $d ia g_{-} {- 1}$
1	0	no	$1 \in {1}$ yes	—	reject (diag with row-0 queen)
1	3	no	no	no	place; $co l s {1, 3}$ , $d ia g_{+} {1, 4}$ , $d ia g_{-} {- 1, - 2}$
2	0	no	$2$ no	$2$ no	place; $co l s {0, 1, 3}$ , $d ia g_{+} {1, 2, 4}$ , $d ia g_{-} {- 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 $d ia g_{+}$ from the row- $0$ queen, which shares its $↗$ 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]$ .

n_queens.pypython

def solve_n_queens(size: int) -> list[list[int]]:
  """
    Every placement of `size` non-attacking queens, each as a list whose\n
    r-th entry is the column of the queen in row r. The list is empty when\n
    no placement exists.\n
  """
  # accumulated solutions and the column-per-row board being built.
  solutions: list[list[int]] = []
  placement: list[int] = [-1 for _ in range(size)]

  # occupancy sets: columns, "/" diagonals (r + c), "\" diagonals (r - c).
  columns: set[int] = set()
  rising_diagonals: set[int] = set()
  falling_diagonals: set[int] = set()

  def place_row(row: int) -> None:

    # a full board is a solution.
    if row == size:
      solutions.append(placement.copy())
      return

    for column in range(size):

      # O(1) conflict check against the three occupancy sets.
      if (
        column in columns
        or (row + column) in rising_diagonals
        or (row - column) in falling_diagonals
      ):
        continue

      # place the queen and mark its column and both diagonals.
      columns.add(column)
      rising_diagonals.add(row + column)
      falling_diagonals.add(row - column)
      placement[row] = column

      place_row(row + 1)

      # undo the placement before trying the next column.
      columns.remove(column)
      rising_diagonals.remove(row + column)
      falling_diagonals.remove(row - column)
      placement[row] = -1

  place_row(0)
  return solutions

def count_n_queens(size: int) -> int:
  """
    The number of distinct non-attacking placements of `size` queens\n
    (the problem known as N-Queens II), counted without storing boards.\n
  """
  # the same three occupancy sets, with no board materialized.
  columns: set[int] = set()
  rising_diagonals: set[int] = set()
  falling_diagonals: set[int] = set()

  def count_from(row: int) -> int:

    # a full board contributes one placement.
    if row == size:
      return 1

    total: int = 0
    for column in range(size):

      # skip any column that conflicts on column or either diagonal.
      if (
        column in columns
        or (row + column) in rising_diagonals
        or (row - column) in falling_diagonals
      ):
        continue

      # mark, recurse to tally the subtree, then unmark.
      columns.add(column)
      rising_diagonals.add(row + column)
      falling_diagonals.add(row - column)
      total += count_from(row + 1)
      columns.remove(column)
      rising_diagonals.remove(row + column)
      falling_diagonals.remove(row - column)

    return total

  return count_from(0)

def is_valid_placement(placement: list[int]) -> bool:
  """
    Whether `placement` (a column per row) has no two queens attacking\n
    along a column or a diagonal. Used to verify candidate boards.\n
  """
  # every pair of rows must differ in column and avoid a shared diagonal.
  size: int = len(placement)
  for row in range(size):
    for other in range(row + 1, size):
      if placement[row] == placement[other]:
        return False
      if abs(placement[row] - placement[other]) == abs(row - other):
        return False
  return True

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)

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.

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

MRV branches on the empty cell with the smallest candidate set (

∣ D ∣ = 2

, in acc), minimizing fan-out and failing fast

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.

sudoku_solver.pypython

from typing import Optional

Grid = list[list[int]]   # 9x9; 0 marks an empty cell

_DIGITS: set[int] = set(range(1, 10))

class _SudokuState:
  """
    Mutable occupancy of a Sudoku in progress: the grid plus the set of\n
    digits already used in each row, each column, and each 3x3 box, so\n
    candidate lookups and updates are O(1).\n
  """

  def __init__(self, grid: Grid) -> None:
    # own copy of the grid plus empty occupancy sets for each region.
    self.grid: Grid = [row.copy() for row in grid]
    self.rows: list[set[int]] = [set() for _ in range(9)]
    self.columns: list[set[int]] = [set() for _ in range(9)]
    self.boxes: list[set[int]] = [set() for _ in range(9)]

    # seed the occupancy sets from the givens already on the grid.
    for row in range(9):
      for column in range(9):
        digit = self.grid[row][column]
        if digit != 0:
          self.rows[row].add(digit)
          self.columns[column].add(digit)
          self.boxes[self._box_index(row, column)].add(digit)

  @staticmethod
  def _box_index(row: int, column: int) -> int:
    """
      The 0..8 index of the 3x3 box that owns cell (row, column).\n
    """
    return (row // 3) * 3 + (column // 3)

  def candidates(self, row: int, column: int) -> set[int]:
    """
      The digits that may still legally fill cell (row, column).\n
    """
    used = self.rows[row] | self.columns[column] | self.boxes[
      self._box_index(row, column)
    ]
    return set(_DIGITS) - used

  def place(self, row: int, column: int, digit: int) -> None:
    """
      Write `digit` into the cell and record it in all three sets.\n
    """
    self.grid[row][column] = digit
    self.rows[row].add(digit)
    self.columns[column].add(digit)
    self.boxes[self._box_index(row, column)].add(digit)

  def remove(self, row: int, column: int, digit: int) -> None:
    """
      Clear the cell and retract `digit` from all three sets.\n
    """
    self.grid[row][column] = 0
    self.rows[row].discard(digit)
    self.columns[column].discard(digit)
    self.boxes[self._box_index(row, column)].discard(digit)

def _propagate(state: _SudokuState) -> Optional[list[tuple[int, int, int]]]:
  """
    Repeatedly fill naked singles (cells with exactly one candidate).\n
    Returns the list of (row, column, digit) fills made so they can be\n
    undone on backtrack, or None if some empty cell ran out of candidates\n
    (a dead state).\n
  """
  # fills made this pass, replayed until a full sweep adds nothing.
  filled: list[tuple[int, int, int]] = []
  progressed: bool = True
  while progressed:
    progressed = False

    # scan every empty cell for its current candidates.
    for row in range(9):
      for column in range(9):
        if state.grid[row][column] != 0:
          continue
        options = state.candidates(row, column)

        # no candidate is a dead end: undo this pass's fills and bail.
        if len(options) == 0:
          for filled_row, filled_column, filled_digit in reversed(filled):
            state.remove(filled_row, filled_column, filled_digit)
          return None

        # a lone candidate is a naked single: place it and keep going.
        if len(options) == 1:
          only = next(iter(options))
          state.place(row, column, only)
          filled.append((row, column, only))
          progressed = True
  return filled

def _select_cell(state: _SudokuState) -> Optional[tuple[int, int]]:
  """
    The empty cell with the fewest candidates (the MRV heuristic), or\n
    None if the grid is full.\n
  """
  # track the emptiest cell seen; start above any real candidate count.
  best_cell: Optional[tuple[int, int]] = None
  best_count: int = 10

  for row in range(9):
    for column in range(9):
      if state.grid[row][column] != 0:
        continue

      # keep the smallest candidate count; a single candidate can't be beat.
      count = len(state.candidates(row, column))
      if count < best_count:
        best_count = count
        best_cell = (row, column)
        if best_count == 1:
          return best_cell

  return best_cell

def solve_sudoku(grid: Grid) -> Optional[Grid]:
  """
    A completed grid satisfying every row/column/box constraint, or None\n
    if `grid` has no solution. The input is not modified.\n
  """
  state = _SudokuState(grid)

  def search() -> bool:

    # propagate naked singles first; an empty domain kills this branch.
    fills = _propagate(state)
    if fills is None:
      return False

    # no empty cell left means the grid is solved.
    cell = _select_cell(state)
    if cell is None:
      return True

    # branch on the most-constrained cell, trying each candidate digit.
    row, column = cell
    for digit in sorted(state.candidates(row, column)):
      state.place(row, column, digit)
      if search():
        return True
      state.remove(row, column, digit)

    # undo this branch's propagation fills before backtracking.
    for filled_row, filled_column, filled_digit in reversed(fills):
      state.remove(filled_row, filled_column, filled_digit)
    return False

  if search():
    return state.grid
  return None

def is_valid_sudoku(grid: Grid) -> bool:
  """
    Whether a completed grid breaks no row, column, or box constraint.\n
  """
  # every row and every column must hold each of 1..9 exactly once.
  for row in range(9):
    if {grid[row][column] for column in range(9)} != _DIGITS:
      return False
  for column in range(9):
    if {grid[row][column] for row in range(9)} != _DIGITS:
      return False

  # every 3x3 box must likewise hold the full digit set.
  for box_row in range(0, 9, 3):
    for box_column in range(0, 9, 3):
      cells = {
        grid[box_row + offset_row][box_column + offset_column]
        for offset_row in range(3)
        for offset_column in range(3)
      }
      if cells != _DIGITS:
        return False
  return True

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: the same 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.³

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

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 prune — it cuts only branches a violated constraint has already doomed — so the backtracking search remains complete: 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.

Forward checking after

x_{1} = r

r

is struck from each neighbor's domain;

D (x_{3})

collapses to

\emptyset

, so the branch is dead before descending

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.

forward checking prunes dead branches before descending; the surviving path is in accent

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

csp_solver.pypython

from __future__ import annotations

from collections import deque
from typing import Callable, Generic, Hashable, Iterable, Optional, TypeVar

Variable = TypeVar("Variable", bound=Hashable)
Value = TypeVar("Value", bound=Hashable)

# A binary constraint judges whether a value-pair on two variables is allowed.
Constraint = Callable[[Value, Value], bool]

class CSP(Generic[Variable, Value]):
  """
    A binary constraint-satisfaction problem.\n
    Each variable has a domain (the values it may take); each unordered\n
    pair of variables may carry a constraint predicate that the chosen\n
    values must satisfy. Constraints are stored symmetrically so the solver\n
    can reason about either direction of an arc.\n
  """

  def __init__(self, domains: dict[Variable, Iterable[Value]]) -> None:
    # own each variable's domain as a set; start with no neighbors or arcs.
    self.domains: dict[Variable, set[Value]] = {
      variable: set(values) for variable, values in domains.items()
    }
    self.neighbors: dict[Variable, set[Variable]] = {
      variable: set() for variable in domains
    }
    self._constraints: dict[
      tuple[Variable, Variable], Constraint[Value]
    ] = {}

  @property
  def constraints(
    self,
  ) -> dict[tuple[Variable, Variable], Constraint[Value]]:
    """
      The recorded binary constraints, keyed by ordered variable pair.\n
      Read-only access for callers that need to inspect or iterate the\n
      problem's arcs without reaching into private state.\n
    """
    return self._constraints

  def add_constraint(
    self,
    first: Variable,
    second: Variable,
    allowed: Constraint[Value],
  ) -> None:
    """
      Require that any values `a` on `first` and `b` on `second` satisfy\n
      `allowed(a, b)`. The constraint is recorded for both directions.\n
    """
    # link the two variables and store the predicate for both directions.
    self.neighbors[first].add(second)
    self.neighbors[second].add(first)
    self._constraints[(first, second)] = allowed
    self._constraints[(second, first)] = lambda b, a: allowed(a, b)

  def consistent(
    self,
    first: Variable,
    first_value: Value,
    second: Variable,
    second_value: Value,
  ) -> bool:
    """
      Whether assigning the two values violates no constraint between the\n
      variables. Variables with no shared constraint are always consistent.\n
    """
    allowed = self._constraints.get((first, second))
    if allowed is None:
      return True
    return allowed(first_value, second_value)

  def shadow(
    self,
    domains: dict[Variable, set[Value]],
  ) -> CSP[Variable, Value]:
    """
      A view of this problem over the supplied `domains`, sharing its\n
      constraints and neighbor structure. Lets AC-3 prune working domains\n
      without touching the original problem.\n
    """
    # a fresh instance over the given domains, sharing structure with self.
    view: CSP[Variable, Value] = type(self).__new__(type(self))
    view.domains = domains
    view.neighbors = self.neighbors
    view._constraints = self._constraints
    return view

def ac3(problem: CSP[Variable, Value]) -> bool:
  """
    Enforce arc consistency over `problem`, shrinking domains in place\n
    until every arc is consistent. Returns False if some domain empties\n
    (the problem is unsolvable), otherwise True.\n
  """
  # seed the queue with every directed arc in the constraint graph.
  arcs: deque[tuple[Variable, Variable]] = deque(
    (first, second)
    for first in problem.neighbors
    for second in problem.neighbors[first]
  )

  while arcs:
    first, second = arcs.popleft()

    # an empty domain after revision means the problem is unsolvable.
    if _revise(problem, first, second):
      if len(problem.domains[first]) == 0:
        return False

      # first lost a value, so its other neighbors must be rechecked.
      for third in problem.neighbors[first]:
        if third != second:
          arcs.append((third, first))

  return True

def _revise(
  problem: CSP[Variable, Value],
  first: Variable,
  second: Variable,
) -> bool:
  """
    Drop every value of `first` that has no compatible value in `second`.\n
    Returns whether any value was removed.\n
  """
  # discard any value of first with no support among second's values.
  removed: bool = False
  for value in set(problem.domains[first]):
    if not any(
      problem.consistent(first, value, second, other)
      for other in problem.domains[second]
    ):
      problem.domains[first].discard(value)
      removed = True
  return removed

def solve_csp(
  problem: CSP[Variable, Value],
) -> Optional[dict[Variable, Value]]:
  """
    A full assignment satisfying every constraint, or None if none exists.\n
    Runs an AC-3 preprocessing pass, then backtracks with MRV variable\n
    selection and forward checking. The problem's domains are not mutated.\n
  """
  # copy domains so AC-3 and search prune a private working set.
  working: dict[Variable, set[Value]] = {
    variable: set(values) for variable, values in problem.domains.items()
  }

  # an AC-3 wipeout before search begins means there is no solution.
  if not ac3(problem.shadow(working)):
    return None

  assignment: dict[Variable, Value] = {}

  def select_variable() -> Variable:
    """
      The unassigned variable with the smallest domain (MRV), breaking\n
      ties by the most constraints on other unassigned variables (degree).\n
    """
    unassigned = [
      variable for variable in working if variable not in assignment
    ]
    return min(
      unassigned,
      key=lambda variable: (
        len(working[variable]),
        -sum(
          1
          for neighbor in problem.neighbors[variable]
          if neighbor not in assignment
        ),
      ),
    )

  def backtrack() -> bool:

    # a complete assignment is a solution.
    if len(assignment) == len(working):
      return True

    # branch on the MRV-selected variable, trying its values in repr order.
    variable = select_variable()
    for value in sorted(working[variable], key=repr):

      # forward checking: provisionally strike `value`'s conflicts from
      # every unassigned neighbor, recording removals so we can undo them.
      removed: dict[Variable, set[Value]] = {}
      dead: bool = False
      for neighbor in problem.neighbors[variable]:
        if neighbor in assignment:
          continue
        losing = {
          other
          for other in working[neighbor]
          if not problem.consistent(variable, value, neighbor, other)
        }
        if losing:
          working[neighbor] -= losing
          removed[neighbor] = losing
          if len(working[neighbor]) == 0:
            dead = True
            break

      # if no neighbor emptied, commit the value and recurse.
      if not dead:
        assignment[variable] = value
        if backtrack():
          return True
        del assignment[variable]

      # undo this value's forward-checking removals.
      for neighbor, losing in removed.items():
        working[neighbor] |= losing
    return False

  if backtrack():
    return assignment
  return None

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.

word_search.pypython

Board = list[list[str]]

_MOVES: tuple[tuple[int, int], ...] = ((-1, 0), (1, 0), (0, -1), (0, 1))

def exists(board: Board, word: str) -> bool:
  """
    Whether `word` can be traced through `board` along adjacent cells\n
    (up/down/left/right) without revisiting a cell. The empty word always\n
    exists; an empty board admits only the empty word.\n
  """
  # trivial cases: the empty word matches; an empty board matches nothing.
  if word == "":
    return True
  if not board or not board[0]:
    return False

  # grid extent plus a visited mask shared across the recursion.
  height: int = len(board)
  width: int = len(board[0])
  visited: list[list[bool]] = [[False for _ in range(width)] for _ in range(height)]

  def trace(row: int, column: int, position: int) -> bool:

    # prune the moment this cell mismatches; succeed at the last letter.
    if board[row][column] != word[position]:
      return False
    if position == len(word) - 1:
      return True

    # mark this cell, then recurse into each unvisited in-bounds neighbor.
    visited[row][column] = True
    for delta_row, delta_column in _MOVES:
      next_row = row + delta_row
      next_column = column + delta_column
      if (
        0 <= next_row < height
        and 0 <= next_column < width
        and not visited[next_row][next_column]
      ):
        if trace(next_row, next_column, position + 1):
          visited[row][column] = False
          return True

    # undo the visit mark before returning to the caller.
    visited[row][column] = False
    return False

  # launch a trace from every cell as a possible starting square.
  for start_row in range(height):
    for start_column in range(width):
      if trace(start_row, start_column, 0):
        return True
  return False

palindrome_partition_search.pypython

def _is_palindrome(text: str, low: int, high: int) -> bool:
  """
    Whether text[low..high] reads the same forwards and backwards.\n
  """
  # close in from both ends until they meet or a mismatch breaks it.
  while low < high:
    if text[low] != text[high]:
      return False
    low += 1
    high -= 1
  return True

def partition(text: str) -> list[list[str]]:
  """
    Every partition of `text` into palindromic substrings, each partition\n
    a list of pieces in left-to-right order. The empty string yields one\n
    partition: the empty list.\n
  """
  # collected partitions, plus the pieces of the partition being built.
  partitions: list[list[str]] = []
  pieces: list[str] = []
  length: int = len(text)

  def cut_from(start: int) -> None:

    # reaching the end means the current pieces form a full partition.
    if start == length:
      partitions.append(pieces.copy())
      return

    # try every palindromic prefix, then recurse on the remaining suffix.
    for end in range(start, length):
      if _is_palindrome(text, start, end):
        pieces.append(text[start : end + 1])
        cut_from(end + 1)
        pieces.pop()

  cut_from(0)
  return partitions

def minimum_cuts(text: str) -> int:
  """
    The fewest cuts that split `text` into all-palindrome pieces (one less\n
    than the size of the smallest such partition). An empty or one-character\n
    string needs zero cuts.\n
  """
  if len(text) <= 1:
    return 0
  return min(len(pieces) for pieces in partition(text)) - 1

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.⁴ 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.⁵ The same min-conflicts/random-restart idea underlies WalkSAT for satisfiability.

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.

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, Ch. — Backtracking: CSPs as variables/domains/constraints solved by recursive, incrementally-checked assignment. ↩
Skiena, § — Combinatorial Search: N-Queens with column and diagonal occupancy sets for $O (1)$ pruning, and pruning as the core of practical backtracking. ↩
Skiena, § — Combinatorial Search: graph coloring as a CSP and the role of vertex ordering and propagation. ↩
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. ↩
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. ↩