Constraint satisfaction is the task of assigning values to variables so that every required rule holds at the same time. A timetable, puzzle or configuration can be represented by variables, their permitted values and constraints connecting them. The central question is whether a complete compatible assignment exists; finding the best assignment adds an optimisation objective and changes what success means.
The gold standard is a model whose rules are explicit, a solving process that preserves valid possibilities, and an independent check of the final answer. A candidate surviving a few local checks is not necessarily a solution. A solver that stops without finding an answer has not necessarily proved impossibility. This guide explains those distinctions through original finite examples, complete calculations, repair exercises and a practical learning project.
Start with the Gold Standard collection or the How X Works hub for the wider map. Computational Complexity Theory explains how resource requirements scale. The Education guide supplies the test for understanding here: can you rebuild the reasoning when a domain, rule or objective changes?
Choose your constraint satisfaction route
Chapters 1–3: Build a faithful model
Chapters 4–6: Propagate and search
Chapters 7–9: Connect and diagnose
Chapters 10–12: Optimise and transfer
Chapter index
Build a faithful model · Chapters 1–3
1. Identify the variables, domains and constraints
Propagate and search · Chapters 4–6
4. Understand why local consistency is not global feasibility
Connect and diagnose · Chapters 7–9
7. Choose search orders without changing correctness
8. Translate the same principles into puzzles and Boolean logic
Optimise and transfer · Chapters 10–12
10. Add an objective and verify the claimed optimum
Check and practise · Chapters 13–14
CHAPTER 1 OF 14 · Build a faithful model
1. Identify the variables, domains and constraints
Begin with a complete assignment
Imagine three fictional demonstrations, A, B and C, to be placed into three numbered time slots. Let each variable record the slot assigned to its demonstration. Suppose A and B can use slots 1 or 2, while C can use slots 1, 2 or 3. Their domains are therefore D(A) = {1,2}, D(B) = {1,2} and D(C) = {1,2,3}.
There is one room, each demonstration lasts exactly one slot, and no two demonstrations may occupy the same slot. We represent that rule by requiring A, B and C to be all different. There are initially 2 × 2 × 3 = 12 complete assignments before this rule is applied. Most are invalid because two demonstrations collide. An assignment is simply a proposed set of values, not a declaration that the rules are satisfied.
For example, A = 1, B = 1, C = 3 uses values within every domain but violates the room rule. The assignment A = 1, B = 2, C = 3 satisfies both the domains and the all-different constraint. The assignment A = 3, B = 1, C = 2 fails even though its values are distinct, because A is not available in slot 3.
Keep the model smaller than the story, but not misleading
This model deliberately omits travel, setup, breaks and variable durations. That is acceptable for a teaching construction because the omissions are stated. For an actual timetable, omitting a required setup interval could produce a mathematically valid answer that is physically unusable. The purpose of modelling is to retain what determines feasibility, not to make a complicated situation look simple by deleting inconvenient requirements.
Before solving, write a sentence for each variable: what does its value mean, what units does it use, and where did its domain come from? Then write a sentence for each constraint identifying the real requirement it represents. This translation record makes later corrections possible. Without it, a solver’s precise output can conceal an imprecise interpretation of the original problem.
CHAPTER 2 OF 14 · Build a faithful model
2. Distinguish required rules from preferences
Feasibility is the first contract
A hard constraint must hold in every accepted solution. In the demonstration model, the room cannot host two events simultaneously. A preference, such as wanting C to finish early, describes how to compare feasible solutions. It should not be quietly promoted into a hard rule unless failure to meet it really makes the plan unacceptable.
Suppose someone says, “A should go before B.” Clarify its meaning inside the model. If it is mandatory, add A < B. If it is merely desirable, record a cost for violating that preference. Those formulations can lead to different answers, especially when later restrictions are added. A solver cannot decide which interpretation was intended simply because the sentence contains the word “should.”
With all-different and the original domains, the two feasible assignments are (A,B,C) = (1,2,3) and (2,1,3). Adding mandatory A < B leaves only (1,2,3). A preference for A before B would rank that assignment above the other while preserving the second as feasible. The distinction becomes useful if slot availability changes and only the less preferred arrangement remains possible.
Do not let a score erase a requirement
A weighted score can combine preferences, but weights express trade-offs chosen by the modeller. They are not measurements of universal fairness or importance. If missing a safety condition is forbidden, a very large penalty is not automatically equivalent to a hard constraint: a poorly bounded objective might still compensate for that violation elsewhere.
In ordinary planning, identify who can authorise changing a requirement and which preferences can be traded. Keep a feasible answer separate from an acceptable real-world decision. People may need to review accessibility, workload or operational details that the current model does not encode. Constraint satisfaction can make the explicit rules consistent; it cannot certify that every relevant human concern has been included.
CHAPTER 3 OF 14 · Build a faithful model
3. Use propagation to remove unsupported values
A deduction changes a domain for a reason
Constraint propagation repeatedly removes values that cannot participate in a permitted combination for a constraint under the current domains. For the binary rule X < Y, consider D(X) = {1,2,3} and D(Y) = {2,3}. Value 3 cannot remain in X because there is no available Y greater than 3. Remove it, leaving D(X) = {1,2}.
Now both values of Y still have support: Y = 2 can pair with X = 1, and Y = 3 can pair with X = 1 or 2. Both remaining X values also have support. The surviving complete pairs are (1,2), (1,3) and (2,3). The reduction from six raw pairs to three valid pairs follows from the inequality, not from a guess about which answer looks most attractive.
If another rule later forces Y = 2, propagation must revisit X < Y. The old support for X = 2 used Y = 3, which has disappeared. X must now become 1. Propagation is therefore sensitive to domain changes. A value that had support earlier may lose it after information arrives from elsewhere in the network.
Sound pruning preserves every solution
The key obligation is that a removed value cannot occur in any solution of the current problem. A heuristic that deletes values because they appear unlikely does not satisfy this obligation unless the task explicitly permits an incomplete search. Keep deductions and choices labelled separately in a learning trace: “removed because unsupported” is different from “temporarily assumed absent in this branch.”
Poole and Mackworth’s consistency algorithms provide the formal treatment. Our example makes the essential test visible: for a proposed value on one side of a binary constraint, search the other current domain for at least one compatible support. The support must satisfy that constraint with the proposed value; a merely nonempty neighbouring domain is not enough.
CHAPTER 4 OF 14 · Propagate and search
4. Understand why local consistency is not global feasibility
A triangle with only two colours
Let variables X, Y and Z each have domain {red, blue}. Require X ≠ Y, Y ≠ Z and Z ≠ X. Every value has support across each individual inequality: red can pair with blue, and blue can pair with red. Enforcing ordinary binary arc consistency therefore removes nothing from these initial domains.
Yet there is no complete solution. If X is red, Y must be blue and Z must be blue because both differ from X. Then Y ≠ Z fails. If X is blue, the same reasoning reverses the colours and produces the same contradiction. The two cases cover all possibilities for X, so the impossibility argument is complete.
The issue is that supports across different constraints need not fit together into one global assignment. X = red is supported by Y = blue on one edge and by Z = blue on another, but those two supporting choices conflict with each other. This is the precise gap hidden by the vague claim that “every individual rule still looks possible.”
Three possible outcomes after propagation
An empty domain establishes that the current constraint problem, or the current search branch, has no solution. A complete singleton assignment that satisfies all constraints is a solution. Between those extremes, nonempty domains with unresolved alternatives mean more work may be needed. They are not a promise that a full answer exists.
Some problem structures admit stronger conclusions from particular consistency procedures, but that requires a theorem with explicit conditions. Do not generalise such a result to every network. A reliable solver combines deduction with other reasoning or search when necessary. A reliable reader asks what level of consistency was enforced before accepting the claim that the problem has been solved.
CHAPTER 5 OF 14 · Propagate and search
5. Exploit a global all-different constraint
Two slots reserved by two variables
Return to A and B with domains {1,2}, and C with domain {1,2,3}. Because A and B must be different, together they occupy slots 1 and 2 in some order. Therefore C cannot use either of those slots and must equal 3. The conclusion does not require choosing which of A or B goes first.
This is a small Hall-set argument: a group of variables whose available values occupy exactly as many distinct values as variables reserves those values when all the variables must take different values. If a group of three variables had only two values available in total, there would be no distinct assignment for that group at all.
The Global Constraint Catalog’s all-different entry describes the constraint and filtering approaches. The important distinction is between its meaning and a particular algorithm enforcing it. A solver may offer different strengths of propagation, so the presence of an all-different expression alone does not justify assuming every possible consequence will be detected immediately.
Equivalent solutions can mean different propagation
Replacing all-different(A,B,C) with the three pairwise inequalities preserves the set of complete solutions. But ordinary arc consistency on those separate binary constraints does not remove 1 or 2 from C in the initial example. C = 1 has support B = 2 and support A = 2 when each constraint is examined separately, although those two choices cannot coexist because A and B must differ.
Thus two logically equivalent models can behave differently during propagation. This matters when debugging performance: a reformulation may preserve correctness while exposing useful structure to a stronger propagator. It also matters when teaching. The statement “these constraints mean the same thing” concerns complete solutions; it does not mean every intermediate deduction procedure will make the same progress.
CHAPTER 6 OF 14 · Propagate and search
6. Search with explicit assumptions and restoration
Branch only after recording the parent state
When propagation leaves alternatives, choose a variable and partition its remaining domain into cases. In the demonstration model after C becomes 3, one case is A = 1 and the other is A = 2. In the first, all-different forces B = 2. In the second it forces B = 1. These two branches recover the two feasible assignments without confusing a trial choice with a permanent rule.
If A < B is mandatory, the second branch fails because 2 < 1 is false. That failure must not alter the parent problem incorrectly. Before exploring another branch, restore every domain reduction caused only by the failed assumption. A common implementation error restores the chosen variable while leaving neighbouring domains narrowed, silently deleting valid solutions from later branches.
One safe teaching implementation copies the domain map before each branch. A more efficient implementation can use a reversible trail of changes. The data structure is secondary to the invariant: each branch begins with exactly the parent information plus its own assumption. Deductions that depend on a discarded assumption cannot be carried into an unrelated case as established facts.
Why the cases are complete
For a finite domain, splitting it into disjoint parts whose union is the original domain preserves every possibility across the branches. If every branch is solved completely, their solutions collectively cover the parent problem. Stopping after the first solution is legitimate when the requested output is one feasible assignment; it is insufficient for counting or proving uniqueness.
Domain splitting explains the relationship between case analysis and propagation. In practice, propagate after a decision, detect failure promptly, and then choose another unresolved variable if needed. The method is disciplined reversibility, not random guessing followed by forgetting the unsuccessful attempts.
CHAPTER 7 OF 14 · Connect and diagnose
7. Choose search orders without changing correctness
The smallest remaining domain is a useful clue
A common variable-ordering heuristic chooses an unresolved variable with few remaining values. The intuition is to expose restrictions or failure early. If one variable has two options and another has twenty, deciding the two-option variable may reveal consequences before a large search tree is explored. This is a heuristic about effort, not a theorem that it wins on every instance.
Tie-breaking can consider how many other unresolved variables are connected to the choice. Value ordering may prefer a value that leaves more room for neighbours, sometimes called a least-constraining-value approach. These choices affect which branch is visited first. Provided no permitted branch is wrongly discarded and the search is completed when required, they do not change the set of valid answers.
In the A, B, C example, assigning C before recognising its reserved-slot deduction wastes effort on C = 1 and C = 2. Recognising the global structure eliminates those branches entirely. This illustrates a useful order of attention: improve the model and propagation before attributing every performance problem to the branching heuristic.
Measure the thing you are comparing
Count decisions, failed branches, propagation operations and elapsed time separately when comparing methods. A stronger propagator may do more work per node while visiting many fewer nodes. A solver with fewer nodes is not automatically faster. Record the input family and implementation conditions alongside the measurements so that a small experiment does not become an unsupported universal performance claim.
The initial product of domain sizes is a count of raw complete assignments. For n variables with d values each it is d to the power n. That describes the naive space, not a lower bound on every algorithm. Constraints and structure can make many instances much easier. The broader limits belong to Computational Complexity Theory, not to an alarming candidate count on its own.
CHAPTER 8 OF 14 · Connect and diagnose
8. Translate the same principles into puzzles and Boolean logic
Crossings are compatibility relations
In a tiny invented word exercise, let an across slot have candidates CAT and CAR, and a down slot have candidates TOP and RAT. Require the final letter of the across word to equal the first letter of the down word. CAT supports TOP through T; CAR supports RAT through R. All four candidates initially survive, but only two complete pairs satisfy the crossing.
If another clue removes RAT, CAR loses its only support and must be removed. The remaining pair is CAT and TOP. This calculation is intentionally small enough to inspect without a dictionary or cultural assumptions. A real crossword adds many crossings and editorial requirements, so local letter compatibility is only part of the complete task.
Continue with Crossword Grids, Rotational Symmetry and Constraint Satisfaction for the distinction between geometric rules, word compatibility and puzzle quality. The method transfers because the values changed from time slots to words while the requirement for compatible assignments remained.
Sudoku and SAT expose different structures
Sudoku, Constraint Satisfaction and Backtracking develops a worked miniature grid. A cell is a variable, permitted symbols form its domain, and rows, columns and boxes impose overlapping constraints. A valid row cannot compensate for a violated box. All required relations must hold together.
Boolean satisfiability uses true-or-false variables and logical formulas. Many finite choices can be encoded through Boolean indicators, but an encoding must preserve the intended assignments. For example, one Boolean per slot needs rules saying that exactly one slot is chosen; saying only “at least one” permits multiple simultaneous choices. SAT Solvers, Boolean Variables, Clauses and Conflict-Driven Learning provides the specialist route. The representation changes the machinery, while modelling correctness remains essential.
CHAPTER 9 OF 14 · Connect and diagnose
9. Explain infeasibility before changing the rules
A transparent contradiction
Suppose A, B and C must all occupy different slots but now every domain is {1,2}. There are three events and only two available slots. No assignment can satisfy all-different. The conflict is structural and can be explained without listing all eight raw assignments: each distinct event would require a distinct slot, and only two slots exist.
There are several possible repairs, each changing a different part of the problem. Add a third usable slot. Allow one event to move to another day represented in the model. Permit simultaneous events by adding another room and modelling room assignments. Remove an event if the real task allows that. None of these is a deduction from the original constraints; each is a change requiring a reason.
Removing the all-different requirement without understanding its purpose could create an unusable plan. If all events need the same speaker, a second room alone does not solve the conflict. If only room capacity caused the restriction, a second room may help. Explain which resource generated the constraint before proposing to relax it.
Minimal does not always mean smallest
An irreducible or subset-minimal conflict is a collection of constraints that is inconsistent, but becomes consistent when any one member is removed. A minimum-cardinality conflict is one with the smallest number of constraints among the conflicts under consideration. These are different properties. A conflict can be irreducible without being the smallest possible explanation.
Also distinguish a conflict explanation from a repair recommendation. An explanation identifies incompatible requirements; a repair chooses which requirements may change and at what cost. The model alone may not know whether a deadline, availability restriction or preference reflects a negotiable choice. Keep the original model and record any authorised revision so that a new solution is not mistaken for proof that the original requirements were compatible.
CHAPTER 10 OF 14 · Optimise and transfer
10. Add an objective and verify the claimed optimum
A fully enumerable preference example
Give A, B and C the full domain {1,2,3} and require all three values to differ. There are six feasible assignments, the permutations of the three slots. Suppose the preferences are: A in slot 1, B in slot 1, and C in slot 3. Define the cost as the number of these three preferences that are not met. Every preference has unit weight for this constructed example.
For assignments (1,2,3) and (2,1,3), the cost is one: C receives slot 3 and one of A or B receives slot 1. Assignment (1,3,2) has cost two, as does (3,1,2). Assignments (2,3,1) and (3,2,1) have cost three. Exhausting the six permutations proves that the minimum cost is one and that two assignments attain it.
There is also a short lower-bound argument. A and B cannot both occupy slot 1, so at least one preference must fail. Since we have a feasible assignment with cost one, that lower bound is attained and the optimum is proved. This illustrates how a bound and a witness can establish optimality without treating a solver’s first answer as automatically best.
Multiple optima are not an error
The two optimal assignments differ in whose preferred early slot is granted. The objective as written is indifferent between them. If a real decision needs a tie-break, specify it explicitly rather than pretending the mathematics selected a uniquely fair answer. A rotation policy across repeated days, for example, introduces information beyond this one-day model.
Changing the weights changes the question. If missing A’s preferred slot costs five units while the other misses cost one, (1,2,3) becomes preferable to (2,1,3). Those units are policy choices, not physical measurements unless a defensible measurement process defines them. Show the weights and test whether modest changes alter the selected answer before relying on a score in a consequential planning decision.
CHAPTER 11 OF 14 · Optimise and transfer
11. Read solver results and check the returned assignment
A status message is part of the answer
The current OR-Tools CP-SAT documentation, checked on 5 November 2026, distinguishes OPTIMAL, FEASIBLE, INFEASIBLE, MODEL_INVALID and UNKNOWN. In optimisation, a feasible incumbent does not by itself establish optimality. An unknown result is not an infeasibility proof, and an invalid model is not evidence that the real planning task has no solution.
Software-specific details matter. CP-SAT works with integer modelling; using a different solver may permit different variable types and constraints. If decimal quantities are scaled to integers, preserve their intended precision and check numerical ranges. Rounding a duration downward can accidentally permit overlap. This guide’s small integer slots avoid that issue, but a production model needs an explicit units and precision policy.
Do not read values as a valid solution unless the solver status supports doing so. Keep the model version, input data and relevant settings with the returned result. A schedule calculated for yesterday’s availability is not verified for today merely because its file name still says “final.”
Build a checker that can disagree with the solver
For the demonstration model, the checker reads every event, confirms exactly one slot is assigned, checks membership in each event’s permitted domain, and then tests all-different and any ordering requirements. If an objective is present, it recomputes the cost from the assignment. An independent checker should not simply echo a “success” flag from the solving procedure.
Test the checker with deliberately invalid candidates: a missing event, a slot outside the domain, two events in the same slot, and a reversed mandatory order. Also provide a feasible but suboptimal answer when testing optimisation reporting. These tests target different failure modes. Passing one does not establish that the other conditions are being checked, and checking feasibility alone does not validate a claim of optimality.
Change availability and predict the consequence
Start from D(A) = D(B) = {1,2}, D(C) = {1,2,3}, all-different and mandatory A < B. The unique answer is (1,2,3). Now remove slot 1 from A’s domain. A must be 2, leaving B = 1 under all-different, which violates A < B. The changed model is infeasible. This is not a failure of propagation; the new availability and ordering requirements conflict.
If A < B was only a preference, the changed model would remain feasible with (2,1,3), at the cost of missing that preference. This single modification checks whether you really understand the hard-versus-soft distinction. State the expected feasibility result before running a solver, then compare its output with your hand argument.
Change the meaning of a slot
Suppose demonstrations may last two slots instead of one. All-different start times no longer prevents overlap. An event starting at 1 and lasting two units overlaps another starting at 2 and lasting one unit, even though their start values differ. The model needs duration-aware non-overlap constraints, not just unique start times.
Using half-open time intervals, an event from 1 to 3 occupies [1,3), while an event from 3 to 4 occupies [3,4). They meet at a boundary without overlapping under that convention. Setup time may require an additional gap. Write the boundary convention explicitly; otherwise one system’s “ends at three” may be another system’s “still occupies three.”
Change the requested output
If the user asks for all schedules rather than one, the solver must continue beyond the first answer and avoid duplicates under the agreed notion of identity. If two rooms are interchangeable, swapping their labels may or may not count as a distinct schedule. Decide this before reporting a solution count. Symmetry handling can simplify search, but it must preserve the output interpretation the user actually requested.
CHAPTER 13 OF 14 · Check and practise
13. Diagnose errors and answer common questions
Why are all domains nonempty but there is no answer?
Nonempty domains only show that each variable retains some candidate. Even arc-consistent binary constraints can fail globally, as the two-colour triangle demonstrates. Check whether propagation reached a fixed point, which constraints it considered, and whether complete search or a stronger argument is needed. Do not repair this by arbitrarily selecting a surviving value and calling it proven.
Why does changing the order of search change the first result?
Several feasible assignments may exist. A different branch order can discover a different one first while remaining perfectly correct. If a unique output is required, add a legitimate tie-break or request a canonical selection rule. Do not infer uniqueness from repeated runs that happen to use the same deterministic search order.
How can I establish uniqueness?
For a finite model, one approach is to find a solution, exclude exactly that complete assignment, and solve the remaining problem completely. A second solution disproves uniqueness. A proved infeasibility result for the remaining problem establishes uniqueness relative to the model and the way complete assignments are counted. A timeout after exclusion leaves the question unresolved.
Why does a stronger propagator sometimes run more slowly?
It may spend more effort deriving deductions than the reduced search saves. The trade-off depends on structure, domain size and implementation. Compare total work on representative instances, including failures, rather than judging only the size of one search tree. Correctness and speed are separate properties that need separate evidence.
Does a valid model guarantee a good real-world plan?
No. A valid assignment satisfies the encoded rules. Missing constraints, mistaken input data and inappropriate preferences can still produce a poor plan. Ask a person familiar with the activity to review the model’s meaning, not merely its syntax. Keep a route for correcting the model when an apparently legal answer exposes an omitted requirement.
What should a useful failure report contain?
State whether the failure is a contradiction, an invalid model, a resource limit or an implementation error. Identify the relevant rule names and input version. Where possible, give a small reproducible example and a logically justified conflict explanation. Avoid a generic “no solution” message that forces the reader to guess whether the requirements are impossible or the computation simply stopped.
CHAPTER 14 OF 14 · Check and practise
14. Build a four-week independent practice project
Week one: model and enumerate
Write the demonstration problem in plain language, then as variables, domains and named constraints. Enumerate the twelve raw assignments of the original model and mark each failure with the rule it violates. Confirm that exactly two assignments survive all-different and exactly one survives the additional ordering requirement. This provides a small reference result against which later automation can be tested.
Keep three separate records: the real-world statement, the mathematical model and the expected answers. They should agree, but they are not interchangeable. If a requirement changes, revise the first two and recompute the third. Preserving the earlier version makes it possible to explain why an answer that was correct yesterday may be wrong under today’s assumptions.
Week two: trace propagation by hand
Work the inequality example and the all-different example. For each deletion, name the constraint and list the missing support or reserved values that justify it. Then work the two-colour triangle and explain why ordinary binary arc consistency stops without finding the contradiction. This contrast teaches the boundary of a method rather than only its successful cases.
Create one incorrect deletion deliberately and find a valid complete solution that it destroys. That exercise tests soundness concretely. Next create a valid value that survives propagation but belongs to no global solution in a suitable example. That tests the opposite misconception: survival is not the same as proof of extendibility to a full answer.
Week three: implement reversible search
Use a simple representation whose state can be copied or restored reliably. Compare the solver’s complete solution set with exhaustive enumeration on several tiny instances. Include an empty domain, a single forced assignment, multiple solutions and the impossible triangle. An automated test should check returned assignments independently, because a search procedure and a checker can otherwise repeat the same mistaken assumption.
Record the branch decisions and domain changes for at least one failed branch. On return to the parent, inspect the restored state before continuing. This is where an attractive-looking solver often hides a serious bug: it finds one answer but misses others because information leaked from a discarded case. Solution-set comparison on tiny models catches that error more directly than timing a large example.
Week four: optimise, perturb and explain
Reproduce the six-permutation preference example and its minimum cost of one. Then change a weight, an availability domain and the meaning of a slot in separate experiments. Predict which part of the reasoning must change in each case. Keep feasibility, optimality and model adequacy as separate questions in the final report.
Finish with a concise explanation another learner can check: what each variable represents, where its domain came from, which constraints are mandatory, how deductions preserve solutions, how branching covers alternatives, and how the returned answer was verified. Follow the linked Sudoku, crossword and SAT guides for specialised applications. The durable skill is to turn a collection of interacting rules into an explicit model, then remain honest about what the model and its solver have actually established.