Constraint SatisfactionOverviewInformal Definition of CSPSEND + MORE = MONEYSlide 5ModelingA Model for MONEYA Model for MONEY (continued)Solution for MONEYExample: Map ColoringSlide 11N-queens Example (4 in our case)Example: SATisfiabilityReal-world problemsFormal definition of a CSPSlide 16Typical Tasks for CSPBinary CSPBinary Constraint GraphMatrix Representation for Binary ConstraintsConstraint Solving is HardCSP as a Search ProblemSystematic search: Backtracking (a.k.a. depth-first search)Backtracking searchSlide 25Backtracking exampleSlide 27Slide 28Slide 29Example: Crossword PuzzleExample: XWORD PuzzleBacktracking: XWORDS E N D + M O R E = M O N E YSlide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Problems with backtrackingImproving backtracking efficiencyMost constrained variableMost constraining variableLeast constraining valueForward checkingSlide 48Slide 49Slide 50Constraint propagationIssues in PropagationCompleteness of PropagationExample: Complete All DifferentSlide 55Basic Constraints vs. PropagatorsSymmetry BreakingSlide 58Performance of Symmetry BreakingOptimizationOptimization: ExampleSEND + MOST = MONEYBranch and BoundConsistencyArc consistencySlide 66Slide 67Slide 68Arc consistency algorithm AC-3Slide 70Constraint propagation: XWORD exampleThe Sudoku PuzzleSudoku as a CSP (9x9 puzzles)Solving Sudoku as a CSPSearchForward Checking (FC)Maintaining Arc-Consistency (MAC)Generalized Arc-Consistency (GAC)The way people playK-consistencyWhy do we care?Improving BacktrackingThe FutureACC 1997/98: A Success Story of Constraint ProgrammingRound Robin Tournament Planning ProblemsThe ACC 1997/98 ProblemThe ACC 1997/98 ProblemSlide 88Slide 89Slide 901Constraint SatisfactionConstraint SatisfactionReading: Russell & Norvig Chapter 5,Kumar: “Algorithms for constraint satisfaction problems: A survey”2Overview•Constraint Satisfaction Problems (CSP) share some common features and have specialized methods–View a problem as a set of variables to which we have to assign values that satisfy a number of problem-specific constraints.–Constraint solvers, constraint logic programming…•Algorithms for CSP–Backtracking (systematic search)–Constraint propagation (k-consistency)–Variable ordering heuristics–Backjumping and dependency-directed backtracking3Informal Definition of CSP•CSP = Constraint Satisfaction Problem•Given(1) a finite set of variables(2) each with a domain of possible values (often finite)(3) a set of constraints that limit the values the variables can take on•A solution is an assignment of a value to each variable such that all the constraints are satisfied.•Tasks might be to decide if a solution exists, to find a solution, to find all solutions, or to find the “best solution” according to some metric.4SEND + MORE = MONEYAssign distinct digits to the lettersS, E, N, D, M, O, R, Ysuch that S E N D + M O R E = M O N E Yholds.5SEND + MORE = MONEYAssign distinct digits to the lettersS, E, N, D, M, O, R, Ysuch that S E N D + M O R E = M O N E Yholds. Solution 9 5 6 7 + 1 0 8 5 = 1 0 6 5 26ModelingFormalize the problem as a CSP:•number of variables: n•constraints: c1,…,cm  n•problem: Find a = (v1,…,vn) n such that a  ci , for all 1  i  m7A Model for MONEY•number of variables: 8•constraints: c1 = {(S,E,N,D,M,O,R,Y) 8 | 0  S,…,Y  9 } c2 = {(S,E,N,D,M,O,R,Y) 8 | 1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E = 10000*M + 1000*O + 100*N + 10*E + Y}8A Model for MONEY (continued)•more constraints c3 = {(S,E,N,D,M,O,R,Y) 8 | S  0 } c4 = {(S,E,N,D,M,O,R,Y) 8 | M  0 } c5 = {(S,E,N,D,M,O,R,Y) 8 | S…Y all different}9Solution for MONEY c1 = {(S,E,N,D,M,O,R,Y) 8 | 0S,…,Y9 } c2 = {(S,E,N,D,M,O,R,Y) 8 | 1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E = 10000*M + 1000*O + 100*N + 10*E + Y} c3 = {(S,E,N,D,M,O,R,Y) 8 | S  0 } c4 = {(S,E,N,D,M,O,R,Y) 8 | M  0 } c5 = {(S,E,N,D,M,O,R,Y) 8 | S…Y all different}Solution: (9,5,6,7,1,0,8,2) 810Example: Map Coloring•Color the following map using three colors (red, green, blue) such that no two adjacent regions have the same color.ED ACB11Example: Map Coloring•Variables: A, B, C, D, E all of domain RGB•Domains: RGB = {red, green, blue}•Constraints: AB, AC,A  E, A  D, B  C, C  D, D  E•One solution: A=red, B=green, C=blue, D=green, E=blueED ACBED ACB=>12N-queens Example (4 in our case)•Standard test case in CSP research•Variables are the rows: r1, r2, r3, r4•Values are the columns: {1, 2, 3, 4}•So, the constraints include:–Cr1,r2 = {(1,3),(1,4),(2,4),(3,1),(4,1),(4,2)}–Cr1,r3 = {(1,2),(1,4),(2,1),(2,3),(3,2),(3,4), (4,1),(4,3)}–Etc.–What do these constraints mean?13Example: SATisfiability•Given a set of propositions containing variables, find an assignment of the variables to {false,true} that satisfies them.•Example, the clauses:–A \/ B \/ ~C, ~A \/ D–(equivalent to C -> A \/ B, A -> D)•Are satisfied byA = falseB = trueC = falseD = false14Real-world problems•Scheduling•Temporal reasoning•Building design•Planning•Optimization/satisfaction•Vision•Graph layout•Network management•Natural language processing•Molecular biology / genomics•VLSI design15Formal definition of a CSPA constraint satisfaction problem (CSP) consists of•a set of variables X = {x1, x2, … xn} –each with an associated domain of values {d1, d2, … dn}. –The domains are typically finite•a set of constraints {c1, c2 … cm} where –each constraint defines a predicate which is a relation over a particular subset of X. –E.g., Ci involves variables {Xi1, Xi2, … Xik} and defines the relation Ri  Di1 x Di2 x … Dik•Unary constraint: only involves one variable•Binary constraint: only involves two variables16Formal definition of a CSP•Instantiations–An instantiation of a subset of variables S is an assignment of a legal domain value to each variable in in S–An instantiation is legal iff it does not violate any (relevant) constraints.•A solution is an instantiation of all of the variables in the network.17Typical Tasks for CSP•Solutions:–Does a solution exist?–Find one solution–Find all solutions–Given a partial