Solving Constraint Satisfaction Problems Forward Checking Brian C. Williams 16410 October 1st 2003 Slides adapted from 6.034 Tomas Lozano perez With help from Stuart russell Peter norvig CSPS and Encoding 4 Queens Problem: Place queens so that Q none can attack the other Q Assume one queen per column What row should each queen be in? 1234 A Constraint Satisfaction Problem is a triple <v, d,c> Variables v 12,3,以4, Domains d {1,2,3,4} Constraints Q<> On different rows Q-Q|<> Stay off the diagonals Example:C12={(1,3)(14)(2,4)(3,1)(4,1)(4,2)} CSP solution: any assignment to v, such that all constraints in C are satisfied1 Solving Constraint Satisfaction Problems: Forward Checking 1 Brian C. Williams 16.410 October 1st, 2003 Slides adapted from: 6.034 Tomas Lozano Perez With help from: Stuart Russell & Peter Norvig 2 CSPS and Encoding 4 Queens Variables V Constraints C Qi <> Qj On different rows Domains D {1, 2, 3, 4} Q1, Q2, Q3, Q4, 1 2 3 4 12 34 Q Problem: Place queens so that none can attack the other. Q Q Q A Constraint Satisfaction Problem is a triple <V,D,C>: |Qi - Qj | <> |i-j| Stay off the diagonals Example: C1,2 = {(1,3) (1,4) (2,4) (3,1) (4,1) (4,2)} • Assume one queen per column. • What row should each queen be in? CSP solution: any assignment to V, such that all constraints in C are satisfied