Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 16 of 16

Thread: Four color theorem help

  1. #1
    Junior Member
    Join Date
    Nov 2013
    Location
    Morgantown
    Posts
    19
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default 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;
        }
    }
    Last edited by fpritt24; February 19th, 2014 at 03:11 PM. Reason: Reworked my code for better readability


  2. #2
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    4,509
    My Mood
    Mellow
    Thanks
    155
    Thanked 613 Times in 600 Posts

    Default 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.

  3. #3
    Junior Member
    Join Date
    Nov 2013
    Location
    Morgantown
    Posts
    19
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Four color theorem help

    I have modified it if you would like to provide help now

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,067
    Thanks
    47
    Thanked 2,146 Times in 2,119 Posts

    Default Re: Four color theorem help

    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.
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Junior Member
    Join Date
    Nov 2013
    Location
    Morgantown
    Posts
    19
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default 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.

  6. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,067
    Thanks
    47
    Thanked 2,146 Times in 2,119 Posts

    Default Re: Four color theorem help

    What is this program's output?
    If you don't understand my answer, don't ignore it, ask a question.

  7. #7
    Junior Member
    Join Date
    Nov 2013
    Location
    Morgantown
    Posts
    19
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default 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)

  8. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,067
    Thanks
    47
    Thanked 2,146 Times in 2,119 Posts

    Default 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?
    If you don't understand my answer, don't ignore it, ask a question.

  9. #9
    Junior Member
    Join Date
    Nov 2013
    Location
    Morgantown
    Posts
    19
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Four color theorem help

    I don't currently have an algorithm. That is what I need help with figuring out.

  10. #10
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,067
    Thanks
    47
    Thanked 2,146 Times in 2,119 Posts

    Default 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?
    If you don't understand my answer, don't ignore it, ask a question.

  11. #11
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    4,509
    My Mood
    Mellow
    Thanks
    155
    Thanked 613 Times in 600 Posts

    Default 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?

  12. #12
    Junior Member
    Join Date
    Nov 2013
    Location
    Morgantown
    Posts
    19
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Four color theorem help

    Quote Originally Posted by GregBrannon View Post
    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 View Post
    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.

  13. #13
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    4,509
    My Mood
    Mellow
    Thanks
    155
    Thanked 613 Times in 600 Posts

    Default 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.

  14. #14
    Junior Member
    Join Date
    Nov 2013
    Location
    Morgantown
    Posts
    19
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default 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.

  15. #15
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    4,509
    My Mood
    Mellow
    Thanks
    155
    Thanked 613 Times in 600 Posts

    Default 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.

  16. #16
    Junior Member
    Join Date
    Nov 2013
    Location
    Morgantown
    Posts
    19
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Four color theorem help

    It is too advanced and they won't understand that or help anyone.. lol

Similar Threads

  1. [SOLVED] background color
    By keepStriving in forum AWT / Java Swing
    Replies: 4
    Last Post: December 3rd, 2013, 04:33 PM
  2. Replies: 6
    Last Post: September 15th, 2013, 07:18 PM
  3. Why does the Color class have two variables for each color?
    By Melawe in forum Java Theory & Questions
    Replies: 5
    Last Post: May 10th, 2012, 04:21 PM
  4. text color changer based on words/ word classification by color
    By knoxy5467 in forum Java Theory & Questions
    Replies: 25
    Last Post: June 15th, 2011, 07:52 AM
  5. Color Problem
    By aussiemcgr in forum Java Theory & Questions
    Replies: 5
    Last Post: July 12th, 2010, 03:53 PM