Consider the 4-queen problem of placing four queens on a 4x4 chessboard so no queens attacks...

Transcribed Image Text:

Consider the 4-queen problem of placing four queens on a 4x4 chessboard so no queens attacks another one, horizontally, vertically, or diagonally. We formalize the problem as a CSP as follows: We use one variable per queen, Q1, Q2, Q3, Q4, where queen i is put in column i at row Qi. We use binary constraints between each pair of queens. We use the initial domains of D1 = {3}, D2 = {1, 2, 3, 4}, D3 = {1, 2, 3, 4), and D4 = {1, 2, 3, 4), for Q1, Q2, Q3, and Q4, respectively. (a) Draw the constraint graph of the 4-queen problem. (b) Give the domains for Q2, Q3, and Q4 after applying Forward Checking. (c) Apply the Arc Consistency algorithm, AC3, on the initial domains (not after forward checking). Show your work in the table by providing the resulting domains after each arc X Y you checked. Specify the arc in the left column and use as many rows as needed. Initial domains After checking: After checking: After checking: After checking: After checking: After checking: After checking: > > > Q {3} Q2 Q3 Q4 {1,2,3,4} {1,2,3,4} {1,2,3,4} (d) Suppose arc-consistency has been done (previous step). List all the unassigned variables that might be selected by the Minimum Remaining Value heuristic. Consider the 4-queen problem of placing four queens on a 4x4 chessboard so no queens attacks another one, horizontally, vertically, or diagonally. We formalize the problem as a CSP as follows: We use one variable per queen, Q1, Q2, Q3, Q4, where queen i is put in column i at row Qi. We use binary constraints between each pair of queens. We use the initial domains of D1 = {3}, D2 = {1, 2, 3, 4}, D3 = {1, 2, 3, 4), and D4 = {1, 2, 3, 4), for Q1, Q2, Q3, and Q4, respectively. (a) Draw the constraint graph of the 4-queen problem. (b) Give the domains for Q2, Q3, and Q4 after applying Forward Checking. (c) Apply the Arc Consistency algorithm, AC3, on the initial domains (not after forward checking). Show your work in the table by providing the resulting domains after each arc X Y you checked. Specify the arc in the left column and use as many rows as needed. Initial domains After checking: After checking: After checking: After checking: After checking: After checking: After checking: > > > Q {3} Q2 Q3 Q4 {1,2,3,4} {1,2,3,4} {1,2,3,4} (d) Suppose arc-consistency has been done (previous step). List all the unassigned variables that might be selected by the Minimum Remaining Value heuristic.

Answer rating: 100% (QA)

Solutions Step 1 To find the solution to the 4 Queens Problem one must place four queens on a chessboard that measures 44 the queens cannot attack each other In other words in this problem no two quee... View the full answer