Artificial Intelligence

Constraint Satisfaction
Problems
By Harshit Mogalapalli
Recall
• Search problems:

– Find the sequence of actions that leads to the goal.

– Sequence of actions means a path in the search space.

– Paths come with different costs and depths.

– We use “rules of thumb” aka heuristics to guide the search

efficiently.

• Constraint satisfaction problems:

– A search problem too!

– We care about the goal itself.

CSPs definition
• Search problems:

– A state is a black box, implemented as some data structure.

– A goal test is a function over the states.

CSPs definition
• CSPs problems:

– A state: defined by variables X i with values from

domain

– A goal test is a set of constraints specifying

allowable combinations of values for subsets of variables.
CSPs definition

• A constraint satisfaction problem consists of three elements:

– A set of variables, X = {X 1 , X 2 , · · · X n }

– A set of domains for each variable: D = {D 1 , D 2 , · · ·

Dn }

– A set of constraints C that specify allowable combinations of

values.
constraints.
• Solving the C SP: finding the assignment(s) that satisfy all
• C oncepts: problem formalization, backtracking search,
consistency, etc. arc

• We call a solution, a consistent assignment.

Example: Map coloring

Variables: X = { WA, N T , Q, NSW, V , SA, T }

Domains: D i = {red, green, blue}

Constraints: adjacent regions must have di↵erent colors;

e.g., WA 6= N T or ( W A, N T ) 2 {(red, green), (red, blue), etc..}

Example: Map coloring

Example:
{ WA=red, NT=green, Q=red, NSW=green,V=red, SA=blue,T=green }
Real-world CSPs
• Assignment problems, e.g., who teaches what class?

• T imetabling problems, e.g., which class is o↵ered when

and where?

• Hardware configuration

• Transportation scheduling

• Factory scheduling

• Floor planning

• Notice that many real-world problems involve real-valued vari-

ables
Constraint graph

Binary CSP: each constraint relates at most two variables Con-

straint graph: nodes are variables, arcs show constraints

CSP algorithms: use the graph structure to speed up

search. E.g., Tasmania is an independent subproblem!
Example: N-Queens
Formulation 1:
Variables:
Domains:
Constraints
Example Cryptarithmetic

Variables: X = {F, T, U, W, R , O, C 1 , C 2 , C3}

Domain: D = {0, 1, 2, · · · , 9}
Constraints:
• All different(F, T, U, W, R , O )
• T 0, F 6= 0
• O + O = R + 10 C 1
• C 1 + W + W = U + 10 C 2
• C 2 + T + T = O + 10 C 3
• C3 = F
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)
Varieties of variables
• Discrete variables:
– Finite domains:
assume n variables, d values, then the number of complete
assignments is O(d n ).

e.g., map coloring, 8-queens problem

– Infinite domains (integers, strings, etc.): need to use a

constraint language,

e.g., job scheduling. T1 + d T2 .

• Continuous variables:
– Common in operations research

– L inear programming with linear or non linear

problems equalities
Varieties of constraints

• Unary constraints: involve a single variable e.g., S A 6=

green

• Binary constraints: involve pairs of variables e.g., S A 6=

WA

• Global constraints: involve 3 or more variables e.g., Alldi↵ that

specifies that all variables must have di↵erent values (e.g.,
cryptarithmetic puzzles, Sudoku)

• Preferences (soft constraints):

– Example: red is better than green

– Often represented by a cost for each variable assignment

– constrained optimization problems

Solving CSPs
Important
• State-space search algorithms: search!

• CSP Algorithms: Algorithm can do two things:

– Search: choose a new variable assignment from many pos-
sibilities

– Inference: constraint propagation, use the constraints to

spread the word: reduce the number of values for a variable
which will reduce the legal values of other variables etc.

• As a preprocessing step, constraint propagation can sometimes

solve the problem entirely without search.

• Constraint propagation can be intertwined with search.

Solving CSPs
• BFS: Develop the complete tree

• DFS: Fine but time consuming

• BTS: Backtracking search is the basic uninformed

search for CSPs. It’s a D F S s.t.

1. Assign one variable at a time: assignments are commuta-

tive. e.g., (WA=red, NT=green) is same as (NT=green,
WA=red)

2. Check constraints on the go: consider values that do not

conflict with previous assignments.
Solving CSPs
• Initial state: empty assignment {}

• States: are partial assignments

• Successor function: assign a value to an unassigned

variable

• Goal test: the current assignment is complete and satisfies

all constraints
Backtracking search
Backtracking search
Backtracking search
Backtracking search
Improving BTS

Heuristics are back!

1. Which variable should be assigned next?

2. In what order should its values be tried?

3. Can we detect inevitable failure early?

Minimum Remaining Values
1. Which variable should be assigned next?

• MRV: Choose the variable with the fewest legal values in its
domain

Pick the hardest!

Least constraining value
2. In what order should its values be tried?

• LCV: Given a variable, choose the least constraining value: the

one that rules out the fewest values in the remaining variables

Pick the ones that are likely to work!

Forward checking
3. Can we detect inevitable failure early?

• FC: K eep track of remaining legal values for the

unassigned variables. Terminate when any variable has no
legal values.
Forward checking
3. Can we detect inevitable failure early?

• FC: K eep track of remaining legal values for the

unassigned variables. Terminate when any variable has no
legal values.
Forward checking
3. Can we detect inevitable failure early?

• FC: K eep track of remaining legal values for the

unassigned variables. Terminate when any variable has no
legal values.
Forward checking
3. Can we detect inevitable failure early?

• FC: K eep track of remaining legal values for the

unassigned variables. Terminate when any variable has no
legal values.
Backtracking search
Solving CSPs: Sudoku
All 3x3 boxes, rows, columns, must contain all digits 1..9.
Solving CSPs: Sudoku
All 3x3 boxes, rows, columns, must contain all digits 1..9.

Variables: V = {A 1 , · · · , A 9 , B 1 , · · · , B 9 , · · · , I 1 · · · I9 }, |V | = 81.
Domain: D = {1, 2, ·· · , 9}, the filled squares have a single value.
Constraints: 27 constraints
• Alldiff(A 1 , A 2 , A 3 , A 4 , A 5 , A 6 , A 7 , A 8 , A 9 )
···
• Alldiff(A 1 , B 1 , C 1 , D 1 , E 1 , F 1 , G 1 , H 1 , I 1 )
···
• Alldiff(A 1 , A 2 , A 3 , B 1 , B 2 , B 3 , C 1 , C 2 , C 3 )
Constraint propagation
• F orward checking propagates information from assigned
to unassigned variables.
• Observe:

– Forward checking does not check interaction between unas-

signed variables! Here S A and N T ! (They both must be
blue but can’t be blue!).
Constraint propagation
• F orward checking propagates information from assigned
to unassigned variables.
• Observe:

– Forward checking does not check interaction between unas-

signed variables! Here S A and N T ! (They both must be
blue but can’t be blue!).
• Forward checking improves backtracking search but does not
look very far in the future, hence does not detect all failures.
• We use constraint propagation, reasoning from constraint
to constraint. e.g., arc consistency test.
Types of Consistency
• Node-consistency (unary constraints): A variable X i is node-
consistent if all the values of D o m a i n ( X i ) satisfy all unary
constraints.

• Arc-consistency (binary constraints): X Y is arc-consistent if and

only if every value x of X is consistent with some value y of Y .

• Path-consistency (n-ary constraints): generalizes arc- consistency

from binary to multiple constraints.

• Note: It is always possible to transform all n-ary constraints

into binary constraints. Often, CSPs solvers are designed to
work with binary constraints.
Arc consistency
• AC: Simplest form of propagation makes each arc consistent.
• X ! Y is consistent I F F for every value x of X , there is
some allowed y.
Arc consistency
• AC: Simplest form of propagation makes each arc consistent.
• X ! Y is consistent I F F for every value x of X , there is
some allowed y.
Arc consistency
• AC: Simplest form of propagation makes each arc consistent.
• X ! Y is consistent I F F for every value x of X , there is
some allowed y.
Arc consistency
• AC: Simplest form of propagation makes each arc consistent.
• X ! Y is consistent I F F for every value x of X , there is
some allowed y.
Arc consistency
Algorithm that makes a CSP arc-consistent!
Complexity of AC-3
• Let n be the number of variables, and d be the domain size.

• If every node (variable) is connected to the rest of the

variables, then we have n ⇤( n — 1) arcs (constraints) !
O(n2 )

• Each arc can be inserted in the queue d times ! O(d)

• Checking the consistency of an arc costs ! O(d 2 ).

• Overall complexity is O(n 2 d 3 ).

Backtracking w/ inference
Problem structure

• Idea: Leverage the problem structure to make the search

more
efficient.
• Example: Tasmania is an independent problem.
• Identify the connected component of a graph constraint.
• Work on independent subproblems.
Problem structure
Complexity:
• Let d be the size of the domain and n be the number of vari-
ables.

• Time complexity for B T S is O (d n ) .

• Suppose we decompose into subproblems, with c variables per

subproblem.
• Then we have n subproblems
c .
• c variables per subproblem takes O(d c ).

• The total for all subproblems takes O ( nc c d ) in the worst

case.
Problem structure
Example:
• Assume n = 80, d = 2.

• Assume we can decompose into 4 subproblems with c = 20.

• Assume processing at 10 million nodes per second.

• Without decomposition of the problem we need:

280 = 1.2 ⇥ 1024
3.83 million years!

• With decomposition of the problem we need:

4 ⇥ 220 = 4.2 ⇥ 106
0.4 seconds!
Problem structure
• Turning a problem into independent subproblems is not always
possible.

• Can we leverage other graph structures?

• Yes, if the graph is tree-structured or nearly tree-structured.

• A graph is a tree if any two variables are connected by only

one path.

• Idea: use DAC, Directed Arc Consistency

• A C S P is said to be directed arc-consistent under an ordering

X 1 , X 2 , . . . , X n I F F every X i is arc-consistent with each X j for
j > i.
Problem structure

• First pick a variable to the be the root.

• Do a topological sorting: choose an ordering of the

variables
s.t. each variable appears after its parent in the tree.

• For n nodes, we have n - 1 edges.

• Make the tree directed arc-consistent takes O ( n )

• Each consistency check takes up to O(d 2 ) (compare d possible

values for 2 variables).

• The C S P can be solved in O(nd 2 )

Nearly tree-structured CSPs

• Assign a variable or a set of variables and prune all the neigh-

bors domains.

• This will turn the constraint graph into a tree :)

• There are other tricks to explore, have fun!

Solving CSPs: Sudoku
All 3x3 boxes, rows, columns, must contain all digits 1..9.