Constraint Satisfaction Problems

After this page you can model a problem as a CSP, run backtracking search by hand, filter with forward checking and AC-3, and explain exactly why MRV and LCV pull in opposite directions.

1. Planning problems vs. identification problems

Every search problem so far — BFS, DFS, UCS and A* — was a planning problem: you knew the goal and were asked how to get there, so the answer is a sequence of actions. Paths have costs (there is a best one) and depths (a shallow goal is cheaper, which is why BFS is complete and DFS is not), and a heuristic $h(n)$ is useful because it estimates remaining distance.

In an identification problem the answer is an assignment of values to variables, and nobody cares how you found it — like a completed crossword, where the order in which you wrote the letters is not part of the answer.

That last row is the whole chapter. Because every solution is at depth $n$, a heuristic saying "you're getting closer" tells us nothing — on every branch we are exactly $n - |\text{assigned}|$ steps from completion. In planning you ask "am I close?"; in identification you ask "am I doomed?", and every algorithm below is a device for discovering that you are doomed as early as possible, so you can stop digging.

2. What exactly is a CSP?

In a standard search problem a state is an arbitrary data structure and the goal test is any function over states. That generality is why generic search can do nothing clever — it cannot look inside either one. A CSP gives up the generality on purpose and gets algorithms in exchange.

The clause that does all the work is "for subsets of the variables". A general goal test is a black box over the whole state, so every variable must be filled before you may call it. A constraint mentions two or three variables, so it can be evaluated on a partial assignment the instant those few are filled. Early failure detection is the entire performance story of this chapter.

3. Why bother? Where CSPs show up

An enormous number of real problems are, once you squint, "assign values to variables so that a pile of local rules all hold". The course's list:

Some instances involve real-valued variables — a start time is a real number, not a colour — which §8 returns to.

4. The running example: colouring Australia

The whole lecture runs on one instance, so it is worth setting up carefully: colour the seven regions of Australia so that no two regions sharing a border get the same colour, using only three colours.

The nine borders — memorise these, every worked example below uses them:

WA–NT   WA–SA   NT–SA   NT–Q   SA–Q   SA–NSW   SA–V   Q–NSW   NSW–V
Tasmania borders nothing.

Verify that solution border by border: WA(red)≠NT(green) ✓, WA(red)≠SA(blue) ✓, NT(green)≠SA(blue) ✓, NT(green)≠Q(red) ✓, SA(blue)≠Q(red) ✓, SA(blue)≠NSW(green) ✓, SA(blue)≠V(red) ✓, Q(red)≠NSW(green) ✓, NSW(green)≠V(red) ✓. All nine hold. T is unconstrained, so any of its three colours works — our first hint about structure.

5. Constraint graphs

The right-hand picture above is such a graph, and it is what the general-purpose algorithms operate on. Note what it throws away: it records that WA and NT are constrained, not how. That is the point — an algorithm written against the graph works for map colouring, scheduling and n-queens alike, because it needs a constraint's scope, never its semantics.

Three ways graph structure speeds up search:

1. Connected components. Tasmania is isolated, so it is an independent subproblem: components of sizes $n_1, n_2$ solved separately cost $O(d^{n_1}) + O(d^{n_2})$ instead of $O(d^{n_1 + n_2})$ — for Australia, $3^6 + 3^1 = 732$ instead of $3^7 = 2187$.
2. Degree. A high-degree node (SA, degree 5) constrains many neighbours, so assigning it early prunes a lot — the "degree heuristic", MRV's tie-breaker.
3. Global shape. If the graph is a tree, the CSP is solvable in $O(n d^2)$ with no backtracking. beyond syllabus See §18.

6. N-queens, modelled twice

The lecture puts up two formulations of n-queens and leaves both blank. That blank is the single most useful exercise in the chapter, because it shows that modelling choices are algorithmic choices: the same puzzle, written down two ways, differs by a factor of $10^{12}$ in search-space size before any clever algorithm is applied.

The puzzle: place $n$ queens on an $n \times n$ chessboard so that no two attack each other — no shared row, column or diagonal.

Formulation 1 — one Boolean per square

Write the constraints explicitly. For every pair of squares that attack each other, we forbid the combination "both are 1". The allowed pairs are therefore $\{(0,0),(0,1),(1,0)\}$ — everything except $(1,1)$:

Indices stay on the board ($1 \le i+k \le n$ and so on). The first four families are binary, so they fit the constraint-graph picture of §5; the fifth does not — the count constraint mentions all $n^2$ variables at once. That global constraint is the ugly part of this model.

Size of the search space. There are $n^2$ variables each with $2$ values, so the number of complete assignments is

For $n = 8$ that is $2^{64} \approx 1.845 \times 10^{19}$. If you could test a billion assignments per second you would need about 585 years.

Formulation 2 — one variable per column

Use a modelling trick that appears everywhere in CSPs: build a constraint into the variables themselves. Exactly one queen goes in each column (two would share the column; if some column had none then with $n$ queens in $n$ columns another has two). So instead of "is there a queen here?", ask "which row holds column $k$'s queen?".

The diagonal condition is the one people mis-derive. Two queens sit at $(i, Q_i)$ and $(j, Q_j)$ in (column, row) coordinates, and they share a diagonal exactly when the horizontal distance equals the vertical distance, $|i - j| = |Q_i - Q_j|$. Forbidding that gives $|Q_i - Q_j| \neq |i-j|$. One absolute-value equation covers both diagonal directions, which is why formulation 2 needs one condition where formulation 1 needed two families.

Verify the explicit list for $n=4$, which the course writes with a "…" and moves on. We need $Q_1 \neq Q_2$ and $|Q_1 - Q_2| \neq |1-2| = 1$ — the two rows must differ by at least $2$:

Six allowed pairs out of sixteen: $(1,3), (1,4), (2,4), (3,1), (4,1), (4,2)$ — exactly the set above. That was one of the $\binom{4}{2} = 6$ constraints; for $n = 8$ you would fill $\binom{8}{2} = 28$ tables of $64$ cells. The implicit form says the same thing in two lines of algebra and costs two instructions to test instead of a table lookup.

Why formulation 2 wins

Count complete assignments again. Formulation 2 has $n$ variables with $n$ values each:

For $n = 8$: 16.8 million assignments instead of 18.4 quintillion. Three further things improve, and they matter more than the raw count:

1. Two constraint families vanish. "One queen per column" and "exactly $n$ queens" are now impossible to violate, and a constraint you cannot violate costs nothing to enforce. The best way to satisfy a constraint is to choose variables that cannot express its violation.
2. The CSP becomes purely binary. The $n^2$-ary count constraint is gone, so the constraint graph is a clean $K_n$ and every algorithm here applies directly.
3. Every assignment is closer to a solution. Formulation 1's assignments mostly have the wrong number of queens entirely; in formulation 2 every assignment is a legal-looking board and $40{,}320$ of the $16{,}777{,}216$ are row-distinct permutations. A space dense in near-solutions is what makes filtering effective.

7. Sudoku as a CSP

Sudoku is the canonical CSP because it is the one you have already solved by hand, using — whether you knew it or not — exactly the algorithms in this chapter.

alldiff$(V_1,\dots,V_9)$ holds exactly when all nine values are pairwise distinct. Each mentions nine variables, so this is a higher-order CSP and the constraint-graph machinery of §5 does not literally apply.

Decomposing into binary constraints

The course's alternative: replace each 9-way alldiff by all $\binom{9}{2} = 36$ pairwise $\neq$ constraints. The CSP is then binary and every algorithm below runs unmodified.

How many? Naively $27 \times 36 = 972$, but that double-counts — two squares in the same row and region generate the same constraint twice. Count by squares: each has $8$ row-peers, $8$ column-peers and $8$ region-peers of which $4$ are already row- or column-peers, so $8+8+4 = 20$ distinct peers, and

distinct constraints — divide by two because each is shared by the two squares it relates. So $810$ edges over $81$ nodes.

One observation for §17: when a human solves Sudoku, "this square can only be a 7, so write 7" is precisely minimum remaining values, and "cross 7 off every peer of this square" is precisely forward checking. You already run these algorithms; this chapter names them.

8. Varieties of CSPs

Everything so far assumed discrete variables with finite domains. With $n$ variables and domain size $d$ there are $d^{\,n}$ complete assignments, so brute-force enumeration is $O(d^{\,n})$ — and it stays exponential no matter how clever we are, because:

So no algorithm below changes the worst-case complexity. Forward checking, AC-3, MRV and LCV are heuristics and pruning rules: they shrink the tree enormously on realistic instances and change nothing at all in the worst case.

The formalism is wider than finite domains, and the slides hand the rest to 07-380. Domains can be discrete but infinite — job scheduling with integer start times — where an explicit table of allowed tuples is not a data structure and you need a constraint language instead, writing things like $\text{Start}_{J_1} + 5 \le \text{Start}_{J_3}$; linear integer constraints are solvable, nonlinear ones are undecidable (Matiyasevich 1970, Hilbert's tenth problem). Or variables can be continuous — Hubble observation windows — where with linear constraints feasibility is solvable in polynomial time by linear programming.

9. Varieties of constraints

Constraints vary along a second axis: arity, how many variables one constraint mentions.

Unary constraints

One variable: "South Australia dislikes green", $\text{SA} \neq \text{green}$. These are free, because a statement about which values one variable may take is a domain. Delete the forbidden values once, before search, and forget the constraint existed — the course's "equivalent to reducing domains". So $D_{\text{SA}} = \{\text{red},\text{green},\text{blue}\}$ becomes $\{\text{red},\text{blue}\}$, in $O(d)$, once, forever.

Binary constraints

Exactly two variables: $\text{SA} \neq \text{NSW}$. The focus of the lecture, because these are exactly the constraints that give a constraint graph, and a graph is a thing algorithms can walk.

Higher-order constraints

Three or more: the Sudoku alldiff of §7, or a cryptarithmetic column (two digits, a carry in and a carry out — four variables). A $k$-ary constraint is a hyperedge on $k$ nodes, giving a hypergraph; the standard move is to decompose into binary constraints.

Soft constraints (preferences)

Everything so far is hard: an assignment satisfies the constraints or it is not a solution. Real problems also have preferences — the course's example is "red is better than green".

Concretely: suppose every region costs $0$ for red, $1$ for green and $3$ for blue. The solution from §4 — WA red, NT green, SA blue, Q red, NSW green, V red, T green — costs $0+1+3+0+1+0+1 = 6$. Recolouring T from green to red is still legal (T has no neighbours) and costs $5$, so that solution was valid but not optimal. Under hard constraints only, both are equally correct answers; under preferences, only one is.

10. A CSP is a search problem

Before inventing anything new, check that the search machinery of Chapter 2 already applies. It does, verbatim.

Three consequences follow immediately:

1. Solutions appear only at depth $n$: each step assigns one variable, and the goal test demands all $n$.
2. There are no infinite paths and no cycles — every step strictly increases the number of assigned variables.
3. The branching factor is $(n-\ell)\,d$ at depth $\ell$: any of the $n - \ell$ unassigned variables, times any of its $d$ values.

That third point is a disaster. Multiplying the branching factors down the tree,

and for Australia ($n = 7$, $d = 3$),

while there are only $3^7 = 2187$ distinct complete assignments. Every assignment is reached $5040$ times, once per ordering of the seven variables. Fixing that is Idea 1 of §11.

The naive algorithm: DFS with the goal test at the bottom

The course's starting point is deliberately dumb: assign a value at each node, and check the constraints only when the assignment is complete — the goal test as the black box of general search. So we build $\text{WA}=\text{red},\ \text{NT}=\text{red}$, already illegal, and extend it through five more variables, generating $3^5 = 243$ complete assignments under a prefix that was dead on arrival and rejecting all $243$ one at a time.

Poll 1 — should we use BFS or DFS?

So: depth-first search, with improvements bolted on.

11. Backtracking search

Idea 1 — one variable at a time

Variable assignments are commutative:

Both are the set $\{\text{WA}=\text{red},\ \text{NT}=\text{green}\}$, and a set has no order, so a search exploring both orderings explores each state $\ell!$ times at depth $\ell$. The fix is one line of code: at each node, fix one variable and branch only on its values. Which variable is up to you; what matters is that you pick one and do not consider the others at this node.

Quantifying the saving. Branching factor drops from $nd$ to $d$; the leaf count drops from $n!\,d^{\,n}$ to $d^{\,n}$; that is a factor of $n!$.

Idea 2 — check constraints as you go

Consider only values that do not conflict with previous assignments. Testing each candidate against the already-assigned neighbours costs a little computation, but nothing compared with the subtree avoided. The course calls this the incremental goal test: a small test at every node instead of one big test at depth $n$. Concretely, with $\text{WA}=\text{red}$ assigned, we simply never generate the child $\text{NT}=\text{red}$ — which naive DFS would have grown $3^5 = 243$ complete assignments beneath before noticing.

The algorithm in full

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


function RECURSIVE-BACKTRACKING(assignment, csp) returns a solution, or failure

    if assignment is complete then
        return assignment                          # every variable has a value, and
                                                   # every value was checked on the way in

    var  <- SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp], assignment, csp)     # decision point 1

    for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do          # decision point 2

        if value is consistent with assignment given CONSTRAINTS[csp] then  # decision point 3
            add {var = value} to assignment
            result <- RECURSIVE-BACKTRACKING(assignment, csp)
            if result != failure then
                return result
            remove {var = value} from assignment   # <- this line is the "backtrack"

    return failure                                 # no value for var works; tell the caller

Three lines are worth reading twice.

• if assignment is complete then return assignment — no constraint check here, and none is needed: every value was checked when it was added, so a complete assignment is automatically consistent. The course states this explicitly ("no need to check constraints for a complete assignment"); it is the pay-off of the incremental goal test.
• if value is consistent with assignment — Idea 2. It checks only constraints between var and the already assigned variables; constraints between two unassigned variables are not testable yet.
• remove {var = value} from assignment — the actual backtrack. An implementation that maintains filtered domains must also restore the domains here. return failure is reached when the loop is exhausted: no value of var works, so the subtree is dead. (SELECT-UNASSIGNED-VARIABLE and ORDER-DOMAIN-VALUES are sound for any choice and any order; MRV and LCV make them smart in §17.)

With just these two improvements, backtracking search solves n-queens for $n \approx 25$. That is the honest number from the course: not thousands, twenty-five. Hold onto it — by §17 the same basic algorithm will handle $n = 1000$.

12. Filtering, part 1: forward checking

Backtracking still wastes effort in a specific, diagnosable way. The state $\{\text{WA}=\text{red},\ \text{Q}=\text{green},\ \text{V}=\text{blue}\}$ is perfectly consistent — no two of WA, Q, V even share a border — but it is already dead: SA borders all three, so SA can be neither red nor green nor blue. Plain backtracking will not discover this until it actually gets to SA, after building every combination of NT and NSW above it.

The Australia trace

Assign $\text{WA}=\text{red}$, then $\text{Q}=\text{green}$, then $\text{V}=\text{blue}$, maintaining domains. Every domain starts $\{\text{R},\text{G},\text{B}\}$. Borders: WA–NT, WA–SA, NT–SA, NT–Q, SA–Q, SA–NSW, SA–V, Q–NSW, NSW–V.

• WA = red. Unassigned neighbours NT and SA: delete R from both. Q, NSW, V and T do not border WA and are untouched.
• Q = green. Unassigned neighbours NT, SA, NSW: delete G from each. NT $\{$G,B$\} \to \{$B$\}$, SA $\{$G,B$\} \to \{$B$\}$, NSW $\{$R,G,B$\} \to \{$R,B$\}$. No domain is empty, so forward checking permits the search to continue.
• V = blue. Unassigned neighbours SA and NSW: delete B from each. NSW $\{$R,B$\} \to \{$R$\}$, fine. SA $\{$B$\} \to \{\,\}$ — empty. FAIL: a variable with no possible values. Backtrack.

13. Consistency of a single arc

Forward checking is a special case of something more general, and naming the general thing lets us strengthen it. The general thing is arc consistency.

$x$ ranges over the values left in $D_X$, $y$ over those left in $D_Y$, and "does not violate" means the pair is allowed by the constraint (for map colouring, $x \neq y$). A $y$ that works for a given $x$ is a support for $x$. So: the arc $X \to Y$ is consistent iff every value in the tail has at least one support in the head.

Forward checking, re-read as arc consistency

The course writes forward checking as

Unpack it. $Y$ was just assigned, so $D_Y$ is a singleton $\{c\}$, and $X$ ranges over $Y$'s neighbours. Enforcing $X \to Y$ deletes from $D_X$ every value with no support in $\{c\}$ — and for a $\neq$ constraint the only value without support is $c$ itself. So those arcs delete exactly $c$ from each neighbour's domain: forward checking, verbatim.

Full arc consistency is strictly stronger: it makes every deletion forward checking makes, and possibly more, for two separate reasons worth keeping apart.

1. More arcs. Forward checking only examines arcs $X \to Y$ with $Y$ just assigned, never an arc between two unassigned variables. Arc consistency examines all of them — which is exactly how it catches "NT and SA are both forced to blue and share a border".
2. Propagation. When forward checking removes a value from $D_X$ it stops. Arc consistency asks whether shrinking $D_X$ destroyed the support of some value in a third variable $W$ neighbouring $X$; if so that value dies too, which may destroy support elsewhere, and so on. Deletions cascade. Forward checking has no cascade — it is one layer deep.

14. AC-3: enforcing arc consistency on the whole CSP

Knowing how to enforce one arc, we need every arc consistent at once. The difficulty is that the arcs interact: enforcing $X \to Y$ shrinks $D_X$, which can break an arc $W \to X$ that was consistent a moment ago. One pass is not enough.

The simplistic algorithm

repeat
    changed <- false
    for each ordered pair (X, Y) of variables joined by a constraint do
        if enforcing X -> Y removes any value then changed <- true
until changed = false

Correct — it stops only at a fixed point, and a fixed point is by definition arc-consistent — and wasteful: one full cycle costs $O(|E| d^2)$ even if the only thing that changed was a single value, and you may need many cycles.

AC-3

function AC-3(csp, queue) returns false if an inconsistency is found, true otherwise
    # queue defaults to ALL directed arcs (Xi, Xj) of the constraint graph --
    # both directions of every edge

    while queue is not empty do
        (Xi, Xj) <- REMOVE-FIRST(queue)

        if REVISE(csp, Xi, Xj) then                 # Di actually shrank
            if size of Di = 0 then
                return false                        # wipeout: this CSP branch is dead

            for each Xk in NEIGHBORS(Xi) \ {Xj} do
                add (Xk, Xi) to queue               # Di shrank, so everyone who
                                                    # depends on Di must be re-checked
    return true


function REVISE(csp, Xi, Xj) returns true iff we removed something from Di
    revised <- false
    for each x in Di do
        if no value y in Dj satisfies the constraint between Xi and Xj given x then
            delete x from Di                        # DELETE FROM THE TAIL
            revised <- true
    return revised

The lecture's Australia trace, compressed

We are inside backtracking search, running AC-3 after each assignment, with WA = red and then Q = green.

Phase 1 — AC-3 after WA = red. $D_{\text{WA}} = \{$R$\}$, everything else $\{$R,G,B$\}$. The queue is seeded with the arcs pointing at the newly assigned variable, $\text{SA}\to\text{WA}$ and $\text{NT}\to\text{WA}$. Each deletes R from its tail — $D_{\text{SA}} = D_{\text{NT}} = \{$G,B$\}$ — and each enqueues every arc into the variable that shrank (WA→SA, NT→SA, Q→SA, NSW→SA, V→SA; then WA→NT, SA→NT, Q→NT). All of those pass: WA→SA finds R supported by G $\in D_{\text{SA}}$, NT→SA compares $\{$G,B$\}$ with $\{$G,B$\}$ and finds G supported by B and B by G, and so on. Nothing more is deleted, so nothing more is enqueued and the queue drains. The CSP is arc-consistent and search continues, leaving $D_{\text{WA}} = \{$R$\}$, $D_{\text{NT}} = D_{\text{SA}} = \{$G,B$\}$ and $D_{\text{Q}} = D_{\text{NSW}} = D_{\text{V}} = D_{\text{T}} = \{$R,G,B$\}$.

Phase 2 — AC-3 after Q = green. Set $D_{\text{Q}} = \{$G$\}$ and seed the queue with the arcs into Q: $\text{NT}\to\text{Q}$, $\text{SA}\to\text{Q}$, $\text{NSW}\to\text{Q}$.

Note the mechanism, because it is the whole point: the deletion at NT in the first step put SA→NT onto the queue, and processing that re-queued arc is what found the contradiction. That cascade is what forward checking does not have.

Where AC-3 fits, and what it costs

AC-3 runs either as a preprocessor — once on the raw CSP before any search, cheaply shrinking every domain permanently, and occasionally proving the whole problem infeasible before you begin — or after each assignment inside the recursion, seeded with the arcs into the just-assigned variable, with its effects undone on backtrack.

15. The limitations of arc consistency

AC-3 returning true feels like a certificate. It is not one. After enforcing arc consistency you may be in any of three situations:

Case 3 is the one to internalise, and it is what the lecture's "What went wrong here?" slide is pointing at.

16. The cost of one run of AC-3

The lecture derives the bound in four steps, each one line.

Sanity-check the factors against Australia: $n = 7$, $d = 3$, giving $n^2 d^3 = 49 \times 27 = 1323$ constraint checks as an upper bound for one call. The trace in §14 used about 15 arcs and a few dozen checks — the bound is loose, as worst-case bounds are, but it is the right shape.

The tightened bound. beyond syllabus Zhang and Yap (2001) showed that the true worst case of AC-3 is $O(n^2 d^2)$, a factor of $d$ better, by not repeating the $d^2$ support scan from scratch on every visit to an arc. The lecture marks this "not required"; the classroom answer is $O(n^2d^3)$.

Where do you run AC-3? — the lecture's question, answered

function BACKTRACKING-WITH-AC3(csp) returns a solution, or failure
    if AC-3(csp, queue = ALL-ARCS(csp)) = false then
        return failure                                  # preprocessing pass: whole CSP is dead
    return RECURSE({}, csp)


function RECURSE(assignment, csp) returns a solution, or failure
    if assignment is complete then return assignment

    var <- SELECT-UNASSIGNED-VARIABLE(...)              # MRV (see section 17)

    for each value in ORDER-DOMAIN-VALUES(var, ...) do  # LCV (see section 17)

        if value is consistent with assignment then
            add {var = value} to assignment
            saved <- copy of all current domains        # so we can undo the filtering
            D[var] <- {value}

            queue <- { (W, var) : W in NEIGHBORS(var) } # only the arcs into var
            if AC-3(csp, queue) then                    # no domain wiped out
                result <- RECURSE(assignment, csp)
                if result != failure then return result

            restore all domains from saved              # undo filtering, then
            remove {var = value} from assignment        # undo the assignment

    return failure

Two details are easy to get wrong and both are fatal:

• saved <- copy of all current domains must happen before D[var] <- {value}, and the restore must happen on every exit from the loop body that does not return a solution — including the path where AC-3 returns false.
• The queue is seeded with arcs pointing at var, i.e. $(W, \textit{var})$ with $W$ the tail. Seeding $(\textit{var}, W)$ instead is the classic direction bug: those arcs are already consistent, the propagation never starts, and your solver silently degenerates into plain backtracking.

17. Ordering: MRV and LCV

Filtering answered "can we detect inevitable failure early?". Ordering answers the lecture's other two questions about improving backtracking: which variable should be assigned next (the SELECT-UNASSIGNED-VARIABLE hook) and in what order should its values be tried (the ORDER-DOMAIN-VALUES hook). Both are pure speed — correctness does not depend on them, since the soundness proof in §11 allowed any choice. And, the part students consistently get backwards, the two questions have opposite answers.

Variable ordering: minimum remaining values

MRV needs filtering to be running — "values left in its domain" is only meaningful if someone is crossing values off. In practice MRV is always paired with forward checking or AC-3.

Tie-breaking. Several variables often tie on domain size — at the start of Australia all seven have three values. The standard tie-breaker is the degree heuristic of §5: among the tied variables, pick the one with the most constraints on unassigned variables. In Australia that is SA (degree 5), precisely the variable we want at the root.

Value ordering: least constraining value

The payoff. The lecture's headline: these ordering ideas make 1000-queens feasible, against the $n \approx 25$ plain backtracking managed in §11. Same algorithm, same exponential worst case — but filtering and ordering together keep realistic instances out of the exponential region entirely.

18. Summary

The chapter in five lines:

Structure, and what is left for later

The lecture lists structure as the third family of speed-ups and puts it in parentheses: mentioned, not covered. beyond syllabus Independent subproblems — solve each connected component separately. Tree-structured CSPs — $\mathbf{O(n d^2)}$ with no backtracking: root the tree, REVISE each parent→child arc from the leaves up, then assign forwards, every value guaranteed to extend (Guided problem 2 was an instance, which is why arc consistency alone solved it). Cutset conditioning — enumerate all $d^{|S|}$ assignments to a cycle cutset $S$ whose removal leaves a tree and solve that tree in $O(nd^2)$ each time, total $O(d^{|S|} \cdot n d^2)$; for Australia removing SA alone leaves a path plus isolated T, so $|S| = 1$ — the formal reason SA kept showing up as the bottleneck. Tree decomposition — $O(n d^{\,w+1})$ for treewidth $w$.

Also deferred: local search for CSPs (min-conflicts hill climbing — start from a complete, broken assignment and repair it; this is what really solves million-queens), continuous and infinite-domain CSPs (§8, handed to 07-380), constrained optimisation for the soft constraints of §9, which needs branch-and-bound rather than "stop at the first solution", and specialised propagators such as the alldiff algorithm §7's pigeonhole example calls for.

Next, in Chapter 5, the problem changes shape again: another agent gets to choose some of the values, and it is not on your side.