Wolkite University
College of Computing and Informatics
Department of Computer Science
Constraint Satisfaction Problems
Prepared by Adem (MSc.)
August 10, 2022
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 1 / 26
Outline
1 Constraint satisfaction problems
2 Constraint Graph
3 Types of Variables
4 Backtracking Search
5 Summary
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 2 / 26
Constraint satisfaction problems
Previous search problems:
Problems can be solved by searching in a space of states
state is a "black box" any data structure that supports successor
function, heuristic function and goal test
problem specific
Constraint satisfaction problem
states and goal test conform to a standard,
structured and simple representation
general-purpose heuristic
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 3 / 26
Cont..
CSP is defined by a set of variables, X1, X2,. . . , Xn, and a set of
constraints, C1, C2,. . . ,Cm,.
CSP:
state is defined by variables Xi with values from domain Di
Each state in a CSP is defined by an assignment of values to some
or all of the variables
An assignment that does not violate any constraints is called a
consistent or legal assignment
A complete assignment is one in which every variable is assigned
A solution to a CSP is consistent and complete assignment
goal test is a set of constraints specifying allowable combinations
of values for subsets of variables
Allows useful general-purpose algorithms with more power than
standard search algorithms.
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 4 / 26
Cont..
Definition
State is defined by a set of variables Xi
Each variable can be unassigned (partial solution) or have a value
from domain Di.
Constraints are a set of rules specifying allowable combinations
of values for subsets of variables
Solution: a state that is a
Consistent assignment: satisfies all constraints
Complete assignment: assigns value to each variable
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 5 / 26
Example: Map-Coloring
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 6 / 26
Example: Cryptarithmetic
Variables: T , W , O, F,U, R, C1, C2, C3
Domains:Di = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Constraints:
alldiff(T , W, O, F, U, R)
O + O = R + 10 × C1
C1 + W + W = U + 10 × C2
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 7 / 26
Example: Sudoku
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 8 / 26
Cont...
Variables: each (open) square
Domains:Di = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Constraints:
9-way for each column
9-way for each row
9-way for each region
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 9 / 26
Cont..
Variables: X = WA, NT, Q, NSW, V, SA, T
Domains: Di = red, green, blue
Constraints: adjacent regions must have different colors
Solution , WA = red, NT = green, Q = red, NSW = green, V =
red, SA = blue, T = red
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 10 / 26
Constraint Graph
Constraint graph: nodes are variables, arcs are constraints
Binary CSP: each constraint relates two variables
CSP conforms to a standard pattern
a set of variables with assigned
values
generic successor function and
goal test
generic heuristics
reduce comp
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 11 / 26
Types of Variables
Discrete variables
finite domains:
n variables, domain size d = complete assignments
e.g., Boolean CSPs, such as 3 SAT (NP complete)
Worst case, can’t solve finite-domain CSPs in less than exponential
time
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 less than or equal to
StartJob3
Continuous variables
e.g., start/end times for Hubble Space Telescope observations
linear constraints solvable in polynomial time by linear
programming
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 12 / 26
Cont..
Unary constraints involve a single variable,
e.g., SA not equal green
Binary constraints involve pairs of variables,
e.g., SA not equal WA
Higher-order constraints involve 3 or more variables
e.g., cryptarithmetic column constraints
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 13 / 26
Real-World CSPs
Assignment problems
e.g., who teaches what class
Timetabling problems
e.g., which class is offered when and where
Transportation scheduling
Factory scheduling
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 14 / 26
CSP as a Standard Search Formulation
State:
Values assigned so far
Initial state:
The empty assignment (all variables are unassigned)
Successor function:
Choose an unassigned variable and assign it a value that does not
violate any constraints Fail if no legal assignment is found
Goal state:
Any complete and consistent assignment.
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 15 / 26
Backtracking Search
Only need to consider assignments to a single variable at each
node b = d and there are d the power of n leaves
Backtracking search is used for a depth-first search that chooses
values for one variable at a time and
backtracks when a variable has no legal values left to assign
Backtracking search is the basic uninformed algorithm for CSP
Depth-first search for CSPs with single-variable assignments is
called backtracking search
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 16 / 26
Backtracking Example
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 17 / 26
Backtracking search algorithm
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 18 / 26
Improving backtracking
Improving backtracking
Can we improve backtracking using general-purpose ideas, without
domain specic knowledge
Ordering:
Which variable should be assigned next?
In what order should its values be tried?
Filtering:
can we detect inevitable failure early?
Structure:
can we exploit the problem structure?
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 19 / 26
Cont...
Variable ordering
Minimum remaining values:
Choose the variable with the fewest legal values left in its domain.
Also known as the fail-first heuristic
Detecting failures quickly is equivalentto pruning large parts ofthe
search tree.
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 20 / 26
Cont...
Value ordering
Least constraining value:
Given a choice of variable, choose the least constraining value.
i.e.,the value that rules out the fewest values in the remaining
variables.
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 21 / 26
Cont...
Filtering: Forward checking
Keep track of remaining legal values for unassigned variables.
Whenever a variable is assigned, and for each unassigned variable
that is connected to
by a constraint, delete from ’s domain any value that is inconsistent.
Terminate search when any variable has no legal value left.
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 22 / 26
Cont...
Filtering: Constraint propagation
Forward checking propagates information assigned to unassigned
variables, but does not provide early detection for all failures:
NT and SA cannot both be blue!
Constraint propagation repeatedly enforces constraints locally.
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 23 / 26
Cont...
Arc consistency
X is arc consistent wrt Y, for every value of X there is some
allowed value of Y.
Make X arc consistent wrt Y by throwing out any values of X for
which there is no allowed value of Y.
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 24 / 26
Backtracking search with inference
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 25 / 26
Summary
CSPs are a special type of search problem:
States are structured and defined by a set of variables and values
assignments
Variables can be unassigned
Goal test defined by
Consistency with constraints
Completeness of assignment
Backtracking search = depth-first search where a successor state
is generated by a consistent value assignment to a single
unassigned variable
Prepared by Adem (MSc.) Introduction to Artificial intelligence August 10, 2022 26 / 26
