Constraint satisfaction · Part 1
Translate a problem into legal assignments and remove impossible choices before doing more search.
Running example: three variables, three values each, and three simple rules.
Variables: one time-slot choice per course.
Domains: available time slots.
Constraint: courses sharing students cannot overlap.
A hard constraint must hold. A preference, such as fewer gaps, needs a score or an objective.
Example: dom(X) = {0, 1, 2}.
With 3 variables and 3 choices each: 3³ = 27.
When domains have different sizes, multiply their sizes instead.
n is the number of variables; i selects one variable Xᵢ.
dom(X₁)={0,1,2}; dom(X₂)={“a”,“b”}.
| X₁ | Possible X₂ values |
|---|---|
| 0 | “a” or “b” |
| 1 | “a” or “b” |
| 2 | “a” or “b” |
A total assignment chooses one value for every variable. If every domain has size d, the product becomes dⁿ.
Context A = {X₁ = 1}.
The question marks mean “unassigned”.
Assignment a = {X₁ = 1, X₂ = 2, X₃ = 0}.
An atomic assignment sets one variable. “Partial” allows any subset, including all variables. A total assignment is a solution only when every rule holds.
The letter a names the whole assignment. The lookup a[X₂] gives the value 2.
S is a set of selected variables. a[S] keeps their variable–value pairs.
Restriction drops pairs; it does not change values. For a partial assignment, choose S only from variables that already have a value.
| Rule | Scope: variables it uses | With X₁=1, X₂=2, X₃=? |
|---|---|---|
| X₁ < 2 | {X₁} · unary | True: 1 < 2 |
| X₃ < X₁ | {X₃, X₁} · binary | Pending: X₃ is missing |
| X₁ + X₂ = X₃ | {X₁, X₂, X₃} · ternary | Pending: X₃ is missing |
The scope of c is its variable set; its arity is |scope(c)|. Here the sum rule is only a ternary-scope illustration, not a course-CSP rule.
ε names evaluation; a supplies the scoped values; c is the constraint.
| Scoped assignment | Evaluation |
|---|---|
| {X₁=1, X₃=0} | ε(a,c)=1 |
| {X₁=0, X₃=1} | ε(a,c)=0 |
| {X₁=1} | Pending: X₃ is missing |
The input must supply all variables in scope(c). For a larger assignment a, evaluate ε(a[scope(c)], c). Pending is not a third value of ε.
A connective combines true/false statements. Here each X₁, X₂, X₃ has domain {0,1,2}.
This is the course 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 course rule.
𝓧 is the variable set; n counts its variables.
𝓒 is the constraint set; m counts its rules.
For each variable X, dom returns its allowed-value set.
Each c ∈ 𝓒 has a scope contained in 𝓧. All values chosen for X must belong to dom(X).
P names the problem. Solving it means finding one or all total assignments that use allowed values and satisfy every constraint.
𝓧: variables {X₁, X₂, X₃}.
dom: allowed values; each starts at {0,1,2}.
𝓒: three rules, all required:
(X₁ < 2) ∧ (X₂ > 0) ∧ (X₃ < X₁).
| X₁ | X₂ | X₃ |
|---|---|---|
| 1 | 1 | 0 |
| 1 | 2 | 0 |
Of the 27 complete assignments, only these two satisfy all three rules.
All solutions: (X₁=1) ∧ ((X₂=1) ∨ (X₂=2)) ∧ (X₃=0).
∧ means AND; ∨ means OR. The grouped OR leaves X₂ a choice.
A domain-valid total assignment a is a solution exactly when every scoped evaluation is 1.
| Course candidate | ε for X₁<2 | ε for X₂>0 | ε for X₃<X₁ |
|---|---|---|---|
| (1,1,0) | 1 | 1 | 1 |
| (2,1,0) | 0 | 1 | 1 |
∀ requires an AND (∧) across all constraints. a[scope(c)] supplies each rule’s values; one failed rule rejects the candidate.
Set X₁ = 1 and leave X₂ and X₃ unassigned. Predict the rule results; then set X₃ = 0 and X₂ = 2.
Three variables, three values each.
Fifteen variables, four values each.
Can we reject a bad choice before completing all the other choices? Backtracking does exactly that.
Here X₁ = 2 already violates X₁ < 2. Plain backtracking does not yet reject X₁ = 0: X₃ is still unassigned.
A is an updatable partial assignment called context; vars(A) is the set of variables already assigned. Here ≡ means “can be evaluated in”, not “is true”. c ≡ A if all variables in c are present in A.
A={X₁=1, X₃=0}. For c: X₁=X₃,
c ≡ A holds, but ε(A[scope(c)],c)=0.
𝓒ₑ contains the rules whose scopes are complete. The bar | means “such that”.
⊆ means “is a subset of”. If a variable in scope(c) is missing, c ≢ A: the rule is pending, so plain DFS cannot evaluate it yet.
DFS_solver(𝓧, 𝓒, A):
𝓒ₑ ← {c ∈ 𝓒 | c ≡ A}
if some c ∈ 𝓒ₑ has ε(A[scope(c)],c)=0:
return ∅
if 𝓧 = ∅: return {A}
choose X ∈ 𝓧; s ← ∅
for x ∈ dom(X):
s ← s ∪ DFS_solver(𝓧∖{X}, 𝓒∖𝓒ₑ,
A ∪ {X=x})
return s𝓧: variables still to assign.
𝓒: rules still to check; 𝓒ₑ: rules checkable now.
A: partial context; s: set of solutions.
∖: remove from a set.
∪: combine sets.
Start with all variables and rules, and A=∅. Returning ∅ means no solutions from this branch; {A} contains one solution.
Step from the empty context. Find the X₁ = 2 branch and its failed rule; then continue until both solutions are recorded. Focus a node to inspect its values.
MRV: minimum remaining values. Choose A; it has fewer alternatives.
Rule A ≠ B; dom(A)={1,2}, dom(B)={1,3}.
| Try | B values left |
|---|---|
| A = 1 | {3} |
| A = 2 | {1,3} |
Least-constraining value: try 2 first.
Degree can break an MRV tie: prefer a variable linked to more constraints on unassigned neighbors. Ordering changes effort, not the solutions.
DFS can be inefficient: it may try every value of B even when the chosen A has no possible partner.
Rule A < B; both domains are {1,2,3,4}.
| Choose A = 4, then try… | Rule check |
|---|---|
| B = 1 | 4 < 1 ✗ |
| B = 2 | 4 < 2 ✗ |
| B = 3 | 4 < 3 ✗ |
| B = 4 | 4 < 4 ✗ |
No allowed B is greater than 4.
Remove 4 before branching on A.
One domain check rules out every completion with A=4, while keeping all solutions.
Consistency algorithms remove values that cannot satisfy a constraint. Repeating these deductions as domains change is constraint propagation.
Rule A < B; both domains initially contain {1,2,3,4}. For a unary rule, filtering is often called domain consistency.
Remove A = 4 and B = 1. The remaining domains are dom(A)={1,2,3} and dom(B)={2,3,4}; no branching was needed.
GAC requires every remaining value to have support for each rule involving its variable.
A value has support if some allowed combination of the other values makes the checked rule true.
The GAC algorithm removes values without support and propagates the effects.
The same test works for different scope sizes:
| 1 variable | X < 2 |
| 2 variables | X < Y |
| 3 variables | X + Y = Z |
X, Y and Z name variables.
First identify the variable–rule connections. Then define support precisely and use a worklist to schedule the checks.
Circle: a variable X.
Rectangle: a constraint c.
Link: X belongs to the scope of c.
A rule using k variables has k links; k is its scope size.
To make domain filtering systematic, record which rules involve each variable. Each network link becomes a support check for GAC.
V contains the variables.
c₁ is A<B; c₂ is B<C. U contains the constraints.
V×U means all variable–constraint pairs. E₀ keeps only pairs connected by a scope.
For this chain, E₀={(A,c₁),(B,c₁),(B,c₂),(C,c₂)}. Bipartite means every edge crosses between the two kinds of vertex.
Rule A < B. A value of A stays only if some remaining B is larger.
Try A = 2. Remove B = 3 and B = 4: its support disappears. One working partner is enough; every partner need not work.
Given a constraint network G and a constraint c with scope(c)={X,Y₁,…,Yₖ}, the edge (X,c) is arc consistent if:
1 · ∀ x ∈ dom(X)
Take every allowed value of X, one at a time.
2 · ∃ y₁,…,yₖ in their domains
Find one combination of values for the other variables.
3 · ε(assignment, c) = 1
Those values must make rule c true. They are a support, or witness.
Check X=A; the only partner is Y₁=B (k=1). Both domains are {1,2,3,4}.
| Value of A | One supporting B |
|---|---|
| 1 | 2, since 1 < 2 |
| 2 | 3, since 2 < 3 |
| 3 | 4, since 3 < 4 |
| 4 | None → remove A=4 |
A witness may depend on x. Checking (A,c) and checking (B,c) are separate edge tests.
Use the course’s worklist name E. E₀ is the initial set of all network edges.
A pair (X,c) means “check variable X against rule c”.
Taking (A,c) removes a pending check, not the rule or network edge.
X is a variable; x is one value. The subscript X identifies the checked variable.
Replace the domain only if it has shrunk.
In the pseudocode, c′ names another rule and Z another variable. The next slide uses these names to schedule checks affected by a deletion.
dom is the current domain mapping; E contains pending checks. The variable set 𝓧 and constraint set 𝓒 stay fixed.
01 GAC(dom, E):
02 while E ≠ ∅:
03 take and remove (X,c) from E
04 NX ← {x ∈ dom(X) | x has support for c}
05 if NX ≠ dom(X):
06 dom(X) ← NX
07 if dom(X)=∅: return dom
08 E ← E ∪ {(Z,c′) | c′≠c ∧ Z≠X
09 ∧ {X,Z}⊆scope(c′)}
10 return domTake one check; compute the values with support.
No: take the next check. Yes: replace the domain.
Empty domain: return immediately. Otherwise add affected checks to E.
Return the pruned domains.
Start with E=E₀. ∅ means empty; ∪ adds checks. Lines 08–09 revisit another variable Z in another rule c′ that also uses X.
Compare dom(X) before with NX kept. When values are removed, highlighted checks show the update to E.
Chain A < B, B < C; each domain starts at {1,2,3,4}.
A = 3 initially has B = 4 as a witness. After B = 4 disappears, put (A, A < B) back on the worklist.
After dom(X) shrinks in a check against c, another variable can lose support in another rule.
c′≠c: consider another rule in 𝓒.
Z≠X: check another variable.
{X,Z}⊆scope(c′): both occur in that rule.
| X=B; c is B<C | The domain just revised. |
| Z=A; c′ is A<B | The check that may be outdated. |
Add a check, not a deleted value. ∧ means all three filters must hold; ∪ keeps existing pending checks and adds these pairs.
No solution in this branch.
After all GAC checks, the one remaining assignment is a solution.
A solution may or may not exist. More reasoning is needed.
A fixed point means no further pruning. If choices remain, domain splitting creates branches and runs GAC again in each one (Part 2).
X₁ = X₂ has the witness (1,1).
X₂ = X₃ has the witness (1,1).
X₁ ≠ X₃ has the witness (1,2).
But: the two equalities force X₁ = X₃, contradicting the inequality.
(X₁=X₂) ∧ (X₂=X₃) ∧ (X₁≠X₃): all three must hold for the same assignment. GAC finds separate witnesses, not one shared solution.
A total assignment, pruned domains and a solution are different things. Be able to show the difference with the course example.
AIML · Constraint Satisfaction Problems ↗
Course CSP, DFS, support, GAC, splitting and local search.
Definitions, worked deductions and the assumptions behind each result.
Further reading: Poole & Mackworth, Artificial Intelligence: Foundations of Computational Agents, Chapter 4.
Lecture 05 · Constraint satisfaction · Part 1