Engineering Homework Help

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.