Darshan Nayak

Full Stack Developer

8-Puzzle Search

Languages/Libraries: Java

Through this application, various search algorithms were implemented for finding solutions for a number of 8-Puzzle games. This was an assignment for CS 820 (Artificial Intelligence) at University of Regina.

Search Algorithms: Depth First Search, Breadth First Search, and Best First Search using 3 distinct heuristics.

Main.java

Following code snippet shows how the Best-First Search tree is generated/traversed during search.

						
public static void continuePlay_BestFS(Node currentNode, int heuristicChoice)	//continues search for goal node after search at previous node fails
{
	
	if (isGoalState(currentNode.gameState)) //every time, we first check if the node in hand is the goal node or not. If it is, we don't need to continue.
	{
		//trace back to origin and print victory!!
		System.out.println("Victory for Best First Search !! Here is the list of moves, starting from\nInitial state:");
		traceVictory_BestFS(currentNode);
		System.out.println("Congratulations! You have reached the goal state.");
		System.out.println("Total states generated to reach goal state: "+popCount);
	}
	else    //if the node in hand is no goal, then we continue with the program
	{
		
		nodeArrayList_BestFSTrace.add(queueBestFS.poll());  //a node from the front of the queue is removed and logged into an arrayList (this arrayList contains the 'explored nodes')
		popCount++;
		if (nodeArrayList_BestFSTrace != null && !nodeArrayList_BestFSTrace.isEmpty())  //check if the arrayList is empty
		{
			Node pregnantNode=nodeArrayList_BestFSTrace.get(nodeArrayList_BestFSTrace.size()-1);    //get the last element of arraylist for creating its child nodes
			createChildNodes_BestFS(pregnantNode, nodeArrayList_BestFSTrace.size() - 1, nodeArrayList_BestFSTrace.get(pregnantNode.parentIndexInTraceList),heuristicChoice);
		}
		if (queueBestFS.peek() != null)    //if the queue is not empty, continue with the program.
		{
			continuePlay_BestFS(queueBestFS.peek(),heuristicChoice);
		}
		else //queue empty, goal not found.
		{
			System.out.println("Ran out of nodes, but goal state still not found. Sorry!");
			//usually, netBeans callStack overflows before this happens!! 
			
		}
		
	}
}
						
                  

Following code shows the function implementation for generating the Best-First Search's final sequence of moves for the game.

						
public static void traceVictory_BestFS(Node currentNode)	//after finding solution, this function prepares the list of moves to make from the tree for winning the game
{
	boolean iterate=true;
	while (iterate)
	{
		solutionListBestFS.add(currentNode);    //in the solutionListBestFS variable, the nodes which are in the path between the initial and goal state are added, while maintining the order of parenthood.
		currentNode=nodeArrayList_BestFSTrace.get(currentNode.parentIndexInTraceList);  //gets the parent of the currentnode.
		if (areStatesSame(currentNode.gameState, initialNode.gameState)) //terminating condition for the while loop. It terminates when we reach all the way up to the initial state.
		{
			solutionListBestFS.add(currentNode);
			iterate=false;
		}
	}
	Collections.reverse(solutionListBestFS);    //reversal is required, otherwise the printed states will be from goal to initial. We want to go from initial to goal state.
	
	for (Node item : solutionListBestFS)    //for each loop used to print the path nodes.
	{
		printState(item.gameState);
		System.out.println("\n");
	}
	System.out.println("Total moves required: "+(solutionListBestFS.size()-1));
}