Artificial Intelligence

6 CONSTRAINT
SATISFACTION PROBLEMS
Russell & Norvig, AI: A Modern Approach, 3rd Ed

01/18/2021 1
 Constraint Satisfaction Problems
• Standard search problems:
• State is a “black box”: arbitrary data structure
• Goal test can be any function over states
• Successor function can also be anything

• Constraint satisfaction problems (CSPs):

• A special subset of search problems
• State is defined by variables Xi with values from a domain
D (sometimes D depends on i)
• Goal test is a set of constraints Ci specifying allowable
combinations of values for subsets of variables

• Allows useful general-purpose algorithms with more power than

standard search algorithms
2
Constraint Satisfaction Problems

3
CSP Examples

4
 Example: Map Coloring
• Variables:

• Domains:

• Constraints: adjacent regions must have different colors

Implicit:

Explicit:

• Solutions are assignments satisfying all constraints, e.g.:

5
Constraint Graphs

6
 Constraint Graphs
• Binary CSP: each constraint relates (at most) two
variables

• Binary constraint graph: nodes are variables, arcs

show constraints

• General-purpose CSP algorithms use the graph

structure to speed up search. E.g., Tasmania is an
independent subproblem!

7
 Example: Cryptarithmetic
• Variables:

• Domains:

• Constraints:

8
Example: Cryptarithmetic
Example: Sudoku
 Variables:
 Each (open) square
 Domains:
 {1,2,…,9}
 Constraints:
9-way alldiff for each column
9-way alldiff for each row
9-way alldiff for each region
(or can have a bunch of
pairwise inequality
constraints)

10
Varieties of CSPs and Constraints

11
 Varieties of CSPs
• 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., job scheduling, variables are start/end times for each job
• 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

12
 Types of Constraint
• Unary Constraint
• Binary
• Ternary
• Global Constraint- alldiff
• Absolute Constraint
• Preference Constraint – Constraint Optimization Problem

13
 Varieties of Constraints
• Varieties of Constraints
• Unary constraints involve a single variable (equivalent to
reducing domains), e.g.:

• Binary constraints involve pairs of variables, e.g.:

• Higher-order constraints involve 3 or more variables:

e.g., cryptarithmetic column constraints

• Preferences (soft constraints):

• E.g., red is better than green
• Often representable by a cost for each variable assignment
• Gives constrained optimization problems
• (We’ll ignore these until we get to Bayes’ nets)
14
Solving CSPs

15
 Standard Search Formulation
• Standard search formulation of CSPs

• States defined by the values assigned so far

(partial assignments)
• Initial state: the empty assignment, {}
• Successor function: assign a value to an
unassigned variable
• Goal test: the current assignment is complete
and satisfies all constraints

• We’ll start with the straightforward, naïve

approach, then improve it

16
Search Methods

• What would DFS do?

17
Backtracking Search

18
 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 as [NT = green then WA =
red]
• Only need to consider assignments to a single variable at each step
• Idea 2: Check constraints as you go
• I.e. consider only values which do not conflict 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 19
Backtracking Example

20
Backtracking Search

• Backtracking = DFS + variable-ordering + fail-on-violation

• What are the choice points?
21
 Improving Backtracking
• General-purpose ideas give huge gains in speed

• 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?

22
 Ordering: Minimum Remaining Values
• Variable Ordering: Minimum remaining values (MRV):
• Fail-first heuristic
• Choose the variable with the fewest legal left values in its domain, thereby pruning
the search tree. If there is a variable X with 0 legal values remaining, then MRV
heuristic will select X and failure will be detected immediately. That helps avoiding
pointless searches through other variables which will always fail when X is finally
selected.
• Also called “most constrained variable”

23
 Ordering: Least Constraining Value
• Value Ordering: Least Constraining Value
• Given a choice of variable, choose the least
constraining value
• I.e., the one that rules out the fewest values in the
remaining variables
• Note that it may take some computation to
determine this! (E.g., rerunning filtering)

24
Filtering

25
 Filtering: Forward Checking
• Filtering: Keep track of domains for unassigned variables and cross off bad options
• Forward checking: Whenever a variable X is assigned, the fwd checking process looks at
each unassigned variable Y that is assigned to X by a constraint & deletes from Y’s
domain any value that is inconsistent with the value chosen for X

NT Q
WA
SA NSW
V

26
 Filtering: Constraint Propagation
• Forward checking propagates information from assigned to unassigned variables, but
doesn't provide early detection for all failures:

NT Q
WA
SA
NSW
V

• NT and SA cannot both be blue!

• Why didn’t we detect this yet?
• Constraint propagation: reason from constraint to constraint

27
Arc Consistency

A network is arc consistent, if every variable is arc consistent.

28
Enforcing Arc Consistency in a CSP

29
Path Consistency

30
K-Consistency

31
K-Consistency

32
K-Consistency

33
K-Consistency

34
Ordering

35
Interleaving Search and inference - Forward checking

36
Interleaving Search and inference - Forward checking

37
MAC(Maintaining arc consistency)

38
Intelligent Backtracking: Looking backward

• Chronological backtracking
• Backjumping: conflict set

39
Local Search for CSPs

• Min-conflicts
• Constraint weighting

40