java for loop fix ?

Question

Hi

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 do not share the same color. The task is to ask the user how many regions they have an express the regions into an adjacency matrix. Say 100 by 100 but probably won't have more then say 8 regions. Using four colors say Region A== Color red Region B == color blue Region C == color green Region D == color orange. Use an adjacency matrix to encode which region borders on which other region.

-------------------------------So my columns and rows of my matrix are my regions, while the cells should contain a 0 (zero) if the two regions are not adjacent. And a 1 (one) if they border one another. My solution will need a recursive backtracking solution which takes in an input from the user on the number of regions in the map and the filename of the adjacency matrix expressing the maps makeup.

I'm really lost on how to start here. I know I need to have something along int [][] adj; int num Regions; int [] colmns; System.out.print("Enter in the number of regions" + regions); // import the file from the user, // FROM here I assume loop the borders and figure out which are adjacent and which aren't , // from there assign a color to that region, // from that region determine the number of regions around it and assign them colors so that no same colors are touching one another, // then move on from there till the map is filled and no regions of the same color are touching//, //return the regions with their assigned color

If someone could help me here I would really appreciate it. Not to sure of my algorithm here in order to fo this. I was thinking maybe a for loop somehow to solve this something like

for (i=0; i<node.count; i++)
{
.... int node = (i + start.node+1) % node.count;
.... [test for uncolored with colored neighbors, etc.]
}

// coding in java- using emacs and terminal etc.

Any help would be highly appreciated.

Don't think the task at hand is super complicated, I'm just not that experienced in this.

Thank again for any future help.

Vulpes · Answer

An interesting though not particularly easy question but I've done something here: /* It's assumed that the file has one line for each region starting from region 0. Each line contains the numbers of those regions to which the region in question is adjacent separated by commas. */ import java.io.*; import java.util.*; public class FourColor { static final int NONE = 0; static final int RED = 1; static final int BLUE = 2; static final int GREEN = 3; static final int ORANGE = 4; static int[] regionColors; static int[][] adjacency; static Scanner scanner = new Scanner (System.in); public static void main (String[]args) throws IOException { System.out.print(Enter number of regions : ); int numRegions = scanner.nextInt(); System.out.print(
Enter name of file : ); String fileName = scanner.next(); regionColors = new int[numRegions]; // all NONE by default adjacency = new int[numRegions][numRegions]; // all 0 by default fillAdjacencyMatrix(numRegions fileName); boolean result = explore(0 RED); System.out.println(); if (result) System.out.println(All regions colored successfully); else System.out.println(Something went wrong!); System.out.println(); printRegionColors(); } static void fillAdjacencyMatrix(int numRegions String fileName) throws IOException { FileInputStream in = new FileInputStream(fileName); BufferedReader br = new BufferedReader(new InputStreamReader(in)); String line; try { int region = 0; while((line = br.readLine()) != null) { String[] items = line.split(); for(int i = 0; i { int region2 = Integer.parseInt(items[i]); adjacency[region][region2] = 1; } region++; } } catch(IOException e) { System.out.println(e); return; } finally { br.close(); in.close(); } } static boolean explore(int region int color) { if (region >= adjacency.length) return true; if (safeToColor(region color)) { regionColors[region] = color; for (int i = RED; i { if (explore(region + 1 i)) return true; } } return false; } static boolean safeToColor(int region int color) { for (int i = 0; i { if (adjacency[region][i] == 0) continue; int adjRegion = i; if (regionColors[adjRegion] == color) { return false; } } return true; } static void printRegionColors() { for(int i = 0; i { System.out.print(Region  + i +  is ); switch (regionColors[i]) { case NONE: System.out.println(none); break; case RED: System.out.println(red); break; case BLUE: System.out.println(blue); break; case GREEN: System.out.println(green); break; case ORANGE: System.out.println(orange); break; } } } } I tested it using this sample file regions.txt with 7 regions: 1425 0465 04365 246 01632 2610 23415 The output which I know to be correct is: Region 0 is red Region 1 is blue Region 2 is blue Region 3 is red Region 4 is green Region 5 is green Region 6 is orange