class puzzleSolver
{
    
    //graph walker for puzzle problem
    //initial puzzle configuration is passed in, together with
    //a search structure and a sequence structure
    //code tries to determine if there is a path from initial configuration
    //to sorted configuration
    //we will make this code more generic later to permit it to take any
    //graph as input
    
    public static void graphSearch(IPuzzle p0, SeqStructure frontier, SearchStructure visited)
    {
	int counter = 0;
	visited.insert(p0);
	frontier.put(p0);
	
	//while there are frontier nodes
	while (! frontier.isEmpty())
	    {
		if (counter % 100 == 0)
		    System.out.println(counter);
		counter++;
		//get a frontier node
		IPuzzle p = (IPuzzle)frontier.get();
		//determine adjacent nodes and process them
		String Moves = "NSEW";
		for (int i = 0; i < Moves.length(); i++)
		    {
			IPuzzle nP = p.duplicate();
			char dir = Moves.charAt(i);
			//try to make the move
			
			boolean OK = nP.move(dir);
			if (OK)
			    {
				//move succeeded, so we have a legitimate node
				boolean reachedFinal = processNode(nP,frontier,visited);
				if (reachedFinal)
				    {
					System.out.println("Hurrah! We have reached the sorted state in " + counter + " steps!");
					nP.display();
					return;
				    }
			    }
		    }
		
		
		
	    }
	//no more frontier nodes
	System.out.println("Could not reach sorted state");	  
    }
    
    //if unexplored node, inserts it in visited and frontier sets
    //returns true if node is goal state
    public static boolean processNode(IPuzzle nP, SeqStructure frontier, SearchStructure visited)
    {
	//if we have reached the sorted state
	if (nP.isSolved()) return true;
	if (! visited.search(nP))
	    {
		//we have a state that we have not visited
		visited.insert(nP);
		frontier.put(nP);
	    }
	return false;
    }
}