Prerequisite: Dynamic Programming

CSP Formulation

A Constraint Satisfaction Problem (CSP) is a triple $(\mathcal{X}, \mathcal{D}, \mathcal{C})$:

  • $\mathcal{X} = {X_1, \ldots, X_n}$: a set of variables.
  • $\mathcal{D} = {D_1, \ldots, D_n}$: domains, where $D_i$ is the finite set of values $X_i$ may take.
  • $\mathcal{C}$: a set of constraints, each a relation over a subset of variables.

A solution is an assignment $X_i \mapsto v_i \in D_i$ that satisfies all constraints. CSPs unify a large class of combinatorial problems: scheduling, graph coloring, Sudoku, SAT, and more.

Backtracking is depth-first search over the space of partial assignments, pruning branches that already violate a constraint.

Backtrack(assignment, csp):
    if assignment is complete: return assignment
    X = SelectUnassignedVariable(csp, assignment)
    for v in OrderDomainValues(X, assignment, csp):
        if v is consistent with assignment:
            assignment[X] = v
            result = Backtrack(assignment, csp)
            if result != failure: return result
            delete assignment[X]
    return failure

Without pruning, this explores $\prod_i |D_i|$ leaves - exponential in $n$. The key to practical performance is reducing this search space aggressively.

Arc Consistency (AC-3)

Arc consistency is a form of constraint propagation. An arc $(X_i, X_j)$ is arc-consistent if for every value $v \in D_i$ there exists some $w \in D_j$ such that $(v, w)$ satisfies the binary constraint $C_{ij}$. Enforcing arc consistency removes values from domains that can never participate in a solution.

AC-3 algorithm:

AC3(csp):
    queue = all arcs in csp
    while queue is not empty:
        (Xi, Xj) = Dequeue(queue)
        if Revise(csp, Xi, Xj):
            if D[Xi] is empty: return false   // no solution
            for Xk in Neighbors(Xi) \ {Xj}:
                Enqueue(queue, (Xk, Xi))
    return true

Revise(csp, Xi, Xj):
    revised = false
    for v in D[Xi]:
        if no w in D[Xj] satisfies constraint(Xi=v, Xj=w):
            remove v from D[Xi]; revised = true
    return revised

Complexity. Let $e$ = number of constraints, $d = \max_i |D_i|$. Each arc $(X_i, X_j)$ is enqueued at most $d$ times (once per removal from $D_i$). Each Revise call costs $O(d^2)$. Total: $O(e \cdot d^3)$.

AC-3 is complete for binary constraints: if it does not detect a domain wipeout, a solution may still require further search, but all detected wipeouts are genuine infeasibilities.

Forward Checking

A lighter form of propagation: after assigning $X_i = v$, remove from each unassigned neighbor $X_j$’s domain all values inconsistent with $v$. If any domain empties, backtrack immediately. Forward checking enforces a weaker form of consistency than AC-3 but costs much less per step.

Variable Ordering: MRV and Degree Heuristic

The choice of which variable to assign next dramatically affects performance.

Minimum Remaining Values (MRV): Choose the variable with the fewest legal values remaining in its domain - the “most constrained” or “fail-first” variable. Intuitively, this detects failures early and prunes large subtrees.

Degree heuristic (tie-breaking): When MRV ties, choose the variable involved in the most constraints on remaining unassigned variables. This heuristic maximizes future constraint propagation.

Formally, MRV picks:

$$X^\ast = \arg\min_{X \text{ unassigned}} |D_X|$$

Value Ordering: Least Constraining Value

When choosing a value for the selected variable, prefer the least constraining value: the one that rules out the fewest values in the domains of neighboring variables. This maximizes the chance that remaining variables can still be assigned.

$$v^\ast = \arg\min_{v \in D_{X^\ast}} \sum_{Y \in \text{neighbors}(X^\ast)} |{w \in D_Y : (v, w) \text{ violates constraint}}|$$

Unlike MRV (which is fail-first), value ordering is success-first: it tries the most promising branch first to find solutions quickly.

Backjumping

Chronological backtracking on failure returns to the most recently assigned variable. This can be wasteful: the conflict may have been caused by a variable assigned much earlier.

Conflict-directed backjumping (CBJ) computes the conflict set for $X_i$: the set of previously assigned variables whose assignments are incompatible with any value in $D_i$. On failure, jump back to the most recent variable in the conflict set, skipping irrelevant intermediate assignments.

This can turn exponential search into polynomial in some structured problems.

$n$-Queens

Place $n$ queens on an $n \times n$ board such that no two share a row, column, or diagonal.

Variables: $Q_i$ = column of queen in row $i$, domain ${1, \ldots, n}$.

Constraints: $Q_i \neq Q_j$ (columns) and $|Q_i - Q_j| \neq |i - j|$ (diagonals) for all $i \neq j$.

Backtracking with MRV places queens row by row. After placing row $i$, forward checking eliminates attacked columns from rows $i+1, \ldots, n$. For $n = 8$: only 92 solutions exist out of $8^8 \approx 16.7$ million naive assignments, but backtracking with propagation finds them in milliseconds.

Sudoku via Backtracking + Constraint Propagation

A $9 \times 9$ Sudoku has 81 variables, each with domain ${1, \ldots, 9}$. Constraints: all-different in each row, column, and $3 \times 3$ box ($27$ all-different constraints total).

Strategy:

  1. Apply AC-3 to propagate initial clues. Many cells reduce to singletons.
  2. Apply MRV: pick the cell with fewest remaining candidates.
  3. Assign a value, run forward checking, recurse.
  4. Backtrack if any domain empties.

Most newspaper Sudoku puzzles are solved without any backtracking - constraint propagation alone suffices. “Hard” puzzles may require a few backtracks.

DPLL for SAT

The Davis-Putnam-Logemann-Loveland (DPLL) algorithm is backtracking search for satisfiability of a propositional formula in CNF, augmented with two propagation rules:

  • Unit propagation: If a clause contains exactly one unset literal, that literal must be true. Assign it and propagate.
  • Pure literal elimination: If a variable appears with only one polarity across all unsatisfied clauses, assign it to satisfy those clauses.

DPLL is the foundation of modern SAT solvers (which add clause learning and non-chronological backtracking - CDCL). It runs in $O(2^n)$ worst case but is extremely fast in practice.

Examples

Map coloring. Assign colors from ${R, G, B}$ to regions of a map such that adjacent regions differ. This is a CSP where variables are regions, domains are colors, and constraints are inequality between adjacent pairs. It is equivalent to graph 3-coloring (NP-complete in general, but planar graphs are 4-colorable by the four-color theorem).

Scheduling with resource constraints. Assign start times $T_i \in {0, \ldots, H}$ to tasks with durations $d_i$, deadlines $l_i$, and resource requirements $r_i$, subject to: $T_i + d_i \leq l_i$ (deadlines), $T_i + d_i \leq T_j$ or $T_j + d_j \leq T_i$ for conflicting tasks (no overlap), and $\sum_{T_i \leq t < T_i + d_i} r_i \leq R$ (resource capacity). AC-3 propagates temporal and resource bounds; MRV selects the most constrained task next.

Read Next: Randomized Algorithms