Constraint Satisfaction Problems
Supervised by
Prof. Abbas AL- Bakri
Prepared By:
Hussein Saeed Areej Rebat
Duaa Mahmud
1
Outline
• Constraint Satisfaction Problems (CSP)
• Backtracking search for CSPs
• Local search for CSPs
2
Constraint satisfaction problems (CSPs)
• Standard search problem:
– state is a "black box“ – any data structure that supports successor function,
heuristic function, and goal test
• CSP:
– state is defined by variables Xi with some values from domain Di
– A set of constraints Ci specifies allowable combinations of values for subsets
of variables
– A consistent state violates none of the constraints C
– A complete assignment has values assigned to all variables.
– A Solution is a complete, consistent assignment.
• Simple example of a formal representation language
3
Example: Map-Coloring
• Variables WA, NT, Q, NSW, V, SA, T
• Domains Di = {red,green,blue}
• Constraints: adjacent regions must have different colors
• e.g., WA ≠ NT, or (WA,NT) in {(red,green),(red,blue),(green,red),
(green,blue),(blue,red),(blue,green)}
4
Example: Map-Coloring
• Solutions are complete and consistent
assignments, e.g., WA = red, NT = green,Q =
red,NSW = green,V = red,SA = blue,T = green
Based on Hwee Tou Ng, [Link]/slides-ppt, which are based on
CSC 8520 Spring 2010. Paula Matuszek Russell, [Link]/slides-pdf.
5
Constraint graph
• Binary CSP: each constraint relates two variables
• Constraint graph: nodes are variables, arcs are constraints
6
Varieties of CSPs
• Discrete variables
– finite domains:
• n variables, domain size d O(dn) complete assignments
• e.g., Boolean CSPs, incl.~Boolean satisfiability (NP-complete)
– infinite domains:
• integers, strings, etc.
• e.g., job scheduling, variables are start/end days for each job
• need a constraint language, e.g., StartJob1 + 5 ≤ StartJob3
• Continuous variables
– e.g., start/end times for Hubble Space Telescope observations
7
Varieties of constraints
• Unary constraints involve a single variable,
– e.g., SA ≠ green
• Binary constraints involve pairs of variables,
– e.g., SA ≠ WA
• Higher-order constraints involve 3 or more variables,
– e.g., cryptarithmetic column constraints
• Global constraints: arbitrary # of constraints, not necessarily all
the variables in a problem.
8
Example: Cryptarithmetic
• Variables: F T U W R O X1 X2 X3
• Domains: {0,1,2,3,4,5,6,7,8,9}
• Constraints: Alldiff (F,T,U,W,R,O)
– O + O = R + 10 · X1
– X1 + W + W = U + 10 · X2
– X2 + T + T = O + 10 · X3
– X3 = F, T ≠ 0, F ≠ 0
9
Real-world CSPs
• Common problems:
– Assignment problems
• e.g., who teaches what class
– Timetabling problems
• e.g., which class is offered when and where?
– Transportation scheduling
– Factory scheduling
• Notice that many real-world problems involve
real-valued variables
• May also include preference constraints:
constraint optimization
10
Standard search formulation (incremental)
Let's start with the straightforward approach, then fix it:
States are defined by the values assigned so far
• Initial state: the empty assignment { }
• Successor function: assign a value to an unassigned variable
that does not conflict with current assignment
fail if no legal assignments
• Goal test: the current assignment is complete
1. This is the same for all CSPs
2. Every solution appears at depth n with n variables
use depth-first search
3. Path is irrelevant, so can also use complete-state formulation
4. b = (n - l )d at depth l, hence n! · dn leaves
11
Backtracking search
• Variable assignments are commutative}, i.e.,
[ WA = red then NT = green ] same as [ NT = green then
WA = red ]
• Only need to consider assignments to a single variable
at each node
b = d and there are dn leaves
• Depth-first search for CSPs with single-variable
assignments is called backtracking search
• Backtracking search is the basic uninformed
algorithm for CSPs
Based on Hwee Tou Ng, [Link]/slides-ppt, which are based on
CSC 8520 Spring 2010. Paula Matuszek Russell, [Link]/slides-pdf.
12
Backtracking example
13
Backtracking example
14a
Backtracking example
15
Backtracking example
CSC 8520 Spring 2010. Paula Matuszek
16
Improving backtracking efficiency
• General-purpose methods can give huge
gains in speed:
– Which variable should be assigned next?
– In what order should its values be tried?
– Can we detect inevitable failure early?
CSC 8520 Spring 2010. Paula Matuszek
17
Most constrained variable
• Most constrained variable:
choose the variable with the fewest legal values
• minimum remaining values (MRV)
heuristic
Based on Hwee Tou Ng, [Link]/slides-ppt, which are based on
CSC 8520 Spring 2010. Paula Matuszek Russell, [Link]/slides-pdf.
18
Most constraining variable
• Tie-breaker among most constrained
variables
• Most constraining variable:
– choose the variable with the most constraints
on remaining variables
Based on Hwee Tou Ng, [Link]/slides-ppt, which are based on
Russell, [Link]/slides-pdf.
19
Search Plus Inference
• Even with these heuristics, a straight backtracking
search isn’t very efficient
• Can improve performance by doing some
reasoning or inference.
• Typically, constraint propagation.
• Constraints restrict the possible values for
assignment, which may in turn restrict the
possible values for other assignments.
• Local consistency
• Limits search space; may actually give solution.
20
Forward checking
• Idea:
– Keep track of remaining legal values for unassigned
variables
– Terminate search when any variable has no legal values
21
Forward checking
• Idea:
– Keep track of remaining legal values for unassigned
variables
– Terminate search when any variable has no legal
values
22
Forward checking
• Idea:
– Keep track of remaining legal values for unassigned
variables
– Terminate search when any variable has no legal values
23
Forward checking
• Idea:
– Keep track of remaining legal values for unassigned
variables
– Terminate search when any variable has no legal values
24
Constraint propagation
• Forward checking propagates information from assigned to unassigned
variables, but doesn't provide early detection for all failures:
NT Q
SA
NSW
• NT and SA cannot both be blue!
• Constraint propagation repeatedly enforces constraints locally
25
Arc consistency
• Simplest form of propagation makes each arc consistent
• X Y is consistent iff
for every value x of X there is some allowed y
consistent consistent
•Arc refers to a directed arc in the constraint graph, such as the arc
from SA to NSW.
•The current domains of SA and NSW,the arc is consistent if, for
every value x of SA, there is some value y of NSW that is consistent
with x.
26
Arc consistency
• Simplest form of propagation makes each arc consistent
• X Y is consistent iff
for every value x of X there is some allowed y
•The assignment NSW = blue, there is no consistent assignment for
SA.
• The arc can be made consistent by deleting the value blue from the
domain of NSW.
27
Arc consistency
• Simplest form of propagation makes each arc consistent
• X Y is consistent iff
for every value x of X there is some allowed y
• If X loses a value, neighbors of X need to be rechecked
28
Arc consistency
• Simplest form of propagation makes each arc consistent
• X Y is consistent iff
for every value x of X there is some allowed y
• If X loses a value, neighbors of X need to be rechecked
• Arc consistency detects failure earlier than forward checking
• Can be run as a preprocessor or after each assignment
29
Arc consistency algorithm AC-3
• Time complexity: O(n2d3)
30
K-Consistency
• Can extend this to an arbitrary number k of variables
• a CSP is k-consistent if for any set of k - 1 variables and a consistent
assignment to those variables, a consistent value can be assigned to
the kth variable.
• However, costly. In practice, don’t usually go beyond AC-3 (2-
consistency) and PC-2 (3-consistency)
For example,
• 1-consistency means that each individual variable by itself is
consistent; this is also called node consistency.
• 2-consistency is the same as arc consistency.
• 3-consistency means that any pair of adjacent variables can always be
extended to a third neighboring variable; this is also called path
consistency.
31
Path Consistency
• Consider coloring Australia with 2 colors.
– Clearly not possible. WA, for example, touches two other countries.
– AC-3 will not detect this immediately.
• Path consistency extends it to look at triples of variables.
• A two-variable set X, Y is path-consistent with a third variable Z iff
– for every value a of X and b of Y which satisfies the constraints on
{X, Y}
– there is a value c of Z which satisfies the constraints on {X,Z} and
{Z,Y}.
• Can look at it as looking at a path from X to Y with Z in the middle.
• Path consistency algorithm PC-2 is extension of AC-3.
32
Global Constraints
• Some global constraints have specialized
algorithms or heuristics
– AllDiff: all variables are distinct
• Sudoku rows, columns, boxes
– AtMost: resources are constrained
• Scheduling 10 people on 4 tasks
33
AllDiff
• If there are m variables and n possible values, any
time m>n it is inconsistent
• Algorithm:
– find all variables with singleton domains (there is only
one value which satisfies the constraint)
– remove that value from domains of remaining variables
• If m>n or any domain is empty, inconsistent.
• Classic way to solve easy Sudoku puzzles
• Reduces search space for more difficult puzzles.
34
Resource Constraints
• Constraints expressed as maximum a sum of values
can reach: 10 people assigned to 4 tasks
• Each task can have 1,2,3...10 people initially.
– T1 = [1, 2, ...10]; T2 = [1,2,...10] etc.
• Sum minimum values of the current domains for each
task; if >10, inconsistent
• We can also enforce consistency by deleting the
maximum value of any domain if it is not consistent
with the minimum values of the other domains.
35
Bounds Propagation
• For larger problems: 420 people on planes
with capacities 165 and 385 passengers.
• Individual variables get min and max
instead of enumerated values
– Plane1 = [0, 165]; Plane2 = [0, 385]
• Propagating the bounds gives us
– Plane1 = [35, 165]; Plane2 = [255, 385]
36
Local search for CSPs
• Local-search algorithms is effective in solving many CSPs.
• They use a complete-state formulation: the initial state
assigns a value to every variable, and change the value of
one variable at a time.
• Variable selection: randomly select any conflicted variable
• Value selection by min-conflicts heuristic:
– choose value that violates the fewest constraints
– i.e., hill-climb with h(n) = total number of violated
constraints
37
Example: 4-Queens
• States: 4 queens in 4 columns (44 = 256 states)
• Actions: move queen in column
• Goal test: no attacks
• Evaluation: h(n) = number of attacks
• Given random initial state, can solve n-queens in almost constant time for
arbitrary n with high probability (e.g., n = 10,000,000)
38
Local Search
• Works best when solutions are dense
– 8 queens has many solutions; good
– Proper Sudoku puzzles have one; bad
• All the usual problems, and solutions, for local search
• Constraint weighing adjusts weight of constraints
which have not been solved: help focus on harder
problems.
• Especially useful when problem gets small changed
– airline scheduling when PHL closes
39
Summary
• CSPs are a special kind of problem:
– states defined by values of a fixed set of variables
– goal test defined by constraints on variable values
• Backtracking = depth-first search with one variable assigned
per node
• Variable ordering and value selection heuristics help
significantly
• Forward checking prevents assignments that guarantee later
failure
• Constraint propagation (e.g., arc consistency) does additional
work to constrain values and detect inconsistencies
• Iterative min-conflicts is often effective in practice
40
Thanks for Listening
