Map-Coloring Problem

Name of book: [Main] Artificial Intelligence A Modern Approach
Exercise 6.10 page 251
Generate random instances of map-coloring problems as follows: scatter n points on the unit square; select a point X at random, connect X by a straight line to the nearest point Y such that X is not already connected to Y and the line crosses no other line; repeat the previous step until no more connections are possible. The points represent regions on the map and the lines connect neighbors. Now try to find k-colorings of each map, for both k = 3 and k = 4, using min-conflicts, backtracking, backtracking with forward checking, and backtracking with MAC. Construct a table of average run times for each algorithm for values of n up to the largest you can manage. Comment on your results.

Notes:
• Each point represents a country.
• An edge between two points represents a border between two countries, i.e., the two points should have different colors.
• This type of graph, no crossings, is called Planar Graph.
• By the Four Color Theorem, every planar graph is four-colorable.
• It is fairly easy to determine whether a graph is 2-colorable or not.
• To determine whether a graph is 3-colorable is NP-complete.
• The objective of this exrcise to try to see if you can solve with 3 colors using CSP.

Essay Mill