Computer Science HW ( java)

CS 111 Introduction to Data Structures 

Outside Programming Assignment I 

Due:  Sept. 23, 2014 AT THE START OF CLASS 

 

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  

CS111-Olab1-Sec? “yourMasterID”.