Map Coloring Problem
6.10 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.
