Hi.

I need to solve a problem, and i'm stuck and don't know what else to do.

Thats why i'm asking here for help.

I need to color the states of the U.S.A. so that adjecent states are not the same color. I tried every way that i can think of but it's not working.

Thanks in advance,

Ronel

Herre is the code:
If you need the source code in files drop me an email and i will send it to you.

import java.io.*;
import java.util.*;

public class CSP {
	
		
	public static void main(String [ ] args) throws IOException {
		
		long t1 = System.currentTimeMillis();
		Calendar cal = new GregorianCalendar();
	
		// Get the components of the time
		int hour = cal.get(Calendar.HOUR_OF_DAY);
		int min = cal.get(Calendar.MINUTE);             // 0..59
		int sec = cal.get(Calendar.SECOND);             // 0..59
		
		System.out.print("\n Started at "+hour+":"+min+":"+sec+"... ");

		MyMapGraph america = new MyMapGraph();
		
		long t2 = System.currentTimeMillis();
		System.out.println("Finished after "+(t2-t1)/1000+" seconds. ("+(t2-t1)+"ms.)");
		
		america.colorGraph();
		
		System.out.println(america.displayGraph());
	}
}

import java.awt.List;
import java.util.ArrayList;
import java.util.Random;



public class MyMapGraph extends MapGraph
{
	
	public void colorGraph()
	{
			borders();
			
					//assign random colors to the states
					for(int i = 0; i < states.length; i++)
					{
					Double r;
					Random generator = new Random();
					
					String color;
					r = generator.nextDouble();
					if (r < 0.25) {color = "red";} else if (r < 0.50 && r > 0.25) {color = "green";}
					else if (r < 0.75 && r > 0.50) {color = "blue";} else {color = "yellow";};
					
					color(states[i], color);
					}
						
					//while 2 adjecent  states are the same color 
					//pick a random color for one of them
					for(int i = 0; i < state1.size();i++)  
					{
						while(isSameColor(state1.get(i), state2.get(i)))
						{
							Double r;
							Random generator = new Random();
							
							String color;
							r = generator.nextDouble();
							if (r < 0.25) {color = "red";} else if (r < 0.50 && r > 0.25) {color = "green";}
							else if (r < 0.75 && r > 0.50) {color = "blue";} else {color = "yellow";};
							
							color(state1.get(i),color);

						}
					}				
	}	
}

import java.util.List;
import java.util.ArrayList;
import java.util.Random;

public abstract class MapGraph {

	public MapNode[] states;
	
	public List<MapNode> state1 = new ArrayList<MapNode>();
	public List<MapNode> state2 = new ArrayList<MapNode>();
	
	
	public MapGraph() {
		
		this.states = new MapNode[47];
		
		this.states[0] = new MapNode("OR", 4, "WA", "ID", "NV", "CA");
		
		this.states[1] = new MapNode("WA", 2, "OR", "ID");
		
		this.states[2] = new MapNode("CA", 3, "OR", "NV", "AZ");
		this.states[3] = new MapNode("ID", 6, "WA", "OR", "NV", "UT", "WY", "MT");
		this.states[4] = new MapNode("NV", 5, "ID", "OR", "CA", "AZ", "UT");
		this.states[5] = new MapNode("UT", 5, "NV", "ID", "WY", "CO", "AZ");
		this.states[6] = new MapNode("AZ", 4, "UT", "NV", "CA", "NM");
		
		this.states[7] = new MapNode("MT", 4, "ID", "WY", "SD", "ND");
		this.states[8] = new MapNode("WY", 6, "MT", "ID", "UT", "CO", "NE", "SD");
		this.states[9] = new MapNode("CO", 6, "WY", "UT", "NM", "OK", "KS", "NE");
		this.states[10] = new MapNode("NM", 4, "CO", "AZ", "TX", "OK");
		this.states[11] = new MapNode("TX", 4, "NM", "OK", "AR", "LA");
		this.states[12] = new MapNode("ND", 3, "MT", "SD", "MN");
		this.states[13] = new MapNode("SD", 6, "ND", "MT", "WY", "NE", "IA", "MN");
		
		this.states[14] = new MapNode("NE", 6, "SD", "WY", "CO", "KS", "MO", "IA");
		this.states[15] = new MapNode("KS", 4, "NE", "CO", "OK", "MO");
		this.states[16] = new MapNode("OK", 6, "KS", "CO", "NM", "TX", "AR", "MO");
		this.states[17] = new MapNode("MN", 4, "WI", "IA", "SD", "ND");
		this.states[18] = new MapNode("IA", 6, "MN", "SD", "NE", "MO", "IL", "WI");
		this.states[19] = new MapNode("MO", 7, "IA", "NE", "KS", "OK", "AR", "KY", "IL");
		this.states[20] = new MapNode("AR", 6, "MO", "OK", "TX", "LA", "MS", "TN");
		
		this.states[21] = new MapNode("LA", 3, "AR", "TX", "MS");
		this.states[22] = new MapNode("WI", 3, "MN", "IA", "IL");
		this.states[23] = new MapNode("IL", 5, "WI", "IA", "MO", "KY", "IN");
		this.states[24] = new MapNode("KY", 7, "VA", "WV", "OH", "IN", "IL", "MO", "TN");
		this.states[25] = new MapNode("TN", 7, "KY", "AR", "MS", "AL", "GA", "NC", "VA");
		this.states[26] = new MapNode("MS", 4, "TN", "AR", "LA", "AL");
		this.states[27] = new MapNode("MI", 2, "IN", "OH");
		
		this.states[28] = new MapNode("IN", 4, "MI", "IL", "KY", "OH");
		this.states[29] = new MapNode("OH", 5, "MI", "IN", "KY", "WV", "PA");
		this.states[30] = new MapNode("WV", 5, "MD", "PA", "OH", "KY", "VA" );
		this.states[31] = new MapNode("VA", 5, "MD", "WV", "KY", "TN", "NC" );
		this.states[32] = new MapNode("PA", 5, "NY", "NJ", "MD", "WV", "OH");
		this.states[33] = new MapNode("NY", 6, "PA", "NJ", "RI", "MA", "VT", "CT");
		this.states[34] = new MapNode("ME", 1, "NH");
		
		this.states[35] = new MapNode("VT", 3, "NY", "MA", "NH");
		this.states[36] = new MapNode("NH", 3, "VT", "ME", "MA");
		this.states[37] = new MapNode("MA", 4, "NH", "VT", "NY", "RI");
		this.states[38] = new MapNode("RI", 2, "MA", "NY");
		this.states[39] = new MapNode("CT", 1, "NY" );
		this.states[40] = new MapNode("NJ", 3, "NY", "PA", "DE");
		this.states[41] = new MapNode("DE", 2, "NJ", "MD");
		
		this.states[42] = new MapNode("AL", 4, "TN", "MS", "FL", "GA");
		this.states[43] = new MapNode("GA", 5, "TN", "AL", "FL", "SC", "NC");
		this.states[44] = new MapNode("FL", 2, "AL", "GA");
		this.states[45] = new MapNode("SC", 2, "NC", "GA");
		this.states[46] = new MapNode("NC", 4, "VA", "TN", "GA", "SC");
		
	}
	
	abstract void colorGraph();
	
	public String displayGraph(){
		String ret = "\n LIST OF STATES AND COLORS:\n";
		for (int i = 0; i < states.length; i++) {
			ret = ret+"  State "+states[i].GetName()+" => "+states[i].GetColor()+"\n";
		}
		ret = ret+"\n";
		return ret;
	}
	
	public void color(MapNode m, String parColor)
	{
			m.SetColor(parColor);
	}
	
	public boolean isSameColor(MapNode m1, MapNode m2)
	{
		if(m1.color == m2.color)
			return true;
		else return false;
	}
	public void borders()
	{
		for (MapNode map : states)
		{
			for (MapEdge border : map.borders)
			{
				for (MapNode m : states)
				{
					if(border.node2 == m.name)
					{
						state1.add(map);
						state2.add(m);
					}
				}
				
			}
		}
	}		
}

public class MapNode {

	public String name;
	public String color;
	
	public boolean assigned;
	
	public MapEdge[] borders;
	
	public MapNode(String parName, int i, String parBorder1) {
		
		this.name = parName;
		this.color = "red";
		assigned = false;
		
			this.borders = new MapEdge[i];
			
			borders[0] = new MapEdge(this.name, parBorder1);
	}	
	public MapNode(String parName, int i, String parBorder1, String parBorder2) {
		
		this.name = parName;
		this.color = "red";
		assigned = false;
		
			this.borders = new MapEdge[i];
			
			borders[0] = new MapEdge(this.name, parBorder1);
			borders[1] = new MapEdge(this.name, parBorder2);
	}
	public MapNode(String parName, int i, String parBorder1, String parBorder2, String parBorder3) 
	{
		this.name = parName;
		this.color = "red";
		assigned = false;
		
			this.borders = new MapEdge[i];
			
			borders[0] = new MapEdge(this.name, parBorder1);
			borders[1] = new MapEdge(this.name, parBorder2);
			borders[2] = new MapEdge(this.name, parBorder3);
	}
	public MapNode(String parName, int i, String parBorder1, String parBorder2,
			String parBorder3, String parBorder4) 
	{
		this.name = parName;
		this.color = "red";
		assigned = false;
		
			this.borders = new MapEdge[i];
			
			borders[0] = new MapEdge(this.name, parBorder1);
			borders[1] = new MapEdge(this.name, parBorder2);
			borders[2] = new MapEdge(this.name, parBorder3);
			borders[3] = new MapEdge(this.name, parBorder4);
	}
	public MapNode(String parName, int i, String parBorder1, String parBorder2,
			String parBorder3, String parBorder4, String parBorder5) 
	{
		this.name = parName;
		this.color = "red";
		assigned = false;
		
			this.borders = new MapEdge[i];
			
			borders[0] = new MapEdge(this.name, parBorder1);
			borders[1] = new MapEdge(this.name, parBorder2);
			borders[2] = new MapEdge(this.name, parBorder3);
			borders[3] = new MapEdge(this.name, parBorder4);
			borders[4] = new MapEdge(this.name, parBorder5);
	}
	public MapNode(String parName, int i, String parBorder1, String parBorder2,
			String parBorder3, String parBorder4, String parBorder5, String parBorder6) 
	{
		this.name = parName;
		this.color = "red";
		assigned = false;
		
			this.borders = new MapEdge[i];
			
			borders[0] = new MapEdge(this.name, parBorder1);
			borders[1] = new MapEdge(this.name, parBorder2);
			borders[2] = new MapEdge(this.name, parBorder3);
			borders[3] = new MapEdge(this.name, parBorder4);
			borders[4] = new MapEdge(this.name, parBorder5);
			borders[5] = new MapEdge(this.name, parBorder6);
	}
	public MapNode(String parName, int i, String parBorder1, String parBorder2,
			String parBorder3, String parBorder4, String parBorder5, 
			String parBorder6, String parBorder7) 
	{
		this.name = parName;
		this.color = "red";
		assigned = false;
		
			this.borders = new MapEdge[i];
			
			borders[0] = new MapEdge(this.name, parBorder1);
			borders[1] = new MapEdge(this.name, parBorder2);
			borders[2] = new MapEdge(this.name, parBorder3);
			borders[3] = new MapEdge(this.name, parBorder4);
			borders[4] = new MapEdge(this.name, parBorder5);
			borders[5] = new MapEdge(this.name, parBorder6);
			borders[6] = new MapEdge(this.name, parBorder7);
	}
	
	public String GetName(){
		return this.name;
	}
	
	public String GetColor(){
		return this.color;
	}
	
	public void SetColor(String parColor){
		this.color = parColor;
	}
}

public class MapEdge {

	public String node1;
	public String node2;
	
	public MapEdge(String parNode1, String parNode2) {
		this.node1 = parNode1;
		this.node2 = parNode2;
	}

}

Instead of leading with a code dump, would you mind just talking about your algorithm first?

Ok sorry. I'll try to explain what i do.

First i create an array of MapNodes and i inicialize them. These are the states, Each State has a name, color and an array of borders (that is the MapEdge ), in the array of borders i inicialize the adjecent states (for the state "OR" the MapEdges (borders) would be ["OR","WA"],["OR","ID"],["OR","NV"] and ["OR","CA]").

After this in the colorGraph() method i use the borders() method. The borders method fills two MapNode lists with the adjecent states. So the first item in the state1 would be OR and the first in state2 WA, the second in state1 OR, the second in state2 ID etc... So basicly they are paired by their indexes.

After the borders method i fill the states arrays states with random colors.

After this i check if the adjecent states are the same color (state1.get(i) is same color as state2.get(i)).

While they have the same color, i randomly assign other color to state1 and this continues while they have the same color.

This is is but its not working correctly, I know that the problem is in this last bit of code where i check them if they are the same color but i don't know how to fix it, i tried lots of ways but i just cant get it.

Hope you can understand it from this text, it's little hard to explain it like this, and english is not my main language, but i hope it's readable.

Thanks in advance

Ronel

I don't know if this randomized method has a decent probability of succeeding. It could be that a very small fraction of random colorings are valid, and then your program won't work. If you want to know if that's what's happening, I suggest debugging your program to see if it's working as you expect or not.

But I would try with backtracking, which is easy to implement recursively. This is a good programming exercise.

Yes it's a project that i need to do.

But it's not like i just ask for the answer without programming anything. I'm stuck thats why i asked for help.

I asked the teacher too, but he suggested that i should implement Min-Conflict. Just like Álvaro suggested that i should implement backtracking.

But the problem is that i can't even solve this, and i don't know how should i implement either one of those two.

I have read lots of descriptions about CSP, but the problem is that there are no real examples, the only one good that i have found is the AIMA library, i understand the example code there for map coloring, but it has so much imports and the imports have imports too, i can't understand everything there.

That's why i asked for help. If it's against the rules, then i'm sorry for starting the thread.

Ronel.

What problems are you having implementing this using backtracking?