You are given a 2x3 grid (two rows 0,1 and three columns 0,1,2). You need to paint each cell so that each cell is painted differently from the cells it shares an edge with. You can use only three colors: Blue Red and Green. Also you are told that the middle-bottom cell should be Green and the middle-top one should be Blue.

1. (a) [10 points] First represent this problem as a CSP, as in Q1. Then, build the corresponding constraint network (you can use AIspace for this sub-question and any of the others related to Arc Consistency below)
2. (b) [25 points]
3. (i) [5pt] Apply the arc consistency (AC) algorithm to the network and show its outcome. You will see that AC alone cannot find a solution. Explain why.
4. (ii) [5+5 pt] Verify if DFS-with-pruning applied to the output of AC in (i) can find a solution. Show your work using the simplified notation for states that was used in the lecture slides to show examples of DFP with pruning
5. (iii) [5+5 pt] Verify if arc consistency with domain splitting can be used to find a solution. How many domain splits were needed to answer this question?
6. (c) [2+8 = 10 points] Assume you are given the additional constraint that the cells in the top- right and bottom-left corners must be painted in the same color. Would AC find a solution to this more constrained problem, and why or why not? Reuse as much as possible the work you have done to answer the previous question, and show the additional steps of AC that are needed to get your answer. For each step, mention which value is pruned from which variable, due to which arc, eg.

Value removed from Variable via arc