Constraint Satisfaction for Everyday Problem Solving
Many puzzles and planning problems share one structure: assign values while respecting a set of rules.
What constraint satisfaction means
Model each decision as a variable, list its allowed values, and write rules that remove invalid combinations. Propagate hard constraints before exploring alternatives, choose the variable with the fewest legal values when search is needed, and score preferences only after feasibility is established.
A constraint limits the answers that may work. Solving means narrowing each choice until the remaining values fit all rules together.
Key relationships
- A variable holds one value from a set of choices.
- A constraint limits which values can appear together.
- Constraint propagation shrinks the choices that remain after each deduction.
Variables, domains, and constraints
A variable is a decision to make. Its domain is the set of allowed values. A constraint removes combinations. In a staff rota, each shift is a variable, available workers form its domain, and availability, skill, rest, and fairness rules are constraints.
Writing these parts separately reveals whether a problem is impossible, merely difficult, or underspecified.
Reduce domains before searching
Constraint propagation removes values that cannot participate in a valid solution. If one specialist must cover Friday, remove that person from overlapping work. If a meeting needs three attendees, intersect their availability before considering room options.
The smallest-domain-first rule is a practical default. Resolve the variable with the fewest legal values because it is most likely to force useful consequences.
Use soft constraints honestly
Real problems often include preferences rather than absolute rules. Label them. A hard constraint cannot be violated; a soft constraint carries a cost. Mixing the two creates false impossibility. A schedule can be legal but inconvenient, and the optimization step should make that tradeoff visible.
Diagnose an impossible problem
When every domain becomes empty, identify the smallest set of constraints that cannot coexist. A rota may fail because one licensed worker is unavailable while two simultaneous shifts require that licence. The useful result is not merely no solution. It is the exact collision that must be renegotiated.
Relax one rule at a time and record what changes. This distinguishes a genuine requirement from a preference that was described as fixed. It also prevents a stakeholder from solving infeasibility by quietly violating an important safety or legal condition.
Compare feasible solutions
A constraint model answers what is allowed. Optimization answers which allowed solution is preferred. Define costs after hard rules: travel time, overtime, imbalance, delay, or risk. Keep each cost visible so a combined score does not hide who bears the tradeoff.
Generate at least two feasible candidates when possible. Comparing them often reveals a missing objective, such as continuity for customers or a fair distribution of unpopular shifts.
Maintain the model as facts change
Real schedules and assignments are not solved once. Store the assumptions, current domains, and reason for each hard rule. When availability changes, update the affected variables and propagate again instead of rebuilding from memory.
A useful model also identifies the fragile assignments with only one legal value. Those are the places where a backup, earlier confirmation, or contingency plan has the greatest value.
Build a small manual model
For a four-person rota, create one row per shift and list every available qualified person. Cross out conflicts and rest violations, then count the remaining candidates. Assign the row with one candidate first and remove that person from overlapping rows. This miniature model exposes the same propagation used by larger scheduling systems without requiring software.
Keep a reason beside each removal. If the model fails, reasons reveal whether the collision comes from coverage, availability, qualification, or an unnecessary preference. That diagnosis tells you which rule can be discussed and which resource would actually increase feasibility.
Diagnose a schedule before trying to optimize it
Consider a two-shift rota. The morning shift needs a licensed worker. The evening shift needs any available worker. Ana is licensed but available only in the morning. Bo is unlicensed and available for either shift. Cy is licensed but unavailable. This is a feasibility problem before it is a fairness problem.
| Variable | Starting domain | Constraint result |
|---|---|---|
| Morning shift | Ana, Bo, Cy | Cy is unavailable and Bo lacks the licence, leaving Ana |
| Evening shift | Ana, Bo, Cy | Ana is unavailable and Cy is unavailable, leaving Bo |
| Fairness preference | Balance unpopular shifts | Evaluate only after both hard assignments are feasible |
The model has two singleton domains, so no search is needed. If Ana becomes unavailable, the morning domain becomes empty. The useful diagnosis is specific: licensed morning coverage is missing. A vague result such as the schedule does not work hides the resource that would restore feasibility.
What to record when a domain becomes empty
- The variable with no legal value.
- The rule responsible for each removed value.
- Which rule is fixed by safety, law, or policy.
- Which preference could be relaxed and who can authorize that change.
Use constraints with precise logic
Directional rules need special care, so review conditional logic and contrapositives before encoding if, only if, or unless statements.
For a worked application, generate a new case with the logic puzzle generator and record each domain reduction.
Model timing, returns, and feasible moves in the 17-minute bridge and torch problem.
For a state-transition example, solve the 4-litre and 9-litre water jug puzzle.