Constraint Satisfaction: Variables, Domains, and Backtracking

Sudoku, class scheduling, circuit layout, and protein folding all share the same skeleton: you have a set of unknowns, each with a finite range of legal values, and a set of rules that link the unknowns together. This abstract skeleton is a Constraint Satisfaction Problem (CSP).

Before we name the parts formally, pick up the smallest version: a 4×4 Sudoku. Each of the 16 cells is an unknown. Each cell’s legal values are {1, 2, 3, 4}. Every row, column, and 2×2 box must contain each digit exactly once. Those row/column/box rules are the constraints.

A solution is an assignment of a value from each variable’s domain such that every constraint is satisfied simultaneously.

The CSP frame matters because it strips away the specifics of any one puzzle and exposes the algorithm underneath. Every solver — from a naive brute-force to Google’s CP-SAT — manipulates these three objects: variables, domains, constraints.

The moment you fix one variable’s value, some values for neighbouring variables become illegal. This is local constraint propagation: no search yet, just implication-following.

The widget below puts you in charge of a three-territory colouring (West, Center, East). All three share borders. Assign West to a colour and watch which values survive in Center’s and East’s domains.

Once you understand domains and propagation, the search algorithm is natural. Backtracking is depth-first search with one extra rule: if the current partial assignment violates a constraint (or empties any domain), stop immediately and undo the last assignment.

The algorithm in plain English:

1. Pick an unassigned variable.
2. Try each value in its domain.
3. If the assignment is consistent with all constraints so far, recurse.
4. If recursion succeeds, return the solution.
5. If every value leads to failure — backtrack: undo this assignment and try the next value for the previous variable.

def backtrack(assignment, csp):
    if len(assignment) == len(csp.variables):
        return assignment          # all variables assigned — success

    var = select_unassigned(csp, assignment)

    for value in csp.domains[var]:
        if consistent(var, value, assignment, csp):
            assignment[var] = value
            result = backtrack(assignment, csp)
            if result is not None:
                return result
            del assignment[var]   # undo — backtrack

    return None                   # no value worked — failure

The 4-Queens problem (place four queens on a 4×4 chessboard so no two attack each other) is a classic CSP. Step through the actual search the algorithm performs:

The critical observation: backtracking does not undo one step at a time after reaching a dead end — it precisely undoes the last decision that could still be varied. This is why it is exponentially faster than exhaustive enumeration, which would try every complete assignment.

Backtracking finds solutions, but it wastes time discovering dead ends it could have predicted. Arc consistency (AC) is a pre-processing pass (and an interleaved-during-search pass) that removes values provably incapable of participating in any solution.

A variable Xᵢ is arc-consistent with respect to Xⱼ if, for every value in Dᵢ, there exists at least one value in Dⱼ that satisfies the constraint between them. If a value in Dᵢ has no such “support” in Dⱼ, it can be deleted: no solution will ever use it.

The widget below runs AC-3 on a three-variable numeric CSP — X, Y, Z each starting with domain {1, 2, 3}, constrained by X < Y and Y < Z. Step through each arc processing to watch domains collapse down to a single value apiece. No search is needed at all.

CSPs are expressive — almost any combinatorial puzzle fits the frame. But three limits matter:

Exponential worst case. Even with AC-3, backtracking can still visit exponentially many nodes on adversarially-constructed problems (e.g., random k-SAT near the phase transition). Arc consistency alone does not guarantee polynomial search time.

Global constraints are outside the basic model. The CSP framework as described handles binary constraints (between two variables). Constraints like “all different” or “the sum equals 100” span many variables. Efficient propagation algorithms for these — called global constraint propagators — are built into industrial solvers (CP-SAT, Choco, MiniZinc) but are not captured by basic AC-3.

Soft constraints are invisible. A hard CSP asks: find any solution. Real scheduling problems ask: find the best solution when some constraints can be violated at a cost. That extension — Constraint Optimisation Problems (COPs) — requires objective functions, branch-and-bound, or LP relaxations layered on top.