CONSTRAINT SATISFACTION PROBLEM

b) We discussed a map-coloring problem as a constraint satisfaction problem in the class. This task considers the same problem for a different map as shown below. Each region must be colored in red, green or blue. There are two constraints. First, we need to color the map such that two adjacent regions always have different colors. Second, we are also required to color region C with blue. B F D E a. Formulate the above map-coloring problem as a constraint satisfaction problem. (i.e., state variables, domain and constraints) b. Given the map above, draw the constraint graph by adding edges between states. (0.5 point) c. Solve the above problem using minimum remaining values (MRV) variable ordering. Break ties using alphanumerical ordering (A comes before Z). (1.5 points) d. On the table below, cross out values that violate arc-consistency by running the algorithm AC-3. The unary constraint on C is already applied for you. Show each required step when you process AC-3 Algorithm (check the lectures to draw arc and remove values when it violates arc-consistency) (2 points) B CDEF Red Green Blue