07 – Constraint Satisfaction Problems

• Compiled by: Dr. Mohammad Alhawarat
• Department of Computer Science
• Faculty of Information Technology
• Middle East University
• Spring 2023

Agenda

​

• CSP Definition
• Constraint Graphs
• Backtracking
• Improving Backtracking
• Local search for CSPs

​

What is Search For?

• Assumptions about the world: a single agent, deterministic actions, fully observed state, discrete state space

​

• Planning: sequences of actions
• The path to the goal is the important thing
• Paths have various costs, depths
• Heuristics give problem-specific guidance

​

• Identification: assignments to variables
• The goal itself is important, not the path
• All paths at the same depth (for some formulations)
• CSPs are specialized for identification problems

Constraint Satisfaction

• Kind of search in which
• States are factored into sets of variables
• Search = assigning values to these variables
• Structure of space is encoded with constraints
• Backtracking-style algorithms work
• E.g. DFS for SAT (i.e. DPLL)
• But other techniques add speed
• Propagation
• Variable ordering
• Preprocessing

© Daniel S. Weld

4

Chinese Constraint Network

© Daniel S. Weld

5

Soup

Total Cost

< $30

Chicken

Dish

Vegetable

Rice

Seafood

Beef Dish

Appetizer

Must be

Hot&Sour

No

Peanuts

No

Peanuts

Not

Chow Mein

Not Both

Spicy

Constraint Satisfaction Problems

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 X_i with values from a domain D (sometimes D depends on i)
• Goal test is a set of constraints specifying allowable combinations of values for subsets of variables

​

• Simple example of a formal representation language

​

• Allows useful general-purpose algorithms with more power than standard search algorithms

​

CSP Examples

Example: Map Coloring

• Variables:

​

• Domains:

​

• Constraints: adjacent regions must have different colors

​

​

​

​

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

​

​

Implicit:

Explicit:

Example: N-Queens

• Formulation:
• Variables:

​

• Domains:

​

• Constraints:

Implicit:

Explicit:

Constraint Graphs

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!

[Demo: CSP applet (made available by aispace.org) -- n-queens]

Screenshot of Demo N-Queens

Example: Cryptarithmetic

• Variables:

​

• Domains:

​

• Constraints:

​

Example: Sudoku

• Variables:
• Each (open) square
• Domains:
• {1,2,…,9}
• Constraints:

​

​

9-way alldiff for each row

9-way alldiff for each column

9-way alldiff for each region

(or can have a bunch of pairwise inequality constraints)

Varieties of CSPs and Constraints

Varieties of CSPs

• Discrete Variables
• Finite domains
• Size d means O(dⁿ) 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 (see cs170 for a bit of this theory)

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)

​

​

Real-World CSPs

• Assignment problems: e.g., who teaches what class
• Timetabling problems: e.g., which class is offered when and where?
• Hardware configuration
• Transportation scheduling
• Factory scheduling
• Circuit layout
• Fault diagnosis
• … lots more!

​

​

​

• Many real-world problems involve real-valued variables…

Solving CSPs

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

​

Search Methods

• What would BFS do?

​

​

​

• What would DFS do?

​

​

​

• What problems does naïve search have?

[Demo: coloring -- dfs]

Video of Demo Coloring -- DFS

Backtracking Search

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

Backtracking Example

Backtracking Search

• Backtracking = DFS + variable-ordering + fail-on-violation
• What are the choice points?

[Demo: coloring -- backtracking]

Video of Demo Coloring – Backtracking

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?

​

Filtering

Filtering: Forward Checking

• Filtering: Keep track of domains for unassigned variables and cross off bad options
• Forward checking: Cross off values that violate a constraint when added to the existing assignment

WA

SA

NT

Q

NSW

V

[Demo: coloring -- forward checking]

Video of Demo Coloring – Backtracking with Forward Checking

Filtering: 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!
• Why didn’t we detect this yet?
• Constraint propagation: reason from constraint to constraint

WA

SA

NT

Q

NSW

V

Consistency of A Single Arc

• An arc X → Y is consistent iff for every x in the tail there is some y in the head which could be assigned without violating a constraint

​

​

​

​

​

​

​

​

​

​

​

• Forward checking: Enforcing consistency of arcs pointing to each new assignment

Delete from the tail!

WA

SA

NT

Q

NSW

V

Arc Consistency of an Entire CSP

• A simple form of propagation makes sure all arcs are consistent:

​

​

​

​

​

​

​

​

• Important: 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
• What’s the downside of enforcing arc consistency?

Remember: Delete from the tail!

WA

SA

NT

Q

NSW

V

Enforcing Arc Consistency in a CSP

• Runtime: O(n²d³), can be reduced to O(n²d²)
• … but detecting all possible future problems is NP-hard – why?

[Demo: CSP applet (made available by aispace.org) -- n-queens]

Video of Demo Arc Consistency – CSP Applet – n Queens

Limitations of Arc Consistency

• After enforcing arc consistency:
• Can have one solution left
• Can have multiple solutions left
• Can have no solutions left (and not know it)

​

• Arc consistency still runs inside a backtracking search!

What went wrong here?

[Demo: coloring -- arc consistency]

[Demo: coloring -- forward checking]

Video of Demo Coloring – Backtracking with Forward Checking – Complex Graph

Video of Demo Coloring – Backtracking with Arc Consistency – Complex Graph

Ordering

Ordering: Minimum Remaining Values

• Variable Ordering: Minimum remaining values (MRV):
• Choose the variable with the fewest legal left values in its domain

​

​

​

​

​

• Why min rather than max?
• Also called “most constrained variable”
• “Fail-fast” ordering

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)

​

• Why least rather than most?

​

• Combining these ordering ideas makes

1000 queens feasible

QUESTIONS