Constraint

constraint programming inverts the usual deal: you state what a solution must satisfy, and a general-purpose solver figures out how to find one. 𐃏 no objective gradient, no simplex tableau — just variables, finite domains, and constraints, attacked by an alternation of inference (prune values that cannot appear in any solution) and search (guess, propagate, backtrack). this page builds the machinery from the formalism up; the sudoku solver and hashiwokakero write-ups on this wiki are the same machinery pointed at actual puzzles.

the formalism#

a constraint satisfaction problem (CSP) is a triple \((X, D, C)\):

• variables \(X = \{x_1, \dots, x_n\}\).
• domains \(D = \{D_1, \dots, D_n\}\), each \(D_i\) a finite set of candidate values for \(x_i\).
• constraints \(C = \{c_1, \dots, c_m\}\), each \(c_j = (S_j, R_j)\) with scope \(S_j \subseteq X\) and relation \(R_j\) a subset of the cartesian product of the scoped domains — the tuples the constraint permits.

an assignment maps some variables to values in their domains; it is consistent if it violates no constraint whose scope it covers, complete if it covers all of \(X\). a solution is a consistent complete assignment. deciding whether one exists is NP-complete already for binary constraints over three-value domains (graph 3-colouring is exactly that CSP), so everything below is about making an exponential search collapse in practice, not about escaping it in theory.

structure lives in the constraint graph: one node per variable, one edge per binary constraint. constraints of higher arity make it a hypergraph — each constraint is a hyperedge covering its scope. 𐃏 the graph is not decoration: tree-structured constraint graphs are solvable in \(O(n d^2)\) by one sweep of directional arc consistency, and the general-case parameter that interpolates between “tree” and “hopeless” is the induced width of this graph.

propagation and consistency#

inference in CP means enforcing a local consistency property, deleting domain values that fail it, and repeating to a fixpoint. the two workhorses:

• node consistency: every value in \(D_i\) satisfies each unary constraint on \(x_i\). enforced once, in a single pass — fold unary constraints into the domains and forget them.
• arc consistency: for every directed arc \((x_i, x_j)\) carrying a binary constraint, every value \(v \in D_i\) has a support — some \(w \in D_j\) with \((v, w)\) permitted. a value without support appears in no solution, so deleting it is safe: propagation never loses a solution, it only shrinks the search space.

ac-3#

mackworth’s AC-3 enforces arc consistency with a worklist of arcs.¹

• input: domains, and a queue holding every directed arc.
• loop: pop an arc \((x_i, x_j)\); revise it — delete each value of \(D_i\) with no support in \(D_j\).
• wake-up rule: if revise deleted anything, the deletion may have destroyed supports elsewhere, so re-enqueue every arc \((x_k, x_i)\) for neighbours \(x_k \neq x_j\) (skipping arcs already queued).
• terminate: queue empty (arc-consistent fixpoint) or some domain wiped out (no solution — the strongest thing propagation alone can prove).

with \(e\) arcs and domains of size at most \(d\), each arc re-enters the queue \(O(d)\) times and a revise costs \(O(d^2)\), giving \(O(e d^3)\) time. AC-4 gets the optimal \(O(e d^2)\) by bookkeeping support counts, but its bookkeeping costs that much always; AC-2001 reaches the same bound while staying as lazy as AC-3, which is why AC-3’s skeleton is the one everybody actually implements.

a worked queue trace#

take the chain CSP: variables \(x, y, z\), all domains \(\{1,2,3\}\), constraints \(x < y\) and \(y < z\). initial queue: \((x,y), (y,x), (y,z), (z,y)\).

bookkeeping notes, step by step: step 1 revises \(x\), whose only neighbour is \(y\) itself, so nothing wakes up. step 2 revises \(y\) and would wake \((z,y)\), but it is already queued. step 3 revises \(y\) again and wakes \((x,y)\) — the arc processed back in step 1, back for another pass because its support landscape changed. step 4 revises \(z\); \(x\) is not adjacent to \(z\), so nothing wakes. the fixpoint is the singleton assignment \(x=1, y=2, z=3\): on this instance arc consistency alone solves the problem. do not be seduced — that is a property of this tiny chain, not of AC-3. the colouring CSP below reaches its arc-consistent fixpoint with a variable still holding two values, and search has to finish the job.

global constraints#

arity-two thinking hits a wall fast. a global constraint is a single constraint over many variables packaged with a dedicated propagation algorithm that exploits its combinatorial structure — the real engine of industrial CP.

alldifferent#

\(\operatorname{alldifferent}(x_1, \dots, x_n)\) demands pairwise distinct values. the naive decomposition into \(\binom{n}{2}\) disequalities is logically equivalent but propagates feebly: a binary \(x_i \neq x_j\) only prunes when one side is already a singleton. take three variables with domains \(\{1,2\}\) — every pairwise arc is consistent (each value of each variable has a support on every arc), yet the conjunction is unsatisfiable outright: three variables, two values, pigeonhole (Epp, Susanna S., 2019). arc consistency on the pieces sees nothing; generalised arc consistency (GAC) on the global constraint — every value extendable to a full satisfying tuple of the constraint — detects the wipe-out immediately.

regin showed GAC on alldifferent is tractable via matching theory.² build the bipartite value graph (variables on one side, values on the other, edges = domain membership); the constraint is satisfiable iff a maximum matching covers every variable, and a value can be pruned from a domain iff its edge lies in no maximum matching — decidable for all edges at once from one maximum matching plus a strongly-connected-components pass over the associated directed graph (berge’s alternating-cycle characterisation). the matching itself is a max-flow computation (Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford, 2009), hopcroft–karp gives \(O(\sqrt{n}\, m)\), and solvers amortise by repairing the previous matching incrementally after each domain change. honest caveat: this is still the priciest propagator in a typical model, so solvers offer weaker bounds-consistency variants of alldifferent when the full filtering does not pay for itself.

cumulative#

\(\operatorname{cumulative}\) is scheduling’s workhorse: tasks \(i\) with start variable \(s_i\), duration \(d_i\) and resource demand \(r_i\) share a resource of capacity \(R\), and the constraint enforces

\begin{equation} \sum_{i \,:\, s_i \le t < s_i + d_i} r_i \;\le\; R \qquad \text{for every time } t. \end{equation}

introduced in the CHIP system for resource-constrained project scheduling.³ here even deciding feasibility is NP-hard, so no polynomial propagator can enforce GAC; practical filtering is deliberately incomplete and layered — timetabling (accumulate each task’s compulsory part, the interval where it must sit however it slides, and forbid overloads), edge-finding (deduce that a task must end before, or start after, a whole set of others because the set’s combined energy leaves no room otherwise), and energetic reasoning (compare available area \(R \times |I|\) of a time window against the minimum work forced inside it). this is the pattern of the whole field: pick the strongest filtering whose cost per node you can afford.

search#

propagation prunes; it rarely finishes. the rest is tree search over assignments.

• chronological backtracking: depth-first — pick an unassigned variable, try a value consistent with the assignments so far, recurse; on failure undo and try the next value; when values run out, retreat to the previous variable. complete, exponential, and prone to thrashing: rediscovering the same dead end under thousands of irrelevant contexts.
• variable ordering — MRV / fail-first: branch on the variable with the fewest remaining values. 𐃏 a variable with two values left will be wrong half the time — better to be wrong near the root. ties break by degree: prefer the variable constraining the most unassigned others.
• value ordering — LCV / succeed-first: given the variable, try first the value that deletes the fewest values from neighbouring domains. variable choice wants to provoke failure early; value choice wants to dodge it — you must expand every value of a doomed variable anyway, but one good value suffices if a solution lies below.
• forward checking (FC): after assigning \(x_i := v\), revise each unassigned neighbour’s domain against \(x_i\) alone — one revise per neighbour and stop. catches immediate wipe-outs and feeds MRV fresh domain counts, but never propagates a deletion’s consequences: prunings that would only follow through a chain of two or more constraints go unseen.
• MAC (maintaining arc consistency): after the same assignment, seed AC-3’s queue with the arcs \((x_k, x_i)\) into the assigned variable and run to fixpoint, so deletions cascade through the whole constraint graph. strictly stronger pruning than FC for strictly more work per node; on hard structured instances MAC’s smaller trees win decisively, and it is the default in serious solvers. modern engines stack conflict-directed backjumping, nogood recording and restarts on top — the same lessons SAT solvers learned, arriving by convergent evolution.

branch and infer vs branch and bound#

CP and mixed-integer programming both wrap tree search around per-node reasoning, but the reasoning is philosophically different: MILP relaxes (drop integrality, solve the LP, bound the objective), CP infers (keep the logic, shrink the domains).⁴

the folk theorem holds up: when the difficulty is finding anything feasible among tangled combinatorial rules, CP’s inference dominates; when the difficulty is trading off costs across loosely-coupled decisions, the LP bound is the asset and MILP dominates. an objective enters CP as branch-and-bound over a domain: post \(z < z_{\text{incumbent}}\) and let propagation feel it — effective exactly when constraints link \(z\) tightly to the decision variables, which in scheduling (makespan) they do and in costing problems they often do not. hybrid decompositions that let an LP bound talk to CP propagators take both columns’ strengths, at the price of owning two models of the same problem.

code#

AC-3 from scratch — a queue of directed arcs, a revise that deletes unsupported values, and the wake-up rule; run on the worked chain and then on the colouring CSP from the diagram:

from collections import deque

def revise(domains, xi, xj, ok):
    """prune values of xi with no support in xj. returns the pruned values."""
    pruned = [v for v in domains[xi] if not any(ok(v, w) for w in domains[xj])]
    for v in pruned:
        domains[xi].remove(v)
    return pruned

def ac3(domains, constraints):
    """constraints: dict {(xi, xj): ok} listing every directed arc."""
    queue = deque(constraints)
    while queue:
        xi, xj = queue.popleft()
        pruned = revise(domains, xi, xj, constraints[(xi, xj)])
        if pruned:
            print(f"  revise({xi},{xj}) pruned {pruned}  ->  {xi} in {domains[xi]}")
            if not domains[xi]:
                return False                      # domain wipe-out
            for (a, b) in constraints:            # re-examine xi's other neighbours
                if b == xi and a != xj and (a, b) not in queue:
                    queue.append((a, b))
    return True

def arcs(edges, ok):
    """both directed arcs per undirected edge, one shared predicate."""
    return {(a, b): ok for (x, y) in edges for (a, b) in [(x, y), (y, x)]}

# --- csp 1: the chain x < y < z, all domains {1,2,3} ---------------------
dom = {"x": [1, 2, 3], "y": [1, 2, 3], "z": [1, 2, 3]}
cons = {("x", "y"): lambda a, b: a < b, ("y", "x"): lambda a, b: b < a,
        ("y", "z"): lambda a, b: a < b, ("z", "y"): lambda a, b: b < a}
print("chain csp, before:", dom)
print("consistent:", ac3(dom, cons))
print("chain csp, after: ", dom)

# --- csp 2: graph colouring, edges a-b, a-c, b-c, c-d --------------------
dom = {"a": ["r"], "b": ["r", "g"], "c": ["r", "g", "b"], "d": ["r", "g"]}
cons = arcs([("a", "b"), ("a", "c"), ("b", "c"), ("c", "d")],
            lambda u, v: u != v)
print("\ncolouring csp, before:", dom)
print("consistent:", ac3(dom, cons))
print("colouring csp, after: ", dom)

chain csp, before: {'x': [1, 2, 3], 'y': [1, 2, 3], 'z': [1, 2, 3]}
  revise(x,y) pruned [3]  ->  x in [1, 2]
  revise(y,x) pruned [1]  ->  y in [2, 3]
  revise(y,z) pruned [3]  ->  y in [2]
  revise(z,y) pruned [1, 2]  ->  z in [3]
  revise(x,y) pruned [2]  ->  x in [1]
consistent: True
chain csp, after:  {'x': [1], 'y': [2], 'z': [3]}

colouring csp, before: {'a': ['r'], 'b': ['r', 'g'], 'c': ['r', 'g', 'b'], 'd': ['r', 'g']}
  revise(b,a) pruned ['r']  ->  b in ['g']
  revise(c,a) pruned ['r']  ->  c in ['g', 'b']
  revise(c,b) pruned ['g']  ->  c in ['b']
consistent: True
colouring csp, after:  {'a': ['r'], 'b': ['g'], 'c': ['b'], 'd': ['r', 'g']}

the chain run reproduces the hand trace line for line — five revisions, \((x,y)\) processed twice. the colouring run confirms the diagram: three prunings, then a fixpoint with \(d\) still holding two values. finishing the job takes search — chronological backtracking with MRV, checking each candidate value only against already-assigned neighbours (ac3 and arcs from the block above are assumed in scope):

def solve(domains, edges):
    neighbours = {v: set() for v in domains}
    for x, y in edges:
        neighbours[x].add(y); neighbours[y].add(x)
    stats = {"tried": 0, "deadends": 0}

    def backtrack(assign):
        if len(assign) == len(domains):
            return dict(assign)
        # mrv: unassigned variable with the fewest remaining values
        var = min((v for v in domains if v not in assign),
                  key=lambda v: (len(domains[v]), v))
        for val in domains[var]:
            stats["tried"] += 1
            if all(assign.get(n) != val for n in neighbours[var]):
                assign[var] = val
                if (sol := backtrack(assign)) is not None:
                    return sol
                del assign[var]
        stats["deadends"] += 1
        return None

    return backtrack({}), stats

edges = [("a", "b"), ("a", "c"), ("b", "c"), ("c", "d")]

raw = {"a": ["r"], "b": ["r", "g"], "c": ["r", "g", "b"], "d": ["r", "g"]}
print("raw domains:      ", solve(raw, edges))

pruned = {"a": ["r"], "b": ["g"], "c": ["b"], "d": ["r", "g"]}   # post ac-3
print("after propagation:", solve(pruned, edges))

raw domains:       ({'a': 'r', 'b': 'g', 'd': 'r', 'c': 'b'}, {'tried': 7, 'deadends': 0})
after propagation: ({'a': 'r', 'b': 'g', 'c': 'b', 'd': 'r'}, {'tried': 4, 'deadends': 0})

same solution both ways, but propagation first means four value trials — one per variable, zero wasted — against seven on the raw domains. on a four-variable toy that saving is cute; on a thousand-task cumulative model it is the difference between milliseconds and heat death, because every value propagation deletes at the root would otherwise be refuted separately under exponentially many partial assignments. running AC-3 inside the search loop after every assignment is exactly the MAC strategy from the search section.

see also#

• integer programming — the branch-and-bound rival; same trees, different inference
• linear programming — the relaxation engine that rival runs on
• multi-objective programming — when “the” objective is several
• sudoku solver — alldifferent earning its keep on a 9x9 grid
• hashiwokakero — bridges, degrees and connectivity as a CSP

References#

Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford (2009). Introduction to Algorithms, MIT Press.

Epp, Susanna S. (2019). Discrete Mathematics with Applications, Cengage Learning.