Encodings Are Essential: 4 Queens Place queens so that no queen can attack another Variables Q 1234 Domains 1, 2, 3, 4] Constraints Q <>Q On different rows Q-Q1|<>|j Stay off the diagonals Example:C12={(1,3)(1,4)(2,4)(3,1)(4,1)(4,2) What is C? A general class of CSPs Binary CSP Depict as a Constraint Graph each constraint relates at · Nodes are variab|es most two variables Arcs are binary constraints Variable v with Unary constraint arc values in domain D Binary Unary constraints constraint just cut down domains7 Encodings Are Essential: 4 Queens Variables Constraints Qi <> Qj On different rows Domains {1, 2, 3, 4} Q1, Q2, Q3, Q4, 1 2 3 4 1 2 3 4 Q Place queens so that no queen can attack another. Q Q Q |Qi - Qj Stay off the diagonals Example: C1,2 What is C13? 8 Binary CSP most two variables Binary constraint arc Unary constraints just cut down domains Unary constraint arc. Variable Vi with domain Di Depict as a Constraint Graph A general class of CSPs | <> |i-j| = {(1,3) (1,4) (2,4) (3,1) (4,1) (4,2)} • each constraint relates at values in • Arcs are binary constraints • Nodes are variables