Encodings Are Essential: 4 Queens 4 Queens Problem Place 4 queens on a 4x4 隧 chessboard so that no queen can attack another Q How big is the encoding? Variables Chessboard positio D ns omain Queen 1-4 or blank Constraints Two positions on a line(vertical horizontal, diagonal)cannot both be Q Encodings Are Essential: 4 Queens Place queens so that no queen can attack another Q What is a better formulation? 123 Assume one queen per column Determine what row each queen should be in Variables Q1, Q2, Q3, Q4 Domains 1, 2, 3, 41 Constraints Q<> On different rows Q-Q1|<>|jl Stay off the diagonals EXample:C12={(1,3)(1,4)(2,4)(3,1)(4,1)(4,2)}5 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 big is the encoding? Q Q Q 6 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. What is a better formulation? Q Q Q • Assume one queen per column. • Determine what row each queen should be in. |Qi - Qj Stay off the diagonals Example: C1,2 Encodings Are Essential: 4 Queens | <> |i-j| = {(1,3) (1,4) (2,4) (3,1) (4,1) (4,2)}