4 Constraint Satisfaction (15 pts) You are trying to solve the N-Queens problem for a 5x5 board. The variables are the columns of the board. The domains of the variables are 1-5, which represent the rows of the board. For example, assigning variable C3 to 5 is the equivalent of putting a queen in the third column and fifth row. C1 C2 C3 C4 C5 1 2 3 4 5 4.1 Forward Checking (3 pts) Cross out all the values that would be eliminated by Forward Checking after variable Cl has been assigned to 1. C1: 1 C2: C3: C1: C5: 4.2 Minimum Remaining Values Heuristic (4 pts) Consider the assignment below. C3 has been assigned and constraint propagation has been done. List all unassigned variables that might be selected by the minimum remaining values (MRV) heuristic: C1: 1,3,5 C2: 1, 2 C3: 1 C1: 1, 2 C5: 1, 3, 5 4.3 Arc Consistency (4 pts) C1 and C3 have been assigned and the domains of C2, C4, and C5 still are 1, 2, 3, 4, and 5. Write down all the domain of all variables after performing are consistency. C1: 1 C2: C3: 5 C4: C5: 4.4 Min-Conflicts Heuristic (4 pts) Suppose you are performing local search on this complete but inconsistent assignment. What new value would be chosen for C3 by the min-conflicts heuristic? C1: 5 C2: 3 C3: 1 C4: 5 C5: 2 4 4 Constraint Satisfaction (15 pts) You are trying to solve the N-Queens problem for a 5x5 board. The variables are the columns of the board. The domains of the variables are 1-5, which represent the rows of the board. For example, assigning variable C3 to 5 is the equivalent of putting a queen in the third column and fifth row. C1 C2 C3 C4 C5 1 2 3 4 5 4.1 Forward Checking (3 pts) Cross out all the values that would be eliminated by Forward Checking after variable Cl has been assigned to 1. C1: 1 C2: C3: C1: C5: 4.2 Minimum Remaining Values Heuristic (4 pts) Consider the assignment below. C3 has been assigned and constraint propagation has been done. List all unassigned variables that might be selected by the minimum remaining values (MRV) heuristic: C1: 1,3,5 C2: 1, 2 C3: 1 C1: 1, 2 C5: 1, 3, 5 4.3 Arc Consistency (4 pts) C1 and C3 have been assigned and the domains of C2, C4, and C5 still are 1, 2, 3, 4, and 5. Write down all the domain of all variables after performing are consistency. C1: 1 C2: C3: 5 C4: C5: 4.4 Min-Conflicts Heuristic (4 pts) Suppose you are performing local search on this complete but inconsistent assignment. What new value would be chosen for C3 by the min-conflicts heuristic? C1: 5 C2: 3 C3: 1 C4: 5 C5: 2 4