Constraint Satisfaction Problems 4 Queens Problem Place 4 queens on a 4x4 隧 chessboard so that no queen can attack another Q How do we formulate? Variables Chessboard positio D ns omain Queen 1-4 or blank Constraints Two positions on a line(vertical horizontal, diagonal)cannot both be Q Constraint Satisfaction Problem(CSP) A Constraint Satisfaction Problem is a triple <V, D, C>, where ° V is a set of variables v D is a set of variable domains The domain of variable v is denoted d C is a set of constraints on assignments to v Each constraint specifies a set of allowed variable values Example °A,Bin{1,2} C={1,2><2,1 A CSP Solution: is any assignment to V, such that all constraints in c are satisfied3 Constraint Satisfaction Problems Variables Constraints Two positions on a line (vertical, horizontal, diagonal) cannot both be Q Domains Queen 1-4 or blank Chessboard positions 1 2 3 4 1 2 3 4 Q 4 Queens Problem: Place 4 queens on a 4x4 chessboard so that no queen can attack another. How do we formulate? Q Q Q 4 Constraint Satisfaction Problem (CSP) A Constraint Satisfaction Problem is a triple <V,D,C>, where: •V is a set of variables Vi •D is a set of variable domains, • i is denoted Di •C is a set of constraints on assignments to V • values. Example: • • A CSP Solution: is any assignment to V, such that all constraints in C are satisfied. The domain of variable V Each constraint specifies a set of allowed variable A,B in {1,2} C = {{<1,2><2,1>}}