Constraint satisfaction · Part 2
Recall the choices, rules and filtering from Part 1. Then finish systematic search with domain splitting and explore local search.
CSP means constraint satisfaction problem. We want to choose values that obey every rule.
Three named choices. Each variable will receive one number.
Each variable starts with these options. dom(X) means “the domain of X”.
∧ means AND: a solution must satisfy all three rules.
Capital X names a variable; lowercase x can name one of its values. Braces {…} enclose a set of available options.
A connective combines true/false statements. Here each X₁, X₂, X₃ has domain {0,1,2}.
This is the running CSP: satisfy all three rules together.
(1,0,0): false overall.
The middle rule fails; the others hold.
An illustrative OR constraint.
Either part may hold; both may hold too.
(1,0,0): true overall.
The left part holds, so this OR holds.
A CSP requires an AND across its constraints. An individual constraint may contain OR. The OR example is a separate illustration, not an extra rule in the running CSP.
An assignment chooses values. A solution is a total assignment that satisfies every constraint.
A={X₁=1} is a partial context. X₂ and X₃ are unassigned.
X₁<2 is true; the other rules are pending.
Every variable has a value, and every rule holds:
(1<2) ∧ (2>0) ∧ (0<1): true.
All values are allowed, but X₃<X₁ becomes 0<0, which is false.
We write a total assignment as a tuple, such as (1,2,0), in the fixed order X₁, X₂, X₃. “?” means unassigned; it is not a domain value.
Choose all three values, then check every rule.
Depth-first search (DFS) builds a partial assignment. Test a rule once all variables it uses have values.
Filter the domains: remove values that cannot satisfy a rule with any allowed partners.
Backtracking rejects choices already made. Propagation reasons about choices still available, before completing an assignment.
GAC filters domains: remove a value when it has no satisfying partners for a rule. Example: X₃ < X₁, both domains {0,1,2}.
This satisfying pair is a support, also called a witness. Keep X₁=1 for this rule.
No possible X₃ makes the rule true. Remove X₁=0 from its domain.
After a deletion, affected checks return to the worklist E. Repeat until E is empty or a domain is empty.
| Variable | Initial domain | After GAC |
|---|---|---|
| X₁ | {0,1,2} | {1} |
| X₂ | {0,1,2} | {1,2} |
| X₃ | {0,1,2} | {0} |
X₁=1 ∧ X₃=0 are fixed. X₂=1 ∨ X₂=2 is still a choice.
Try the X₂ alternatives in separate branches. Propagate again inside each branch.
In general: an empty domain means failure; all singleton domains after GAC give a solution; remaining choices leave the result unresolved. A singleton is a set with one value.
Split a remaining domain. Propagate each branch and explore all alternatives.
Change one value at a time. Reduce conflicts, and sometimes move sideways or uphill.
Systematic search can prove impossibility when exhaustive. A bounded local-search run may simply finish without finding a solution.
After GAC: (X₁=1) ∧ ((X₂=1) ∨ (X₂=2)) ∧ (X₃=0). Split the OR into two branches; keep every original constraint in both.
The parts must be nonempty, disjoint and cover the original domain. Copy the domains, run GAC in each branch, and explore both.
dom₀ is the domain mapping after GAC; D₁ and D₂ are the two parts.
| Variable | Branch j, with j=1 or 2 |
|---|---|
| The selected X | domⱼ(X)=Dⱼ |
| Any other Y≠X | domⱼ(Y)=dom₀(Y) |
Example: {1,2,3,4} splits into {1,2} and {3,4}.
∪ = union; ∩ = intersection; ∅ = empty set; ∧ = AND. All conditions must hold: the parts cover the domain, do not overlap, and are nonempty.
Input: variables 𝓧 with their domains, constraints 𝓒, and pending checks E. Result: a set of solutions.
procedure Con_Solve(𝓧, 𝓒, E)// Inputs: variables, constraints and checks. dom₀ = GAC(𝓧, 𝓒, E)// Filter the current domains using GAC. if ∃X∈𝓧, dom₀(X)=∅ then// Does any variable have no value left? return ∅// Reject this branch: it has no solution. else if ∀X∈𝓧, |dom₀(X)|=1 then// Does every variable have exactly one value? return {{X=x | X∈𝓧, x∈dom₀(X)}}// Return a set containing that one assignment. else// Some domains still contain choices. select X such that |dom₀(X)|>1// Choose one variable that needs a decision. partition dom₀(X) into D₁ and D₂// Two nonempty, disjoint parts cover its values. (∀Y≠X, dom₁(Y)=dom₀(Y)) ∧ dom₁(X)=D₁// Branch 1: copy other domains; restrict X to D₁. (∀Y≠X, dom₂(Y)=dom₀(Y)) ∧ dom₂(X)=D₂// Branch 2: copy other domains; restrict X to D₂. E′ = {(Z,c′) | Z≠X, {X,Z}⊆scope(c′)}// Recheck other variables in rules involving X. return Con_Solve(𝓧[dom₁],𝓒,E′) ∪ Con_Solve(𝓧[dom₂],𝓒,E′)// Solve both branches; combine their solutions. end if// All three cases have now been handled.end procedure// End the procedure.𝓧: variables with current domains.
𝓒: constraints · X,Y,Z: variables.
x: a value · D₁,D₂: the two parts.
dom₀: after GAC · dom₁,dom₂: branch domains.
domⱼ(X): X’s values in branch j (1 or 2).
𝓧[domⱼ]: same variables, using domains domⱼ.
E: pending (variable,rule) checks.
E′: affected checks · c′: a constraint.
scope(c′): variables used by that constraint.
∃: some · ∀: every · ∈: belongs to · ⊆: subset · ∧: AND · ∪: union · ∅: empty set · |…|: number of values.
{… | …}: items meeting all the conditions · {{…}}: a set containing one assignment. “=” stores a result on lines 2, 10–12; tests compare values.
Predict the running example’s two X₂ branches, then step. Select the contradiction: GAC leaves nonempty domains, but splitting eventually rejects every branch.
The assignment space is the set of possible combinations of variable values.
Explore alternatives systematically, pruning impossible branches.
A huge space can be too costly to finish; an infinite space may never be exhausted.
Keep one complete candidate and change it a little at a time.
Visit selected candidates, without trying to cover every alternative.
The trade-off: local search can find a solution with less work, but may miss one even when it exists.
Our examples have finite domains. Infinite domains can create infinitely many assignments.
a is a complete candidate. Its conflict score h(a) counts the rules it violates.
Rules: (X₁ < 2) ∧ (X₂ > 0) ∧ (X₃ < X₁).
Assign missing values; reject a branch when an evaluable rule fails.
Only X₃ < X₁ fails: h(a)=1.
Change X₁ to 1: (1,1,0) has score 0.
Goal: h(a)=0. No rule is broken, so a is a solution. A positive score means the candidate still needs repair.
Keep one total candidate. Each method changes how we choose its next move.
| Method | The question it answers |
|---|---|
| Generic search | What does the shared loop do? |
| Random sampling | What if we just try fresh candidates? |
| Random walk | What if we change one value at random? |
| Iterative best improvement (IBI) | What if the conflict score guides us? |
| Simulated annealing | When should we accept a worse move? |
First define candidates, neighbors and scores. Then change one policy at a time; compare them in the final lab.
Keep a complete candidate; choose one allowed change. This defines the local-search neighborhood.
h(a) = 1: only X₃ < X₁ fails.
| Change | Candidate | Conflicts h(a) |
|---|---|---|
| X₁ to 1 | (1,1,0) | 0 |
| X₂ to 0 | (0,0,0) | 2 |
A policy decides which neighbor to propose and whether to accept it. Random walk, best improvement and annealing use different policies on the same neighborhood.
Variables: vertices A, B, C, D.
Domain: {red, green, blue}.
Rule: joined vertices must differ.
Assignment shown: a = {A=red, B=green, C=red, D=blue}.
The ∧ symbols mean AND: all five rules must hold. Here only A≠C fails, so h(a)=1.
h is an evaluation function: it scores a complete candidate a by counting the constraints it violates.
| Rule | Broken? | Add |
|---|---|---|
| X₁ < 2 | No: 0 < 2 | 0 |
| X₂ > 0 | No: 1 > 0 | 0 |
| X₃ < X₁ | Yes: 0 < 0 is false | 1 |
One broken rule means one conflict.
Lower is better. A score of zero means every constraint holds.
Use h(a) for this conflict score throughout local search.
Score a candidate by adding 1 for each violated rule and 0 for each satisfied rule.
Input: variables 𝓧 and constraints 𝓒. Goal: a complete assignment that satisfies every constraint.
procedure Local_search(𝓧, 𝓒)// Inputs: variables 𝓧 and constraints 𝓒.repeat// Begin an attempt; restart here if needed. for X ∈ 𝓧 do// Visit every variable X. a[X] = rand(dom(X))// Give X a random allowed value. end for// a now assigns a value to every variable. while ¬stop() ∧ ∃c∈𝓒, ε(a[scope(c)],c)=0 do// Continue if not stopped AND a rule fails. Y = select_var(𝓧)// Choose the variable Y to update. y = select_val(dom(Y))// Choose its allowed replacement value y. a[Y] = y// Change only Y’s value in candidate a. end while// Return to the test on line 6. if ∀c∈𝓒, ε(a[scope(c)],c)=1 then// Check whether EVERY constraint holds. return a// Success: return this complete solution. end if// If the test failed, continue to line 14.until terminate()// Finish overall, or begin another attempt.return ∅// This run found no solution; not a proof of none.end procedure// End the procedure.𝓧: variables · 𝓒: constraints.
X,Y: variables · y: a value.
a: complete candidate; a[Y]: Y’s value.
dom(Y): allowed values of Y.
scope(c): variables used by rule c.
ε(a[scope(c)],c): 1 if c holds, 0 if it fails.
∈: belongs to · ¬: NOT · ∧: AND.
∃: at least one · ∀: every.
∅: no solution returned by this run.
stop(): end this attempt · terminate(): end the whole search · rand: random choice. “=” stores a value on lines 4, 7–9; the rule tests compare with 0 or 1.
All four vertices start red. Press Next: which vertex changes, and how many conflicts remain? Every state is a complete candidate.
Draw a complete candidate, test it, then discard it if a rule fails.
Order: X₁,X₂,X₃. First draw fails X₃<X₁; second draw satisfies all three rules.
Skip the inner repair loop. Each attempt only samples and tests.
No information from the failed candidate guides the next draw. A finite number of draws can miss every solution.
Press Next to draw a fresh coloring. All four values are sampled again; the score may rise or fall. Reset and try another seed.
Keep the current candidate. Pick a variable and a new allowed value at random.
Conflicts: 1 → 2.
X₂>0 now fails too. Random walk still keeps the move.
Sampling: replace the whole candidate.
Walk: retain the other values and change just one.
Random walk ignores whether the score improves. Next, IBI uses that score to choose a move.
Press Next and compare the colors. Exactly one vertex changes; the move is kept even if its conflict score does not improve.
Count violated rules: (X₁ < 2) ∧ (X₂ > 0) ∧ (X₃ < X₁). Lower is better; zero means a solution.
a is the total assignment, in order X₁,X₂,X₃. h(a) counts violated constraints.
| Some one-value changes | Conflicts |
|---|---|
| X₁→1: (1,1,0) | 0 ✓ |
| X₁→2: (2,1,0) | 1 |
| X₂→0: (0,0,0) | 2 |
Check all allowed changes; choose a neighbor with the lowest score.
Strict IBI: repeat only while the best neighbor has a lower score. No lower neighbor? Stop this attempt; a solution may still exist elsewhere.
Choose a good allowed move, but temporarily avoid variables changed very recently.
X₁ and X₃ are temporarily tabu (blocked). X₂ is available.
X₁ becomes available again. The memory delays an immediate reversal.
The memory delays an immediate reversal. Here t=2 means “avoid the last two changed variables”. Tabu may take an equal or worse move to keep searching.
Strict IBI accepts only lower scores. On this graph it stops at one conflict, even though a two-move route reaches zero.
Try strict improvement → sideways B to blue → strict improvement again. A sideways move keeps h(a)=1 but opens a move to h(a)=0.
Replace every value, then try improvement again from the new starting point.
Occasionally replace a greedy move with a random local change, even if the score does not fall.
Next: simulated annealing controls the acceptance of worse moves using temperature.
Press Next: strict improvement stops at one conflict. Compare Tabu, or choose All red to see a successful improving run.
In both panels, the current candidate has 1 conflict. We propose a candidate with 2 conflicts.
The worse proposal has a higher chance of being accepted.
Replace the current candidate with the proposed one.
The same proposal has a higher chance of being rejected.
Keep the current candidate; try another proposal.
Temperature changes the chance of accepting the proposal. It does not change its conflict count. Both decisions remain possible.
Accept better or equal candidates. Sometimes accept a worse one to escape a trap. Use h(a) to compare their conflict scores.
Δh ≤ 0: accept a better or equal move.
Draw u uniformly from [0,1). Accept if u < p.
Here Δh=2. A positive T makes this worse move possible; cooling makes it less likely. The prime ′ marks the proposed assignment.
Set Δh=2 and u=0.5. Compare T=4 with T=0.5. Then try Δh=0: an equal-score move is always accepted. p is the acceptance probability; u is the test draw.
An annealing schedule is simply the rule used to lower temperature during a run.
Worse moves are easier to accept, helping search leave a trap.
The same worse move is less likely to be accepted.
The lab lowers temperature a little after each step. Cooling too fast can leave search stuck; a finite run can still miss a solution.
Annealing starts selected. Press Next to see accepted and rejected moves. Then reset and compare policies on the same start. A seed repeats the same random choices.
| Method | Works on | What a completed run establishes |
|---|---|---|
| Generate-and-test | Total assignments | All solutions if every candidate is tested. |
| Backtracking | Partial assignments | All solutions if every branch is explored. |
| GAC alone | Domains and supports | Pruned domains; sometimes inconclusive. |
| GAC + splitting | Restricted-domain branches | All solutions, or none, if exhaustive. |
| Local search | One changing total assignment | A solution at h(a)=0; otherwise inconclusive. |
Exhaustive claims assume finite domains and sound checks. Finding one solution can justify success before exhaustive completion.
Explain what the result proves. A correct number without the right conclusion can still be misleading.
X₁ < 2 is true.
X₂ > 0 and X₃ < X₁ are pending.
dom(X₁)={1}
dom(X₂)={1,2}
dom(X₃)={0}
X₂ has two choices; each yields a solution.
Each rule has support separately. But the equalities force X₁=X₃, violating X₁≠X₃.
Δh=2:
T=4 → p≈0.607
T=0.5 → p≈0.018
Write dom(X₂)={1,2} for a set of choices. Write X₂=1 when a specific value has actually been selected.
Exhaustive finite search: solutions or a proof of none.
h(a)=0: a solution. Budget spent: unresolved.
The key distinction: “no solution exists” requires a proof; “this run found no solution” is only a report of a run.
Definitions, worked deductions and the assumptions behind each result.
Further reading: Poole & Mackworth, Artificial Intelligence: Foundations of Computational Agents, Chapter 4.
Use a concrete example, then state whether the result is a solution, a proof of impossibility, or still unresolved.
Lecture 06 · Constraint satisfaction · Part 2