Constraint Satisfaction
Problems (CSP)
What is Search For?
• Assumptions about the world : a single agent, deterministic actions,
fully observed state, discrete state space
• Planning: sequences of actions
• Want: path to the goal.
• Paths have various costs, depths.
• Heuristics give problem-specific guidance
• Identification: assignments to variables
• The goal itself is important, not path.
• All paths at same depth (for some formulations)
• CSPs are specialized identification problems
Standard Search and CSP
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 values from domain Di
◦ 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
Constraint Satisfaction Problems
• CSP is defined by a set of variables, X1,X2,……Xn, and a set of
constraints, C1,C2,….Cn.
• Each variable Xi has a non empty domain Di of possible values
• Each constraint Ci involves some subset of the variables and specifies
the allowable combinations of values for that subset.
More on CSP
• A state of the problem is defined by an assignment of values to some
or all of the variables {Xi=vi, Xj=vj….}
• 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 mentioned,
and a soln to a CSP is a complete assignment that satisfies all the
constraints
• Some CSP require a soln that maximizes an objective function
Example: Map Coloring
• Variables: WA, NA, Q, NSW, V, SA, T
• Domains: D = {red, green, blue}
• Constraints: adjacent regions must have
different colors
• Implicit:
• Explicit: (WA,NT) ∈ {(red,green),(red,blue),...,}
• Solutions are assignmets satisfying all
constrains, e.g:
{ WA = red, NT= green, Q = red, NSW=green,
V=red, SA=blue, T=green }
Example: N Queen
Formulation 1:
Variables:
Domains: {0,1}
Constraints:
Example: N Queen
𝑄1
Formulation 2:
𝑄2
Variables:
Domains: {1,2,3, … , N} 𝑄3
Constraints:
Implicit: non threatening 𝑄4
Explicit:
…
…
Constraint Graph
Binary CSP: each constraint relates two
variables
Constraint graph: nodes are variables, arcs are
constraints
General-purpose CSP algorithms use the
graph structure to speed up search.
E.g., Tasmania is an independent subproblem!
Varieties of CSPs and Constraints
• Discrete Variables
• Finite domains
• Size d means O(dn) complete assignments.
• E.g., Boolean CSPs, including Boolean satisfiability (NP-complete)
• Infinite domains (integers, strings, etc.)
• E.g., Scheduling: Variables = Job start times.
• Linear constraints solvable
• Nonlinear undecidable
• Continuous variables
• E.g., start/end times for Hubble Telescope observations
• Linear constraints solvable in polynomial time by LP methods
(see cs170 for a bit of this theory)
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
◦ Preferences (soft constraints):
◦ E.g., red is better than green
◦ Often represented as cost for assignment
◦ Gives constrained optimization problems
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
Search Methods
• What would BFS do?
• What would DFS do?
• What problems does naive search have?
Backtracking Search
• Backtracking search is the basic uninformed algorithm for solving CSPs
• Idea 1: One variable at a time.
• Variable assignments are commutative, so fix ordering
• I.e., [WA = red then NT = green] same same [NT = green then WA = red]
• Assign single variable at each step
• Idea 2: Check constraints as you go.
• I.e. consider values which do not conflict with previous assignments Might have to do some
computation to check the constraints
• “Incremental goal test”
• Depth-first search with these two improvements is called backtracking search (not
the best name)
• Can solve n-queens for n ≈ 25
Backtracking example
Backtracking example
Backtracking example
Backtracking example
• Backtracking = DFS + variable-ordering + fail-on-violation
• What are the choice points?
Most constrained variable
• Most constrained variable:
choose the variable with the fewest legal values
• WA=red and NT=green, one possible value for SA, so rather assign value
at Q we choose SA
• And later Q,NSW and V values are forced. Reduce the unnecessary
backtracking steps, failure will be detect easily
• minimum remaining values (MRV) heuristic
• Fail-first heuristic
Degree Heuristic
• Selecting the variable that involved in the largest number of
constraints on other unassigned variables
• Reduce the branching factor on future choices
• Tie-breaker among most constrained variables
• SA is the variable with highest degree 5
Least constraining value
• Given a variable, choose the least constraining value:
• the one that rules out the fewest choice values in the remaining
variables
• Combining these heuristics makes 1000 queens feasible
Forward checking
• Idea:
• Keep track of remaining legal values for unassigned
variables
• Terminate search when any variable has no legal values
Forward checking
• Idea:
• Keep track of remaining legal values for unassigned
variables
• Terminate search when any variable has no legal values
Forward checking
• Idea:
• Keep track of remaining legal values for unassigned
variables
• Terminate search when any variable has no legal values
Forward checking
• Idea:
• Keep track of remaining legal values for unassigned
variables
• Terminate search when any variable has no legal values
Constraint propagation
• Forward checking propagates information from assigned
to unassigned variables, but doesn't provide early
detection for all failures:
• NT and SA cannot both be blue!
• Constraint propagation repeatedly enforces constraints
locally
Arc consistency
• Arc consistency is based on a very simple concept
• Stronger than Forward Checking
• if we can look at just one constraint and see that x=v is
impossible …obviously we can remove the value x=v from
consideration
• How do we know a value is impossible?
• If the constraint provides no support for the value
• e.g. if Dx= {1,4,5} and Dy= {1, 2, 3}
• then the constraint x > y provides no support for x=1
• we can remove x=1 from Dx
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
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
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
• 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
Arc consistency algorithm AC-3
• A binary CSP O(n2) arcs, each arc (xk,xj) inserted only d times so
O(n2d)..checking consistency of an arc can be done O(d2).
• Time complexity: O(n2d3)
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)
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 usually effective in practice
