# Four color theorem help

• February 18th, 2014, 11:49 PM
fpritt24
Four color theorem help
Okay so I'm a beginner to java programming, only in my second class on it, and we were assigned the four color theorem problem. The four color theorem states that for any region, 4 colors should be able to color it without 2 regions of the same color touching.
The actual problem statement is:
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 an interactive input from the user the number of regions in the map and the filename of the adjacency matrix expressing the maps makeup.

The file I am reading from looks like this:
0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0

The output should look like this.
1
2
3
2

I am completely stuck now with what to do. I feel as though most of my code is wrong but I don't know where, how, or what to fix right now.

Here's my code,
Code :

```import java.util.Scanner; import java.io.FileReader; import java.io.FileNotFoundException;   public class ColorCoding { static int[][] adj; static int[] colors; static int numRegions; public static void main(String[] args) throws FileNotFoundException { Scanner input = new Scanner(System.in); Scanner inputFile = new Scanner(new FileReader("test.txt")); System.out.println("Enter the size of the region."); numRegions = input.nextInt();   int region = 0; int color = 1; colors = new int[numRegions];   adj = new int[numRegions][numRegions]; //Initialize for(int i = 0;i < adj.length;i++) for(int j = 0;j < adj.length;j++) adj[i][j] = inputFile.nextInt();   printRegion();   for(int i = 0;i < numRegions;i++) colors[i] = 0;   if(move(0,0)) { System.out.println("The regions and colors are:"); for(int i = 0;i < numRegions;i++) { switch(colors[i]) { case 1: System.out.println(i + " is Red"); break; case 2: System.out.println(i + " is Green"); break; case 3: System.out.println(i + " is Yellow"); break; case 4: System.out.println(i + " is Blue"); break; } } } else System.out.println("Wrong");   printRegion(); }   /**prints the region Pre-Cond: adj[][] is a valid matrix Post-Cond: none @param none @return void*/ public static void printRegion() { for(int i = 0;i < adj.length;i++) { for(int j = 0;j < adj.length;j++) System.out.print(adj[i][j] + " "); System.out.println(); } }   /**determines if the given coordinates are in the region Pre-Cond: r,c valid integers between 0 and number of regions Post-Cond: none @param integers r and c @return boolean true if in region, false otherwise*/ public static boolean inRegion(int r, int c) { return (r >= 0 && r < numRegions && c >= 0 && c < numRegions); }   /** determines if adjacent regions are the same color Pre-Cond: r and c are valid integers between 0 and numRegions Post-Cond: boolean true or false @param r and c are rows and columns of adj matrix @return boolean if the two match*/ public static boolean checkColor(int r,int c,int nr, int nc) { if(adj[r][c] == adj[nr][nc]) return true; else return false; }   /** recursive backtracking function to color map Pre-Cond: r and c are valid integers between 0 and numRegions Post-Cond: boolean true or false @param r and c are rows and columns of adj matrix @return boolean if the color was successful*/ public static boolean move(int r,int c) { int i; int nr = 0; int nc = 0;   //Record first move adj[r][c] = colors[1];     for(i = 0;i < 4;i++) { switch(i) { case 0: { nr = r; nc = c + 1; if(checkColor(r,c,nr,nc)) break; } case 1: { nr = r + 1; nc = c; if(checkColor(r,c,nr,nc)) break; } case 2: { nr = r; nc = c - 1; if(checkColor(r,c,nr,nc)) break; } case 3: { nr = r - 1; nc = c; if(checkColor(r,c,nr,nc)) break; } } if(move(nr,nc)) return true; } adj[r][c] = 0; return false; } }```
• February 19th, 2014, 04:55 AM
GregBrannon
Re: Four color theorem help
The use of expletives is not in keeping with the forum's requirement for the use of professional language. Please repost without expletives when you can.

Also, please give a better explanation of what you need help with. Not everyone may be aware of the "Four Color Theorem," and nobody will likely know what you need help with.
• February 19th, 2014, 02:00 PM
fpritt24
Re: Four color theorem help
I have modified it if you would like to provide help now
• February 19th, 2014, 02:49 PM
Norm
Re: Four color theorem help
Can you post what the correct output from the program should be?

What steps does the code need to take to solve the problem?
Which of those steps does the posted code take?

BTW The code needs to be properly formatted so it is easier to read and understand. The indentations are terrible.
• February 19th, 2014, 03:12 PM
fpritt24
Re: Four color theorem help
Yes, sorry I was in the middle of the rewrite when you posted. I have rewrote some code, asked the question better, and properly formatted. I was really tired last night and frustrated when I originally posted.
• February 19th, 2014, 03:21 PM
Norm
Re: Four color theorem help
What is this program's output?
• February 19th, 2014, 03:29 PM
fpritt24
Re: Four color theorem help
It should be the colors of the regions. Like if there are 4 regions, then the regions are A,B,C,D and the 1,2,3,4 are the different colors of the regions.
The output should be better formatted to this:
Region Color
A ------- 1
B ------- 2
C ------- 3
D ------- 2
(Ignore the - I just put it so it would be better formatted)
• February 19th, 2014, 03:39 PM
Norm
Re: Four color theorem help
Do you have an algorithm for solving this problem? Can you post it?

What does the current program do when you execute it?
• February 19th, 2014, 03:41 PM
fpritt24
Re: Four color theorem help
I don't currently have an algorithm. That is what I need help with figuring out.
• February 19th, 2014, 03:53 PM
Norm
Re: Four color theorem help
Seems a waste of time to have written all that code if you have no idea how it was supposed to solve the problem.

What have you found searching on the internet?
• February 19th, 2014, 03:55 PM
GregBrannon
Re: Four color theorem help
Sorry to be so dense, but I'm just now figuring out the adjacency matrix, I think. For the one you posted:

0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0

Is it correct that there are 4 regions and each row shows the adjacency of one region to the others. For example, the first row is region A, and the row:

0 1 1 1

says that A is not adjacent to itself (notice the major diagonal - a region's adjacency to itself - is all zeros) but is adjacent to B, C, and D.

The B row:

1 0 1 0

says B is adjacent to A and C.

Do I understand the adjacency matrix correctly?
• February 19th, 2014, 03:58 PM
fpritt24
Re: Four color theorem help
Quote:

Originally Posted by GregBrannon
Sorry to be so dense, but I'm just now figuring out the adjacency matrix, I think. For the one you posted:

0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0

Is it correct that there are 4 regions and each row shows the adjacency of one region to the others. For example, the first row is region A, and the row:

0 1 1 1

says that A is not adjacent to itself (notice the major diagonal - a region's adjacency to itself - is all zeros) but is adjacent to B, C, and D.

The B row:

1 0 1 0

says B is adjacent to A and C.

Do I understand the adjacency matrix correctly?

Yes that is perfect.

--- Update ---

Quote:

Originally Posted by Norm
Seems a waste of time to have written all that code if you have no idea how it was supposed to solve the problem.

What have you found searching on the internet?

Haven't found a thing. And I have this code written because it was supposed to be due today so I had to write something to get some credit but since nobody understands, they have post-poned it until Friday.
• February 19th, 2014, 04:15 PM
GregBrannon
Re: Four color theorem help
A brute force method would be to assign every region a color (represented by a number, letter, something easy) and then determine if the colors assigned satisfy the adjacency matrix. I don't know if it would be better to start with a random color assignment or with all regions assigned the same color. I'm leaning toward all being the same color as a starting point.

Initial assignment:

Colors: W, X, Y, Z

A - W
B - W
C - W
D - W

But according to the adjacency matrix, A is adjacent to B, C, and D, so B, C, and D cannot be the same color as A. New assignment:

A - W
B - X
C - X
D - X

That satisfies the first row of the adjacency matrix. Now for the second row, B is adjacent to A and C. A and B are already satisfied, but B and C cannot be the same color, so new assignment:

A - W
B - X
C - Y
D - X

Third row: C's adjacency to A and B is already taken care of, but C is also adjacent to D, so C and D cannot be the same color, and they aren't. The third row is satisfied.

Fourth row: D is adjacent to A and C, and the colors are already different.

The adjacency matrix has been satisfied with 3 colors.

Now you have an algorithm. Program it.
• February 19th, 2014, 04:35 PM
fpritt24
Re: Four color theorem help
I don't know how to start to program that though. I am a beginner and do not know what to do to start.
• February 19th, 2014, 04:48 PM
GregBrannon
Re: Four color theorem help
We can only push you in a direction, hopefully a useful one. As I've completely outlined a solution approach, I'm not sure what else to do. "I don't know where/how to start," is one of the hardest complaints to help someone with, because it indicates they are lacking the necessary basics and/or the confidence to apply them. Both of those deficiencies can be fortified with practice.

Since the whole class is uncertain how to program a solution, and the due date had to be extended, perhaps this problem is a bit too advanced for your class' current skill and experience level.
• February 19th, 2014, 05:04 PM
fpritt24
Re: Four color theorem help
It is too advanced and they won't understand that or help anyone.. lol