Thread: 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,

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;
    }
}

Can you post what the correct output from the program should be?

Can you ask specific questions about what problems you are having?

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.

What is this program's output?

Do you have an algorithm for solving this problem? Can you post it?

What does the current program do when you execute it?

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?