Color the map shown below using four colors in such a way that no two bordering countries have the same color. (One possible coloring is shown.) Use depth-first search.
One way to do this is to treat each state in the state space as a partial coloring of the map so that each extension of a path consists of coloring one additional country. To keep the branching factor down, assume that the countries are colored in alphabetical order. Another way is to treat each state as a complete coloring of the map but not necessarily correct (unless it's a goal state). In this case each extension of a path consists of changing the color of a single country.
Because you are not doing heuristic search, you will not need to write
the estimate procedure.
Ideally your program should apply to any map, not just the one shown above, but if you find this too difficult, write it so that it works for the map shown.
The Eights Puzzle consists of a square with nine cells. All cells but one contain a square with a number on it. Squares adjacent to the empty cell can be moved into it. The goal is to arrange the numbers in sequential order from left to right and top to bottom:
1 2 3 4 _ 5 6 7 8Use A* search to solve the Eights Puzzle. Start from an initial state which is relatively close to the goal state so the search will not take too long.
