$4$ colers

Part $3.$ Constraint Satisfaction Problems $(50$pts$)$

Consider the following coloring problem: Each rectangle must be painted Green, Red or Blue. Two

neighboring rectangles cannot be painted in the same color. In choosing an evaluation sequence for

the depth$-$first search in a constraint satisfaction problem, three heuristics are often useful: LRV $($least

remaining values$),$ MCV $($most constraining variable$),$ and LCV $($least constraining value$).$

$($a$)$ According to the LRV$,$ MCV$,$ and LCV heuristics, which region should be colored first, and why?

$(20$pts$)$

$($b$)$ Suppose B has already been colored red, all others are not colored yet. Would it make more sense

to color A$,$ D or E next? Why? $(20$pts$)$