Constraint Satisfaction Problems — Reading Notes

1.Defining Constraint Satisfaction Problems

In Topics 01–03 every state was atomic: a black box that the search algorithm could only generate, test for the goal, and compare by cost or utility. A constraint satisfaction problem (CSP) opens the box. A state is described by a set of variables, each holding a value, and the problem is solved when every variable has a value that satisfies all of the constraints on it. This factored representation lets general-purpose algorithms use the structure of the problem — which variables interact, and how — to prune huge parts of the search space at once.

1.1Variables, Domains & Constraints

A CSP consists of three components:

X — variables

A set {X1, …, Xn}.

D — domains

One domain Di = {v1, …, vk} of allowable values for each variable X_i.

C — constraints

Each constraint Cj = ⟨scope, rel⟩ names the variables it involves (its scope) and a relation saying which combinations of their values are allowed. The relation can be an explicit list of tuples or an abstract test such as X1 ≠ X2.

The running example is AIMA's map colouring of Australia: colour each state and territory red, green or blue so that no two neighbouring regions share a colour.

1.2Assignments & Solutions

An assignment gives values to some or all variables, e.g. {WA = red, NT = green}. It is consistent (or legal) if it violates no constraint, and complete if every variable has a value. A solution is a complete, consistent assignment. A partial assignment leaves some variables unassigned; a partial solution is a partial assignment that is consistent.

The key observation for search is that a partial assignment can already be inconsistent. As soon as WA and NT are both red, no extension of that assignment can be a solution, so an algorithm can discard every one of the 3⁵ = 243 ways of completing it in a single step. This is exactly what a black-box state representation cannot do.

1.3The Constraint Graph

A binary CSP is naturally drawn as a constraint graph: a node for each variable, and an edge between two variables whenever a constraint involves both. Structure is visible at a glance. Tasmania has degree 0 — it is an independent subproblem and can be coloured any way at all. South Australia has degree 5 — it is involved in more constraints than any other region, which makes it the natural variable to decide first (§3.2) and the natural variable to remove to break every cycle (§4.5).

1.4Kinds of Constraints

• Unary constraints restrict a single variable, e.g. ⟨(SA), SA ≠ green⟩.
• Binary constraints relate two variables, e.g. ⟨(SA, NSW), SA ≠ NSW⟩. A binary CSP has only unary and binary constraints and can be drawn as a constraint graph.
• Global (higher-order) constraints involve an arbitrary number of variables. The most common is Alldiff, which requires all of its variables to take different values — every row, column and box of a Sudoku. In a cryptarithmetic puzzle such as TWO + TWO = FOUR, Alldiff(F, T, U, W, R, O) is combined with column constraints like O + O = R + 10 · C1 that link letters to auxiliary carry variables C₁, C₂, C₃; these are drawn as a constraint hypergraph.

Every finite-domain constraint can be reduced to a set of binary constraints if enough auxiliary variables are introduced, or by building the dual graph in which constraints become variables. This is why most algorithms in this topic are stated for binary CSPs, although specialised propagation for global constraints (§2.5) is often far more efficient in practice.

1.5Hard vs. Soft Constraints: University Timetabling

So far every constraint has been absolute: violating it rules out a solution. Many real problems also contain preference constraints that say which solutions are better. A CSP with preferences is a constraint optimisation problem (COP): find a solution that satisfies all hard constraints and minimises the total penalty of the violated soft ones.

The Playground's Course Scheduling lab uses the following formulation. Each of the 12 course sessions is a variable; its domain is the set of (timeslot, room) pairs — 3 days × 4 periods × 4 rooms = 48 values.

A standard two-phase strategy is to find a feasible timetable with backtracking search (H2 and H4 are removed up front by node consistency, §2.1), and then improve the soft score with local search that never breaks a hard constraint (§4.1). In the engine's reference run, backtracking with MRV and forward checking finds a feasible timetable with 12 assignments and no backtracks; local search then lowers the soft penalty from 21 to 3.

1.6CSP as a Search Problem

A CSP can be solved by the search algorithms of Topic 02 using the incremental formulation:

Initial state

The empty assignment { }.

Actions

Assign a value to an unassigned variable, provided it does not conflict with the current assignment.

Goal test

The assignment is complete (and therefore, by construction, consistent).

Path cost

Irrelevant — every solution appears at depth n, so depth-first search is the natural choice.

Done naïvely, the branching factor at the top level is n · d (any variable, any value), at the next level (n − 1) · d, and so on: a tree with n! · dn leaves, even though there are only dn complete assignments. The fix is commutativity: the order in which values are assigned does not change the result, so it is enough to consider a single variable at each node of the tree. With that restriction the tree has exactly dn leaves. For Australia this is the difference between 7! · 3⁷ = 11,022,480 and 3⁷ = 2,187.

2.Constraint Propagation: Inference in CSPs

A search algorithm for atomic states can only search. A CSP algorithm can also infer: use the constraints to reduce the number of legal values for a variable, which in turn reduces the legal values of its neighbours, and so on. This is constraint propagation. It may be done as a preprocessing step, or interleaved with search (§3.4–3.5). The central idea is local consistency: treat each variable as a node and each binary constraint as an arc, and remove values that cannot be part of any solution because they fail some local test.

2.1Node Consistency

A variable is node-consistent if all the values in its domain satisfy its unary constraints; a network is node-consistent if every variable is. Node consistency is enforced once, by simply deleting offending values, after which all unary constraints can be dropped.

In the timetabling CSP, H2 and H4 are unary. For the ML Lab session AI302L (24 students, a lab, taught by Dr. Okafor who is unavailable on Monday), 36 of the 48 (slot, room) values fail H2 (the three lecture rooms) and 4 fail H4 (the Computer Lab on Monday), leaving a domain of just 8 values before search even begins.

2.2Arc Consistency

A variable X_i is arc-consistent with respect to X_j if for every value in D_i there is some value in D_j that satisfies the binary constraint on the arc (X_i, X_j). A network is arc-consistent if every variable is arc-consistent with every other variable. The basic operation is REVISE(Xi, Xj), which deletes every value of X_i that has no support in D_j.

AIMA's example: the constraint Y = X² with X, Y ∈ {0, …, 9}. Making X arc-consistent with Y leaves X ∈ {0, 1, 2, 3} (since 4² = 16 is out of range); making Y arc-consistent with X leaves Y ∈ {0, 1, 4, 9}. Note that arcs are directed — each direction is a separate revision.

Arc consistency does not always help. Colouring Australia with no pre-assignments, every value of every region has a different-coloured supporting value in each neighbour, so arc consistency removes nothing.

2.3The AC-3 Algorithm

AC-3 maintains a queue of arcs. Initially the queue holds every arc in the CSP (each binary constraint contributes two arcs). AC-3 pops an arbitrary arc (X_i, X_j) and revises it. If D_i is unchanged it moves on; if D_i shrank, every arc (X_k, X_i) that points into X_i must be re-checked and is added to the queue; if D_i became empty, the whole CSP has no consistent solution and AC-3 returns failure immediately.

function AC-3(csp) returns false if an inconsistency is found and true otherwise
    queue ← a queue of arcs, initially all the arcs in csp
    while queue is not empty do
        (Xi, Xj) ← POP(queue)
        if REVISE(csp, Xi, Xj) then
            if size of Di = 0 then return false
            for each Xk in Xi.NEIGHBORS − {Xj} do
                add (Xk, Xi) to queue
    return true

function REVISE(csp, Xi, Xj) returns true iff we revise the domain of Xi
    revised ← false
    for each x in Di do
        if no value y in Dj allows (x, y) to satisfy the constraint between Xi and Xj then
            delete x from Di
            revised ← true
    return revised

With c binary constraints and domains of size at most d, each arc can be re-inserted at most d times (once per deleted value of its tail) and each revision costs O(d²), so AC-3 runs in O(c · d³) time.

Run AC-3 on Australia after fixing WA = red and Q = green: revisions remove red and green from NT and from SA, leaving NT = {blue} and SA = {blue}; the arc (SA, NT) then empties D(SA) and AC-3 returns false. The partial assignment is shown to be hopeless with no search at all. With WA = red and NT = green instead, AC-3 forces SA = blue, Q = red, NSW = green and V = red — it colours the entire mainland by itself.

2.4Path Consistency & k-Consistency

Arc consistency can miss inferences. Try to colour the triangle WA–NT–SA with only two colours: every single value has a supporting value across each arc, so the network is arc-consistent — yet it obviously has no solution. Path consistency tightens binary constraints using implicit constraints inferred from triples: a two-variable set {X_i, X_j} is path-consistent with respect to X_m if for every consistent assignment {Xi = a, Xj = b} there is a value of X_m consistent with both. For the two-coloured triangle the only consistent pairs for {WA, NT} are {red, green} and {green, red}, and neither leaves a colour for SA; the PC-2 algorithm deletes both pairs and exposes the inconsistency.

More generally, a CSP is k-consistent if any consistent assignment to any k − 1 variables can be extended to any k-th variable. 1-consistency is node consistency, 2-consistency is arc consistency and 3-consistency is path consistency (for binary constraint networks). A graph that is strongly n-consistent can be solved without any backtracking, but establishing it takes time and space exponential in n in the worst case, so practical solvers stop at arc or path consistency.

2.5Global Constraints

Global constraints come with specialised propagation that is both faster and stronger than decomposing them into binary constraints. A simple test for Alldiff: if m variables are involved and only n distinct values remain in the union of their domains, and m > n, the constraint cannot be satisfied (the pigeonhole principle). Suppose NT, SA and Q are mutually adjacent and all three have been reduced to {green, blue}: an Alldiff check on {NT, SA, Q} sees 3 variables and 2 values and fails at once. The general algorithm repeatedly removes variables with singleton domains (and their value from the others), failing if a domain empties or more variables than values remain.

For resource constraints such as Atmost(10, P1, P2, P3) (at most 10 personnel in total), inconsistency is detected by summing the minimum values of the current domains; for large integer problems, domains are represented by lower and upper bounds and handled by bounds propagation.

2.6Sudoku as a CSP

A 9×9 Sudoku has 81 variables (one per cell) with domain {1, …, 9}; the givens have single-value domains. There are 27 Alldiff constraints — one per row, column and 3×3 box — so every cell has 20 peers. Enforcing arc consistency on the binary ≠ constraints solves the easy newspaper puzzles completely. For AIMA's hardest puzzles AC-3 leaves many candidates and search is required; interleaving AC-3 with backtracking (MAC, §3.5) and the MRV heuristic still solves them in milliseconds. On the Playground's "Hard" puzzle, for example, MAC + MRV needs 291 assignments, while plain backtracking gives up after 1.5 million constraint checks.

3.Backtracking Search for CSPs

Many CSPs cannot be solved by inference alone; at some point we must search. Backtracking search is a depth-first search that chooses values for one variable at a time and backtracks when a variable has no legal values left. It exploits commutativity (§1.6) by fixing one variable per level, and it checks consistency incrementally so that an inconsistent partial assignment is abandoned immediately.

3.1The Algorithm

function BACKTRACKING-SEARCH(csp) returns a solution or failure
    return BACKTRACK(csp, { })

function BACKTRACK(csp, assignment) returns a solution or failure
    if assignment is complete then return assignment
    var ← SELECT-UNASSIGNED-VARIABLE(csp, assignment)
    for each value in ORDER-DOMAIN-VALUES(csp, var, assignment) do
        if value is consistent with assignment then
            add {var = value} to assignment
            inferences ← INFERENCE(csp, var, assignment)
            if inferences ≠ failure then
                add inferences to csp
                result ← BACKTRACK(csp, assignment)
                if result ≠ failure then return result
                remove inferences from csp
            remove {var = value} from assignment
    return failure

The algorithm has three hooks that do not depend on the particular problem: SELECT-UNASSIGNED-VARIABLE (which variable next?), ORDER-DOMAIN-VALUES (in what order to try its values?) and INFERENCE (what can be deduced after each assignment?). Choosing them well is what separates a slow solver from a fast one. With a fixed variable order WA, NSW, NT, Q, SA, V, T and no inference, the engine needs 12 assignments and 5 backtracks to colour Australia: after WA = red, NSW = red and NT = green, Q must be blue and SA then has no colour; the algorithm must undo Q, NT and eventually NSW.

3.2Variable Ordering: MRV and the Degree Heuristic

The minimum-remaining-values (MRV) heuristic chooses the variable with the fewest legal values — also called the "most constrained variable" or "fail-first" heuristic. After WA = red and NT = green, SA has only blue left, so MRV assigns SA next rather than wandering off to Q, NSW or V. If some variable has zero legal values, MRV selects it and the failure is detected immediately, avoiding pointless searches through other variables. MRV typically performs orders of magnitude better than a static or random ordering.

MRV does not help with the first choice in Australia: every region starts with three values. The degree heuristic breaks the tie by choosing the variable involved in the largest number of constraints on other unassigned variables. SA has degree 5, T has degree 0. With SA chosen first, the map can be coloured with no backtracking at all. The degree heuristic is mainly used as a tie-breaker for MRV (MRV + Degree in the lecture and Playground).

3.3Value Ordering: Least-Constraining Value

Once a variable is chosen, the least-constraining-value (LCV) heuristic prefers the value that rules out the fewest choices for the neighbouring variables. After WA = red, NT = green, suppose Q is next. Q = green is illegal. Q = blue would remove SA's last value; Q = red leaves blue for SA. LCV therefore tries red first. The asymmetry with variable ordering is deliberate: a variable must eventually be assigned, so we pick the one most likely to fail early (fail-first), but we only need one solution, so we try the value most likely to succeed (fail-last).

3.4Forward Checking

Inference is most powerful when it is interleaved with search. The simplest form is forward checking: whenever a variable X is assigned, for each unassigned neighbour Y delete from D_Y any value inconsistent with the value chosen for X. If some D_Y becomes empty, the current branch fails immediately.

The table reproduces AIMA Figure 6.7. After WA = red, red is removed from NT and SA. After Q = green, green is removed from NT, SA and NSW — NT and SA are now both {blue}. After V = blue, blue is removed from NSW and SA, SA's domain becomes empty, and forward checking backtracks. Notice what forward checking missed: at the second row, NT and SA are adjacent and both forced to blue, which is already a contradiction. Forward checking only looks at the neighbours of the variable just assigned, so it cannot see it.

3.5Maintaining Arc Consistency (MAC)

The MAC algorithm fixes this. After a variable X_i is assigned, INFERENCE calls AC-3, but instead of a queue of all arcs it starts with only the arcs (Xj, Xi) for the unassigned neighbours X_j of X_i. From there AC-3 propagates in the usual way, and fails if any domain is emptied. In the example above, once NT is reduced to {blue} the arc (SA, NT) is examined and SA's last value disappears — one level earlier than forward checking. MAC is strictly more powerful than forward checking, because forward checking does the same work as MAC on the initial arcs but, unlike MAC, does not propagate further when a domain shrinks.

3.6Intelligent Backtracking: Looking Backward

When a branch fails, BACKTRACK returns to the most recently assigned variable — chronological backtracking. That is often the wrong place. Take the fixed order Q, NSW, V, T, SA with the partial assignment {Q = red, NSW = green, V = blue, T = red}. SA has no consistent value: red conflicts with Q, green with NSW, blue with V. Chronological backtracking tries T = green and T = blue, which cannot possibly help because Tasmania is not adjacent to SA.

A smarter approach keeps, for each variable, its conflict set: the assigned variables that ruled out one of its values. Here conf(SA) = {Q, NSW, V}. Backjumping jumps back to the most recent variable in the conflict set — V. When forward checking is used, the conflict set comes for free: when forward checking from an assignment X = x deletes a value from D_Y, it adds X to conf(Y). If the jump target also fails, conflict-directed backjumping merges the conflict sets, conf(Xj) ← conf(Xj) ∪ conf(Xi) − {Xj}, and keeps jumping. Constraint learning goes one step further and records the minimal set of variables responsible for a failure as a no-good, so the same contradiction is never rediscovered in another branch.

4.Local Search & the Structure of Problems

4.1Local Search: Min-Conflicts

Local search algorithms (Topic 02's hill climbing) turn out to be very effective for many CSPs. They use a complete-state formulation: every variable has a value, and each step changes the value of one variable. The min-conflicts heuristic picks a conflicted variable at random and gives it the value that results in the minimum number of conflicts with other variables, breaking ties randomly.

function MIN-CONFLICTS(csp, max_steps) returns a solution or failure
    current ← an initial complete assignment for csp
    for i = 1 to max_steps do
        if current is a solution for csp then return current
        var ← a randomly chosen conflicted variable from csp.VARIABLES
        value ← the value v for var that minimizes CONFLICTS(csp, var, v, current)
        set var = value in current
    return failure

Min-conflicts is surprisingly effective. On the n-queens problem (one queen per column; each queen's row is its value), its run-time is roughly independent of problem size: after a greedy initial assignment it solves even the million-queens problem in about 50 steps on average. In the engine's 8-queens demonstrations a random start is typically solved in a few dozen steps; a 60-queens board takes on the order of a hundred.

4.2Plateaus, Tabu Search & Constraint Weighting

The landscape of a CSP under min-conflicts often has plateaus: millions of assignments that are only one conflict away from a solution. Allowing sideways moves (to a value with the same number of conflicts) helps the search wander across them. Tabu search keeps a short list of recently visited states and forbids returning to them. Constraint weighting gives each constraint a numeric weight, initially 1; at each step the algorithm minimises the total weight of violated constraints, and then increases the weight of every constraint still violated. Constraints that are hard to satisfy therefore grow heavier, focusing the search on them.

A second advantage of local search is that it works online: when the problem changes — a flight is cancelled, a lecturer falls ill — the existing schedule can be repaired with a few moves instead of being rebuilt from scratch. This is how the Course Scheduling lab optimises its soft constraints.

4.3Independent Subproblems

The structure of the constraint graph can make a problem dramatically easier. The simplest case: if the graph has several connected components, each is an independent subproblem, and a solution is the union of the component solutions. Suppose n variables fall into components of c variables each, with domain size d. The total work is O(dc · n/c) — linear in n — instead of O(dn). With n = 80 Boolean variables split into four components of 20, this is the difference between 2⁸⁰ (longer than the lifetime of the universe at 10 million nodes per second) and 4 · 2²⁰ (a fraction of a second).

4.4Tree-Structured CSPs

A constraint graph is a tree when any two variables are connected by exactly one path. Any tree-structured CSP can be solved in time linear in the number of variables. The key is directional arc consistency (DAC): under an ordering X₁, …, X_n, a CSP is DAC if every X_i is arc-consistent with each X_j for j > i.

function TREE-CSP-SOLVER(csp) returns a solution, or failure
    n ← number of variables in X
    assignment ← an empty assignment
    root ← any variable in X
    X ← TOPOLOGICALSORT(X, root)
    for j = n down to 2 do
        MAKE-ARC-CONSISTENT(PARENT(Xj), Xj)
        if it cannot be made consistent then return failure
    for i = 1 to n do
        assignment[Xi] ← any consistent value from Di
        if there is no consistent value then return failure
    return assignment

After the backward pass, every parent value has a compatible value in each child, so the forward pass can assign variables from the root down with no backtracking. There are n − 1 arcs and each is revised once at cost O(d²), giving O(n · d²) overall. Exercise 6.6 traces the algorithm on the tree of AIMA Figure 6.10.

4.5Cutset Conditioning

Most graphs are not trees, but many are nearly trees. Cutset conditioning chooses a subset S of variables such that the constraint graph becomes a tree after S is removed — a cycle cutset. For each possible consistent assignment to S, it removes from the domains of the remaining variables any values inconsistent with that assignment, and solves the remaining tree-structured CSP. If the cutset has size c, the total run-time is O(dc · (n − c) · d²): very fast when c is small. In Australia, S = {SA}: after assigning SA, the rest of the map is the chain WA – NT – Q – NSW – V plus the isolated T.

4.6Tree Decomposition

A tree decomposition transforms the constraint graph into a tree of connected subproblems. Each subproblem is solved independently, and the resulting solutions are combined. A decomposition must satisfy three requirements: every variable appears in at least one subproblem; if two variables are connected by a constraint, they (and the constraint) appear together in at least one subproblem; and if a variable appears in two subproblems, it appears in every subproblem along the path connecting them. Australia decomposes into {WA, NT, SA}, {NT, SA, Q}, {SA, Q, NSW}, {SA, NSW, V} and {T} (AIMA Fig 6.13).

Each subproblem is solved and its solutions become the domain of a single "mega-variable"; constraints between mega-variables require shared variables to agree; and the resulting tree is solved with the tree algorithm. The tree width w of a decomposition is one less than the size of its largest subproblem (here w = 2); a CSP with tree width w can be solved in O(n · dw+1) time. Finding the decomposition with minimal tree width is NP-hard, but good heuristics exist.

Finally, value symmetry can be exploited: in map colouring, any permutation of the d colours of a solution is also a solution, so imposing an arbitrary symmetry-breaking constraint such as NT < SA < WA (alphabetical colour order) reduces the search space by a factor of d!.

5.Evaluating CSP Solvers

5.1Measuring Work

Wall-clock time depends on the machine and the implementation, so CSP solvers are usually compared by counting the work they do: the number of assignments (search nodes) tried, the number of backtracks, and the number of constraint checks. Inference trades checks for assignments — MAC performs more checks per node than forward checking, which performs more than plain backtracking — but on tightly constrained problems it explores so many fewer nodes that it wins overall. The lecture's live benchmark reproduces this on a 20-region random map: plain backtracking needs 1,113 assignments and 1,093 backtracks, whereas MRV + MAC finds a solution with just 20 assignments and no backtracking at all.

5.2Complexity

General finite-domain CSPs are NP-complete (they include 3-SAT as a special case), so no known complete algorithm is better than exponential in the worst case. Heuristics and inference do not change the worst case; they change the typical case, often by many orders of magnitude. Structure gives genuine polynomial special cases.

5.3Comparison Matrix

6.Practice Exercises

Eleven worked exercises covering formulation, AC-3, forward checking, ordering heuristics, min-conflicts and structure. Exercises 7–11 are adapted from the AIMA Chapter 6 exercise set (Exercises 6.5, 6.6, 6.8, 6.11 and 6.15), reworded and illustrated for clarity. Try each one before opening the answer; every answer was checked with the lecture's engine or a short solver script.

complete assignments = dn      = 37        = 2,187
naïve tree leaves    = n! · dn = 5,040 · 2,187 = 11,022,480

1. REVISE(X, Y): remove 4 from D(X)
     X {1,2,3}  Y {1,2,3,4}  Z {1,2,3,4}
2. REVISE(Y, X): remove 1 from D(Y)
     X {1,2,3}  Y {2,3,4}  Z {1,2,3,4}
3. REVISE(Y, Z): remove 4 from D(Y); re-queue (X, Y)
     X {1,2,3}  Y {2,3}  Z {1,2,3,4}
4. REVISE(Z, Y): remove 1, 2 from D(Z)
     X {1,2,3}  Y {2,3}  Z {3,4}
5. REVISE(X, Y): remove 3 from D(X)
     X {1,2}  Y {2,3}  Z {3,4}
queue empty → arc-consistent.    X {1,2}  Y {2,3}  Z {3,4}

SA : {blue}              → 1   (neighbours WA = red, NT = green)
Q  : {red, blue}         → 2   (neighbour NT = green)
NSW: {red, green, blue}  → 3
V  : {red, green, blue}  → 3
T  : {red, green, blue}  → 3
MRV chooses SA.

Q = red : SA {blue} (1 value), NSW {green, blue} (2)  → 3 values remain
Q = blue: SA {}     (0 value), NSW {red, green}  (2)  → SA wiped out
LCV order: red, then blue.

r = 1 : row with c3, diagonals with c1 and c4   → 3 conflicts
r = 2 : row with c1, diagonal with c3               → 2 conflicts
r = 3 : diagonal with c1, row with c4               → 2 conflicts
r = 4 : no row or diagonal shared                    → 0 conflicts

MAKE-ARC-CONSISTENT(D, F) : no change
MAKE-ARC-CONSISTENT(D, E) : remove G from D(D) → D(D) = {B}
MAKE-ARC-CONSISTENT(B, D) : no change
MAKE-ARC-CONSISTENT(B, C) : remove R from D(B) → D(B) = {G}
MAKE-ARC-CONSISTENT(A, B) : remove G from D(A) → D(A) = {R}

A = R   (root)
B = G   (≠ parent A = R)
C = R   (≠ parent B = G)
D = B   (≠ parent B = G)
E = G   (≠ parent D = B)
F = G   (≠ parent D = B)

c = 1, n = 7, d = 3
cutset conditioning : dc · (n − c) · d² = 3 · 6 · 9 = 162
brute force         : dn              = 37       = 2,187

C1 : O, R, W, U, C2            → degree 5
C2 : C1, W, U, T, O, C3        → degree 6   ← chosen
C3 : C2, T, O, F               → degree 4

T = 5 : O = 2·5 − 10 = 0   → units: R = O+O = 0 = O   ✗ D(R) = ∅
T = 6 : O = 2, R = 4        → tens: U = 2W (C1 = C2 = 0)
        W ∈ {0,…,4} \ {1,2,4} = {0,3} → U = 0 (= W) or 6 (= T)  ✗ every U fails
T = 7 : O = 4, R = 8        → U = 6, W = 3                         ✓

D(X) = {⟨1,1⟩, ⟨1,2⟩, ⟨1,3⟩, ⟨2,1⟩, ⟨2,2⟩, ⟨2,3⟩}     (2 × 3 = 6 pairs)

⟨X, A⟩ :  A = X1
⟨X, B⟩ :  B = X2
⟨X, C⟩ :  C = X1 + X2

REVISE(X, C): keep pairs whose sum is in D(C) = {3, 4}
  ⟨1,1⟩ sum 2 ✗   ⟨1,2⟩ sum 3 ✓   ⟨1,3⟩ sum 4 ✓
  ⟨2,1⟩ sum 3 ✓   ⟨2,2⟩ sum 4 ✓   ⟨2,3⟩ sum 5 ✗
  → D(X) = {⟨1,2⟩, ⟨1,3⟩, ⟨2,1⟩, ⟨2,2⟩}
REVISE(A, X): A = 1 ✓ (⟨1,2⟩), A = 2 ✓ (⟨2,1⟩)   → no change
REVISE(B, X): B = 1 ✓, 2 ✓, 3 ✓ (⟨1,3⟩)           → no change
REVISE(C, X): C = 3 ✓, C = 4 ✓                    → no change

#1 A1 = R
#2 H  = G      (R taken by A1)
#3 A4 = R      (only H is assigned among its neighbours)
#4 F1 = R      (T not assigned yet)
#5 A2 = B      (R by A1, G by H)                 conf(A2) = {A1, H}
#6 F2 = R
#7 A3 : R ✗ by A4,  G ✗ by H,  B ✗ by A2        conf(A3) = {A4, H, A2}

Jump ① from A3: most recent in {A4, H, A2} is A2   (F2 is skipped)
        conf(A2) = {A1, H} ∪ {A4, H, A2} − {A2} = {A1, H, A4}
        A2 has no values left (B was its only legal value)
Jump ② from A2: most recent in {A1, H, A4} is A4   (F1 is skipped)
        A4 : G ✗ (H),  B ✓  → A4 = B

#4 F1 = R   #5 A2 = B   #6 F2 = R
#7 A3 = R   (A2 = B, A4 = B, H = G → R is free)
#8 T  = B   (H = G, F1 = F2 = R)

 1. REVISE(SA,  WA) : remove G  → SA  = {R, B}
 2. REVISE(SA,  V ) : remove R  → SA  = {B}        arcs into SA re-queued
 3. REVISE(NT,  WA) : remove G  → NT  = {R, B}
 4. REVISE(NSW, V ) : remove R  → NSW = {G, B}
 5. REVISE(NT,  SA) : remove B  → NT  = {R}
 6. REVISE(Q,   SA) : remove B  → Q   = {R, G}
 7. REVISE(NSW, SA) : remove B  → NSW = {G}
 8. REVISE(Q,  NSW) : remove G  → Q   = {R}
 9. REVISE(Q,   NT) : remove R  → Q   = { }         ✗ empty → return false

1. (B, C): B = R has no support (C = R)  → D(B) = {G}
2. (A, D): every A value has support    → no change
3. (A, B): A = G has no support (B = G)  → D(A) = {R}
Forward pass: A = R, B = G, D = G, C = R   ✓ no backtracking

1. (A, B): both A values have support (B still {R, G}) → no change
2. (A, D): no change
3. (B, C): B = R has no support                         → D(B) = {G}
Forward pass: A = G (first value) → B must be ≠ G but D(B) = {G}   ✗ backtrack