Does a solution exist at all?
Integer programming (topic 04) is where the corner theorem stops being enough, and branch and bound (05) is the machinery that copes. Topic 19 shares this course's language of variables and constraints but drops the objective: sometimes the honest question is not “what's best” but “does anything work at all.” Topic 21 asks when the simplest rule of thumb is provably good enough, and topic 10 is what you reach for once exact methods die.
Stop and notice what every topic before this one has in common, including this course's own four-line opening. There has always been an objective: a number to push up or down, a plan to call "best." Constraint satisfaction has no objective at all. The only question is whether some assignment exists that satisfies every constraint simultaneously, and if so, to produce one. There is no better or worse among the assignments that work: an assignment either satisfies every constraint or it does not, full stop. That is not a simplification made for this course; it is the honest, complete statement of what the field studies, and it is worth sitting with, because it means a good deal of the vocabulary built up over the last seventeen topics (shadow prices, bounds, approximation ratios) simply does not apply here. There is nothing to be a ratio of.
The formal shape: a constraint satisfaction problem (CSP) is a set of variables, each with a domain of allowed values, and a set of constraints, each restricting which combinations of values its variables may jointly take. Solving it means finding an assignment of one value per variable that satisfies every constraint, or correctly reporting that none exists.
Two techniques do essentially all the work, and they compose. Backtracking search assigns variables one at a time, checking constraints as it goes, and undoes an assignment the moment it conflicts with one already made. Constraint propagation runs before or between those assignments and removes domain values that could never appear in any solution, tightening the problem before search has to touch it. Neither is quantum, neither is exotic, and the worked example above shows exactly what propagation removes and why.
General CSP (arbitrary finite domains, arbitrary constraints given as tables of allowed combinations) is NP-complete. Membership in NP is immediate: guess an assignment, and checking it against every constraint takes polynomial time. NP-hardness needs no new argument either, because two problems already on this page's own hardness ledger are themselves nothing but CSPs with a particular choice of variables, domains and constraints: graph k-colourability (also one of Karp's original 21 NP-complete problems, Karp, 1972: the same paper topic 04 cites for 0–1 integer programming, though it doesn't discuss colouring) and Boolean satisfiability (Cook, "The Complexity of Theorem-Proving Procedures," Proceedings of the 3rd ACM Symposium on Theory of Computing (1971), 151–158: the theorem that opened the NP-complete class in the first place).
That general statement hides something sharper. Restrict every variable's domain to just two values (Boolean CSP) and Schaefer proved the complexity of every possible constraint language collapses to exactly two outcomes, with nothing in between: T.J. Schaefer, "The Complexity of Satisfiability Problems," Proceedings of the 10th ACM Symposium on Theory of Computing (1978), 216–226. Whatever set of allowed relations a Boolean CSP is built from, the resulting problem is either solvable in polynomial time. Schaefer names six tractable cases in full, among them Horn clauses, 2-SAT-like binary clauses, and linear equations over GF(2), and shows they cover every polynomial case there is, or it is NP-complete. No Boolean constraint language sits anywhere in between.
The natural next question: does the same clean dichotomy hold once domains are allowed to be larger than two values, as in genuine graph colouring: stayed open for two decades as the Feder–Vardi conjecture (Feder & Vardi, SIAM Journal on Computing 28(1) (1998), 57–104) before being proved independently, and published back-to-back in the same proceedings, by Bulatov, "A Dichotomy Theorem for Nonuniform CSPs," Proceedings of FOCS (2017), 319–330, and Zhuk, "A Proof of CSP Dichotomy Conjecture," Proceedings of FOCS (2017), 331–342: every fixed-template CSP, over any finite domain whatsoever, is either in P or NP-complete.
Constraint propagation's standard form is arc consistency: an arc from variable Xi to Xj is consistent if every value remaining in Xi's domain has some compatible value in Xj's domain. A value with no such support can never be part of any solution, so deleting it is a proof of uselessness, not a heuristic guess: exactly as final as branch and bound's pruning in topic 05. AC-3 (Mackworth, "Consistency in Networks of Relations," Artificial Intelligence 8(1) (1977), 99–118) is the standard algorithm: maintain a queue of arcs, revise one, and if a domain shrinks, re-queue every arc pointing back into the variable that just changed, since a value that used to have support may have lost it. The worked example above runs exactly this and shows two domains shrink from three colours to two before any variable beyond WA is even assigned.
Register allocation, every time a compiler runs A compiler must assign each live temporary value in a program to one of a small number of physical registers, never giving the same register to two temporaries that are "live" at the same time. That is a CSP by construction: variables are temporaries, the domain is the set of physical registers, the constraint is "different register from anything you interfere with", and it is standardly solved as graph colouring, on an interference graph built from the program. Chaitin, Auslander, Chandra, Cocke, Hopkins & Markstein, "Register Allocation via Coloring," Computer Languages 6(1) (1981), 47–57, is the paper that made this the industry-standard approach; when the graph is not colourable with the registers available, the compiler "spills" a value to memory and recolours.
And the puzzle everyone has already solved by hand Sudoku is a CSP with 81 variables, domains {1,…,9}, and all-different constraints on every row, column and 3×3 box. Nothing more exotic than that. The reason a good human solver reaches for "this cell can only be a 7" long before guessing anything is that they are doing constraint propagation by eye, the same pruning AC-3 does mechanically above.
Check yourself
What does constraint propagation (arc consistency) do before the search has to guess anything?
Fixing WA to amber removes amber from the domains of NT and SA at once. Deleting an unsupported value is a proof of uselessness, as final as branch and bound's pruning.