java for loop fix ?

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

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("\nEnter 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 < items.length; 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 <= ORANGE; i++)

{

if (explore(region + 1, i)) return true;

}

return false;

}

static boolean safeToColor(int region, int color)

{

for (int i = 0; i < adjacency.length; 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 < regionColors.length; 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:

1,4,2,5

0,4,6,5

0,4,3,6,5

2,4,6

0,1,6,3,2

2,6,1,0

2,3,4,1,5

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

1 Reply

Know the answer? Post it — somebody with the same question will find it here.

Vulpes12y ago
Accepted 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("\nEnter 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 < items.length; 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 <= ORANGE; i++)
{
if (explore(region + 1, i)) return true;
}
}

return false;
}

static boolean safeToColor(int region, int color)
{
for (int i = 0; i < adjacency.length; 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 < regionColors.length; 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:

1,4,2,5
0,4,6,5
0,4,3,6,5
2,4,6
0,1,6,3,2
2,6,1,0
2,3,4,1,5

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