Assignment $3$

Written Assignment: Constraint Satisfaction Problem

The problem is to color the sections such that no two sections sharing a border have the same color. You are allowed to use the colors $($Red$,$ Green. Blue$).$

TASK $1(10$ points$)$

Draw the constraint graph for this problem..

TASK $2(30$ points$)$

Assuming you are using Backtracking search to solve this problem and that you are using MRV with degree heuristic to select the variable, which variable will be selected at each level of the search tree $[$You do not need to draw the tree. Just let me know which variable will be selected and why $($MRV and degree values$)].$ Note: Multiple possible correct answers. You only must give one.

TASK $3(30$ points$)$

Assume you assign the color 'Red' to the first variable selected in part b$.$ Show the steps involved in checking the remaining legal values for all other variables using Arc Consistency.

TASK $4(10$ points$)$

Can you use the structure of the problem to make solving it more efficient?

TASK $5(20$ points$)$

Give one valid solution to this problem. $($You just must give the solution. No need to give all the steps$).$