Constraint SatisfactionCS472/CS473 — Fall 2005Slide CS472 – Constraint Satisfaction 1Moving to a different formalism...SEND+ MORE--------MONEYConsider state space for cryptarithmetic (e.g. DFS).Is this (DFS) how humans tackle the problem?Human problem solving appears more sophisticated!For example, we derive new constraints on the fly.→ little or no search!Slide CS472 – Constraint Satisfaction 2Constraint Satisfaction Problems (CSP)A powerful representation for (discrete) search problems.A Constraint Satisfaction Problem (CSP) is defined by:X is a set of n variables X1,X2,...,Xn,each defined by a finite domain D1,D2,...,Dnof possible values.C is a set of constraints C1,C2,...,Cm.Each Ciinvolves a subset of the variables; specifiesthe allowable combinations of values for that subset.A solution is an assignment of values to the variablesthat satisfies all constraints.Slide CS472 – Constraint Satisfaction 3Cryptarithmetic as a CSPProblem: TWO+TWO=FOURVa r i a b l e s :T ∈{0,...,9}; W ∈{0,...,9}; O ∈{0,...,9};F ∈{0,...,9}; U ∈{0,...,9}; R ∈{0,...,9};X1∈{0,...,1}; X2∈{0,...,1}; X3∈{0,...,1};Constraints:O + O = R +10∗ X1X1+ W + W = U +10∗ X2X2+ T + T = O +10∗ X3X3= Feach letter has a different digit (F =T,F= U, etc);Slide CS472 – Constraint Satisfaction 4Map-Coloring ProblemWesternAustraliaNorthernTerritorySouthAustraliaQueenslandNew South WalesVictoriaTasmaniaSlide CS472 – Constraint Satisfaction 5Cryptarithmetic Constraint Graph(a)OWTF U R+OWTOWTFOURX2X1X3(b)Slide CS472 – Constraint Satisfaction 6Types of ConstraintsUnary Constraints: Restriction on single variableBinary Constraints: Restriction on pairs of variablesHigher-Order Constraints: Restriction on more than twovariablesSlide CS472 – Constraint Satisfaction 7Constraint Satisfaction Problems (CSP)For a given CSP the problem is one of the following:1. find all solutions2. find one solution• just a feasible solution, or• a “reasonably good” feasible solution, or• the optimal solution given an objective function3. determine if a solution existsSlide CS472 – Constraint Satisfaction 8How to View a CSP as a Search Problem?Initial State – state in which all the variables areunassigned.Successor function – assign a value to a variable from aset of possible values.Goal test – check if all the variables are assigned and allthe constraints are satisfied.Path cost – assumes constant cost for each stepSlide CS472 – Constraint Satisfaction 9Branching FactorApproach 1 – any unassigned variable at a givenstate can be assigned a value by an operator: branchingfactor as high as sum of size of all domains.Approach 2 – since order of variable assignmentnot relevant, consider as the successors of a nodejust the different values of a single unassignedvariable: max branching factor = max size of domain.Maximum Depth of Search Treen the number of variables → all solutions at depth n.Prefer DFS or BFS?Slide CS472 – Constraint Satisfaction 10CSP – Goal Decomposed into ConstraintsBacktracking Search :aDFSthat• chooses values for variables one at a time• checks for consistency with the constraints.Decisions during search :• Which variable to choose next for assignment.• Which value to choose next for the variable.Slide CS472 – Constraint Satisfaction 11ExampleWA=red WA=blueWA=greenWA=redNT=blueWA=redNT=greenWA=redNT=greenQ=redWA=redNT=greenQ=blueSlide CS472 – Constraint Satisfaction 12General Purpose Heuristics• Variable and value ordering:Minimum remaining values (MRV): choose thevariable with the fewest possible values.Degree heuristic: assign a value to the variable that isinvolved in the largest number of constraints on otherunassigned variables.Least-constraining value heuristic: choose a valuethat rules out the smallest number of values in variablesconnected to the current variable by constraints.Slide CS472 – Constraint Satisfaction