The four-color theorem states that any map in a plane can be colored using four-colors in such a way that regions sharing a common boundary (other than a single point) do not share the same color. This problem is sometimes also called Guthrie's problem after F. Guthrie, who first conjectured the theorem in 1852.
The problem at hand is to take a map separated into regions as expressed in an adjacency matrix and using four colors, color the map such that no two contiguous regions share the same color. We will use an adjacency matrix to encode which region borders on which other region. The columns and rows of the matrix are the regions while the cells contain a 0 if the two regions are not adjacent and a 1 if they border. Create a recursive backtracking solution which accepts as interactive input from the user the number of regions in the map and the filename of the adjacency matrix expressing the maps makeup. Your output should be similar to
Region Color
A red
B Green
C yellow
D Blue
Or whatever four colors you choose (and if you want you could have the user choose the four colors but that it not mandatory).
Consider the following map with four regions:
Its adjacency matrix would be
|
|
A
|
B
|
C
|
D
|
|
A
|
0
|
1
|
0
|
1
|
|
B
|
1
|
0
|
1
|
0
|
|
C
|
0
|
1
|
0
|
1
|
|
D
|
1
|
0
|
1
|
0
|
Consider the following map of central Europe with 9 regions:
The solution to these maps do not require backtracking
Consider this final map with 6 regions it will require backtracking
While these three maps will not fully test your solution they will be a start. Nithin and Billy will be creating a map(s) to test your program when you turn it in. You are to write module specifications (JavaDoc) all methods in the class except main. In addition to turning in a gnulist printout, you are also to email your class to your lab instructor (and only your lab instructor). Use the subject line.