A CSP is defined by THREE components: X a set of VARIABLES {X₁, …, Xₙ} D a set of DOMAINS {D₁, …, Dₙ}, one per variable, each a set of allowable values {v₁, …, vₖ} C a set of CONSTRAINTS specifying allowable combinations of values Each constraint Cᵢ is a pair ⟨scope, rel⟩ where SCOPE is the tuple of variables participating and REL is a relation defining the values those variables may take. AN ASSIGNMENT gives values to some or all variables. CONSISTENT (or legal) — violates no constraint COMPLETE — every variable is assigned PARTIAL — some variables are unassigned A SOLUTION is a consistent, complete assignment. WHY THIS IS DIFFERENT FROM ORDINARY STATE-SPACE SEARCH, and it is the whole point of the topic: · the state has a FACTORED representation — a set of variables with values, rather than an atomic black box (recall the representations from the agent structure topic) · so the solver can SEE WHY a state fails, not merely that it fails · which means it can prune whole regions rather than backtracking one step · and the GOAL TEST is decomposed into constraints, so partial assignments can be rejected before completion TYPES OF CONSTRAINT: UNARY involves one variable — effectively a domain reduction: SA ≠ green BINARY involves two variables: WA ≠ NT. A CSP with only binary constraints is a BINARY CSP and can be drawn as a CONSTRAINT GRAPH with variables as nodes and constraints as edges. HIGHER-ORDER / GLOBAL involves three or more. ALLDIFF(X₁…Xₙ) is the commonest, and every n-ary constraint can be converted to binary ones by introducing auxiliary variables — so binary CSP is fully general. PREFERENCE soft constraints expressing which solutions are better; a CSP with these is a CONSTRAINT OPTIMISATION PROBLEM. VARIETIES OF DOMAIN: DISCRETE, FINITE map colouring, scheduling — the standard case DISCRETE, INFINITE integer start times with no deadline; needs a constraint language rather than enumeration CONTINUOUS e.g. telescope observation windows; the best-known class is LINEAR PROGRAMMING

THE CLASSIC EXAMPLE — colouring the seven regions of Australia so that no two neighbours share a colour. VARIABLES WA, NT, Q, NSW, V, SA, T DOMAIN {red, green, blue} for each CONSTRAINTS the neighbouring pairs must differ: SA≠WA, SA≠NT, SA≠Q, SA≠NSW, SA≠V, WA≠NT, NT≠Q, Q≠NSW, NSW≠V (T is an island — no constraints at all) THE CONSTRAINT GRAPH: WA ──── NT ──── Q \ │ /│ \ │ / │ ─── SA ──── │ │ \ │ V ──── NSW T (isolated) NAIVE SEARCH: 3^7 = 2,187 complete assignments to test. With 4 colours it would be 4^7 = 16,384. BACKTRACKING SEARCH is the basic algorithm: assign one variable at a time, and backtrack as soon as a constraint is violated. function BACKTRACKING-SEARCH(csp) returns a solution or failure return BACKTRACK({}, csp) function BACKTRACK(assignment, csp) if assignment is complete then return assignment var ← SELECT-UNASSIGNED-VARIABLE(csp) for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) if value is consistent with assignment then add {var = value} to assignment inferences ← INFERENCE(csp, var, value) if inferences ≠ failure then add inferences to assignment result ← BACKTRACK(assignment, csp) if result ≠ failure then return result remove {var = value} and inferences from assignment return failure THE THREE PLACES TO BE CLEVER are the three named subroutines, and this is what the exam asks about. 1. VARIABLE ORDERING — MINIMUM REMAINING VALUES (MRV) Choose the variable with the FEWEST legal values remaining. Also called "most constrained variable" or "fail first". WHY IT WORKS: if a variable has only one legal value, assign it now — and if it has none, discover the failure immediately rather than after assigning ten other variables. WORKED: after WA=red and NT=green, SA has only {blue} left. MRV picks SA next, forcing the value and pruning everything that would have contradicted it. 2. TIE-BREAKING — DEGREE HEURISTIC Choose the variable involved in the most constraints on unassigned variables. Used to break MRV ties, and to pick the first variable when all domains are equal. WORKED: at the start every region has 3 values, so MRV cannot choose. SA has degree 5 — more than any other — so start there. Assigning SA first immediately reduces five other domains. 3. VALUE ORDERING — LEAST CONSTRAINING VALUE Prefer the value that rules out the fewest choices for the neighbouring variables. NOTE THE ASYMMETRY, which is a favourite exam point: FOR VARIABLES WE WANT TO FAIL FAST (most constrained first), BUT FOR VALUES WE WANT TO SUCCEED (least constraining first). The reason is that we need only ONE value to work, but ALL variables must be assigned. INFERENCE — the technique that makes CSPs tractable: FORWARD CHECKING When X is assigned, delete from the domain of each unassigned neighbour any value inconsistent with X. ✔ detects failure earlier than plain backtracking ✘ does not look ahead far enough to see all implications CONSTRAINT PROPAGATION AND ARC CONSISTENCY (AC-3) A variable Xᵢ is ARC-CONSISTENT with respect to Xⱼ if for every value in Dᵢ there is SOME value in Dⱼ satisfying the constraint. A network is arc-consistent when every arc is. AC-3 repeatedly revises arcs, re-queueing neighbours whenever a domain shrinks, until no domain changes. COMPLEXITY: O(cd³) for c binary constraints and domains of size d. WHAT FORWARD CHECKING MISSES AND AC-3 CATCHES: suppose after some assignments NT and SA both have domain {blue}. Forward checking sees nothing wrong — each has a legal value. AC-3 examines the arc NT–SA, finds that choosing blue for NT leaves nothing for SA, empties a domain, and reports failure immediately. THE POINT: propagation detects inconsistency BEFORE any further search, and detecting it one level earlier can prune an entire subtree. THE MEASURED EFFECT — published comparisons on hard CSPs show plain backtracking taking many millions of consistency checks on instances that MRV plus forward checking solves in a few thousand. THE HEURISTICS ARE NOT MARGINAL IMPROVEMENTS; they are the difference between solvable and not.

EXPLOITING PROBLEM STRUCTURE — the deepest idea in CSP: INDEPENDENT SUBPROBLEMS Tasmania is not connected to anything, so it is an independent subproblem and should be solved separately. Finding the CONNECTED COMPONENTS of the constraint graph decomposes the problem: if a CSP splits into subproblems of n/c variables each, the cost falls from d^n to (n/c)·d^c — LINEAR in n rather than exponential. WORKED: 80 variables, domain size 2, and suppose it splits into 20 subproblems of 4 variables. undecomposed: 2^80 ≈ 1.2 × 10^24 decomposed: 20 × 2^4 = 320 At a million nodes per second the first takes about 38 billion years and the second is instantaneous. TREE-STRUCTURED CSPs If the constraint graph is a TREE (no cycles), the CSP can be solved in O(n·d²) — POLYNOMIAL time. The method: pick a root, order the variables topologically, make each arc consistent with its parent working backwards, then assign forwards with no backtracking at all. THIS IS A GENUINELY IMPORTANT RESULT: the difference between exponential and polynomial is a property of the GRAPH'S SHAPE, not of the algorithm. CUTSET CONDITIONING If the graph is nearly a tree, find a small subset of variables (a CYCLE CUTSET) whose removal leaves a tree, enumerate its assignments, and solve the remaining tree quickly for each. Cost O(d^c · (n−c)d²) for a cutset of size c — practical when c is small. LOCAL SEARCH FOR CSPs — a completely different approach: Start with a complete but inconsistent assignment and repair it. The MIN-CONFLICTS heuristic reassigns the variable in a violated constraint to the value that minimises the number of remaining conflicts. ✔ REMARKABLY EFFECTIVE. Min-conflicts solves the million-queens problem in about 50 steps on average, essentially independent of n — a result that is genuinely startling next to systematic search. ✔ works well for ONLINE problems, where a schedule must be repaired after a disruption rather than recomputed ✘ INCOMPLETE: it can get stuck in a local minimum and cannot prove that no solution exists THE N-QUEENS COMPARISON, which puts the whole topic in one table: n = 8, naive assignment of a square per queen 8^8 = 16,777,216 candidates as a CSP, one queen per column, permutation formulation 8! = 40,320 n = 20, naive 20^20 ≈ 1.05 × 10^26 n = 20, permutation 20! ≈ 2.43 × 10^18 n = 1,000,000, min-conflicts local search about 50 STEPS THE PROGRESSION IS THE ARGUMENT OF THIS SECTION: better formulation, then better inference and ordering, then — where completeness can be sacrificed — a local method that ignores the size of the space entirely. Each step is a larger win than the last, and none of them is a faster computer.