Question: Let's get back to basics with some good old Map Coloring. As a refresher, in the Map Coloring problem, the goal is to assign
Let's get back to basics with some good old Map Coloring. As a refresher, in the Map Coloring problem, the goal is to assign one of k colors to variables in some geographically connected setting such that no two adjacent variables share the same color. Suppose we have the following constraint graph associated with a Map Coloring problem in which edges denote adjacency between variables, and we have k = 3 colors to work with: D = {red, green, blue} A B C D E F G 3.1. Suppose, during backtracking, we begin by assigning {E = red, F = blue} and are performing forward checking. Which variable would be wise to assign to next, and why? 3.2. Suppose, during backtracking with forward checking, we begin by assigning {A = green, F = blue} and have decided to assign to B next. At this point, the domain of B will have been reduced to DB = {blue, red} from forward checking; which of these values would we be wise to try assigning to B next, and why?
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
