Recursive algorithm for the four-color theorem

Question

The problem is to take a map divided into regions, as shown in the adjacency matrix and using four colors, color the map so that no two adjacent regions have the same color. We will use the adjacency matrix to encode which region borders on another region. Columns and rows of the matrix are areas, while cells contain 0 if two areas are not adjacent, and 1 if they are borders. Create a recursive inverse tracking solution that takes as an interactive input from the user the number of areas on the map and the name of the adjacency matrix file expressing the map layout.

The problem I am facing is that the first value in countryColor is changed, but many of the values ​​in the array never change.

private static final int[] color = {1,2,3,4}; //this color array is meant to represent 4 colors like red, blue, green, orange etc. private static int[][] map = {{0,1,1,0,1,1,0},{1,0,0,1,1,0,1},{1,0,0,1,1,1,0},{0,1,1,0,1,0,1},{1,1,1,1,0,0,0},{1,0,1,0,0,0,1},{0,1,0,1,0,1,0}}; //this is the adjacency matrix showing which countries are next to each other private static int[] countryColor = new int[7]; //this is the array that holds the color values for each country private static boolean colorMap(int country ){ System.out.println("Checking Country "+ country); boolean check; for(int j= 0;j< countryColor.length; j++){ if(useColor(country,color[j]) == true) countryColor[country] = color[j]; if(country == countryColor.length-1) return true; check = colorMap(country+1); System.out.println(check); if(check == true) return true; countryColor[country]=0; } return false; } private static boolean useColor(int country, int color){ for(int i = 0; i < map.length;i++){ if(map[country][i] == 1&& countryColor[i]==color){ System.out.println("Nah country " + country +" cant be "+color ); return false; } } return true; } 

Answer 1

Your problem is that if useColor returns as false, it does not set the color for the current country, but it still tries to recursively color the rest of the map. As an example, we first try to color the first country (country 0) with color 1, which will be successful. Then we try to color country 1 with color 1, which does not work, because it is adjacent to country 0, which already has this color. Then it tries to recursively color the rest, and if it succeeds, we return true. What you should do is if the current color does not work, then you must continue the next iteration of the loop, sifting through another color, before recursively coloring the rest.

In particular, you must change

 if(useColor(country,color[j]) == true) countryColor[country] = color[j]; 

to

 if(useColor(country,color[j]) == true) countryColor[country] = color[j]; else continue; //this will try and color the current country with another color