EightPuzzle.java

/*********************************************************************************************
* Name: David Emmanuel
* Date: October 12, 2015 
* Class: CS 420
* Description:
**********************************************************************************************/
import java.util.Random;
import java.util.Scanner;
public class EightPuzzle {	
	public static void main(String[] args) {
		int eCount = 0, tempNum, ans = 0, num = 0;				// Reply the user enters and the num is the counter for the frontier
		int[][] temp = new int[3][3], goal = { {0,1,2}, {3,4,5}, {6,7,8} };
		boolean play = true, h_1 = true, finished = false;
		Scanner kb = new Scanner(System.in);
		Node[] frontier = new Node[200], path;
		Node[][] explored = new Node[55][80];	// Holds all previous states that are not in the frontier by their cost
		Node root = new Node(), copy, min;			// Copy save the root for the second heuristic	
		
		for(int h = 0; h < 55; h++) {
			for(int g = 0; g < 80; g++) {
				explored[h][g] = new Node();
			}
		}
		
		
		while(play) {		// While the user wants to continue playing
			System.out.println("\n\nIf you would like a rondomly generated puzzle enter: 1\n" + 
							   "If you would like to enter in your own puzzle enter: 2\n" +
							   "If you would like to quit enter: 3\n");
			ans = kb.nextInt();
			///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Random root
			if(ans == 1) {							// A randomly generated puzzle is configured
				root.setPuzzle(fillPuzzle());
				frontier[num++] = root;
				setCosts(frontier, num, 1, goal);		// Find the cost for the root using the first heuristic
				explored[root.getCost()][0] = root;		// Add the root to the explored set
				copy = root.copy();					// Copies the node for the second heuristic	
				frontier[0] = null;						// Remove the root from the frontier
				num = 0;
				num = expandNode(root, frontier, num);	// Expand the root and add the expanded states to the frontier
				while(h_1) {									//////////////////////////////////////////////////////////////////////////////// First heuristic
					setCosts(frontier, num, 1, goal);		// Sets the costs for all nodes in the frontier for the first heuristic
					num = checkFrontier(frontier, explored, num);		// Checks to see if a state has already been visited
					min = findMin(frontier, num);
					
					if(checkGoal(min, goal)) {	// If the goal state has the lowest cost
						path = new Node[min.getGCost() + 1];
						for(int i = 0; i < path.length; i++) {	// Fill in the path by getting the parents
							path[i] = min;
							min = min.getParent();
						}
						for(int j = path.length - 1; j > -1; j--) {		// Print path in reverse order
							path[j].print();
							System.out.println();
						}
						h_1 = false;	// Done with the first heuristic 
					} else {
						while(explored[min.getCost()][eCount] == null) {
							eCount++;
						}
						explored[min.getCost()][eCount] = min;	// Add min to explored
						eCount = 0;								// Reset eCount
						num = expandNode(min, frontier, num);	// Expand min
					}
				}
				
				for(int x = 0; x < num; x++) {	// Resets the frontier
					frontier[x] = null;
				}
				
				num = 0;			// Reset num
				path = null;		// Reset the path
				explored = null;	// Reset explored
				min = null;			// Reset the min
				
				root = copy;
				////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Second heuristic
				
				frontier[num++] = root;
				setCosts(frontier, num, 1, goal);		// Find the cost for the root using the first heuristic
				explored[root.getCost()][0] = root;		// Add the root to the explored set
				frontier[0] = null;						// remove the root from the frontier
				num = 0;
				num = expandNode(root, frontier, num);	// Expand the root and add the expanded states to the frontier
				while(!h_1) {
					setCosts(frontier, num, 2, goal);		// Sets the costs for all nodes in the frontier for the second heuristic
					num = checkFrontier(frontier, explored, num);		// Checks to see if a state has already been visited
					min = findMin(frontier, num);
					
					if(checkGoal(min, goal)) {	// If the goal state has the lowest cost
						path = new Node[min.getGCost() + 1];
						for(int i = 0; i < path.length; i++) {	// Fill in the path by getting the parents
							path[i] = min;
							min = min.getParent();
						}
						for(int j = path.length - 1; j > -1; j--) {		// Print path in reverse order
							path[j].print();
							System.out.println();
						}
						h_1 = true;		// Done with the second heuristic 
					} else {
						while(explored[min.getCost()][eCount] == null) {
							eCount++;
						}
						explored[min.getCost()][eCount] = min;	// Add min to explored
						eCount = 0;								// Reset eCount
						num = expandNode(min, frontier, num);	// Expand min
					}
				}
			
			/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Root is given	
				
			} else if(ans == 2) {							// The user enters their own puzzle
				for(int i = 0; i < temp.length; i++) {
					for(int j = 0; j < temp[i].length; j++) {
						temp[i][j] = kb.nextInt();
					}
				}
				root.setPuzzle(temp);
				frontier[num++] = root;
				setCosts(frontier, num, 1, goal);		// Find the cost for the root using the first heuristic
				explored[root.getCost()][0] = root;		// Add the root to the explored set
				copy = root.copy();					// Copies the node foe the second heuristic
				frontier[0] = null;						// Remove the root from the frontier
				num = 0;
				num = expandNode(root, frontier, num);
				
				while(h_1) {									//////////////////////////////////////////////////////////////////////////////// First heuristic
					setCosts(frontier, num, 1, goal);		// Sets the costs for all nodes in the frontier for the first heuristic
					num = checkFrontier(frontier, explored, num);		// Checks to see if a state has already been visited
					min = findMin(frontier, num);
					if(min.getNumOfChildren() != 0) {
						min = findNewMin(frontier, num, min);
					}
					
					if(checkGoal(min, goal)) {	// If the goal state has the lowest cost
						path = new Node[min.getGCost() + 1];
						for(int i = 0; i < path.length; i++) {	// Fill in the path by getting the parents
							path[i] = min;
							min = min.getParent();
						}
						for(int j = path.length - 1; j > -1; j--) {		// Print path in reverse order
							path[j].print();
							System.out.println();
						}
						h_1 = false;	// Done with the first heuristic 
					} else {
						while(explored[min.getCost()][eCount] != null) {
							eCount++;
						}
						explored[min.getCost()][eCount] = min;	// Add min to explored
						eCount = 0;								// Reset eCount
						num = removeFromFrontier(frontier, min, num);
						num = expandNode(min, frontier, num);	// Expand min
						//if(tempNum == num) {
							//System.out.printlnt
						//}
							
					}
				}
				
				for(int x = 0; x < num; x++) {	// Resets the frontier
					frontier[x] = null;
				}
				
				num = 0;			// Reset num
				path = null;		// Reset the path
				explored = null;	// Reset explored
				min = null;			// Reset the min
				
				root = copy;
				////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Second heuristic
				
				frontier[num++] = root;
				setCosts(frontier, num, 1, goal);		// Find the cost for the root using the first heuristic
				explored[root.getCost()][0] = root;		// Add the root to the explored set
				frontier[0] = null;						// remove the root from the frontier
				num = 0;
				num = expandNode(root, frontier, num);	// Expand the root and add the expanded states to the frontier
				while(!h_1) {
					setCosts(frontier, num, 2, goal);		// Sets the costs for all nodes in the frontier for the second heuristic
					num = checkFrontier(frontier, explored, num);		// Checks to see if a state has already been visited
					min = findMin(frontier, num);
					
					if(checkGoal(min, goal)) {	// If the goal state has the lowest cost
						path = new Node[min.getGCost() + 1];
						for(int i = 0; i < path.length; i++) {	// Fill in the path by getting the parents
							path[i] = min;
							min = min.getParent();
						}
						for(int j = path.length - 1; j > -1; j--) {		// Print path in reverse order
							path[j].print();
							System.out.println();
						}
						h_1 = true;		// Done with the second heuristic 
					} else {
						while(explored[min.getCost()][eCount] == null) {
							eCount++;
						}
						explored[min.getCost()][eCount] = min;	// Add min to explored
						eCount = 0;								// Reset eCount
						num = expandNode(min, frontier, num);	// Expand min
					}
				}
			
				
			} else if(ans == 3) {	// The user quits the program
				System.out.println("Good Bye :)\n");
				play = false;
			}
			else					// An incorrect command was entered and the prompt appears once more
				System.out.println("Command not recognized\n");	
		}
	}
	
	public static int removeFromFrontier(Node[] f, Node x, int num) {
		// The purpose of this method is to remove a node from the frontier and 
		// shift it over as well adjust the num
		boolean id = true;
		
		for(int i = 0; i < num; i++) {			// Runs through the frontier
			for(int j = 0; j < 3; j++) {		
				for(int k = 0; k < 3; k++) {
					if(f[i].puzzle[j][k] != x.puzzle[j][k])		// Compares state with x
						id = false;
				}
			}
			if(id) {			// If we found the state
				f[i] = null;	// Remove it
				for(int l = i; l < num; l++) {		// Shift over
					f[l] = f[l + 1];
					f[l + 1] = null;
				}
				return num - 1;
			}
		}
		return num;
	}
	
	public static void setCosts(Node[] f, int num, int h, int[][] g) {
		// This method sets the costs for each node in the frontier that hasn't
		// had their cost set. If num = 1 then it sets the costs according to the 
		// first heuristic. If num = 2 it sets the costs for the second heuristic.
		int cost = 0;
		
		if(h == 1) {		// If its the first heuristic
			for(int i = 0; i < num; i++) {		// Run through all the nodes in the frontier
				//System.out.println("---------------------" + i);
				//f[i].print();
				//System.out.println("Cost is: " + f[i].getCost());
				if(f[i].getCost() == 0) {		// If the cost hasn't been set up yet
					cost = 0;
					for(int j = 0; j < 3; j++) {		// First loop of the 2D array
						for(int k = 0; k < 3; k++) {	// Second loop of the 2D array
							if(f[i].puzzle[j][k] != g[j][k]) {		// If the values are not equal add a 
								cost++;								// point to the cost
							}
						}
					}
					f[i].setCost(cost + f[i].getGCost());
				}
				//f[i].print();
				//System.out.println("Cost is: " + f[i].getCost());
				//System.out.println("---------------------");
			}
		} else {			// Cost is determined by the second heuristic
			for(int l = 0; l < num; l++) {	// Run through all the nodes in the frontier
				if(f[l].getCost() == 0) {	// If the cost hasn't been set up yet
					for(int m = 0; m < 3; m++) {		// Runs through the first loop of the 2D array
						for(int n = 0; n < 3; n++) {	// Runs through the second loop of the 2D array
							if(f[l].puzzle[m][n] != g[m][n]) {		// If the piece is not in its correct place
								f[l].setCost(pathCost(f[l].getPuzzle(), m, n, g) + f[l].getGCost());
							}
						}
					}
				}
			}
		}
	}
	
	public static int pathCost(int[][] node, int row_1, int col_1, int[][] g) {
		// This method finds the path cost of one piece in the puzzle
		int num = node[row_1][col_1], row_2 = -1, col_2 = -1;
		
		for(int i = 0; i < 3; i++) {		// Finds the index it should be at and sets it
			for(int j = 0; j < 3; j++) {	// to row_2 and col_2
				if(g[i][j] == num) {
					row_2 = i;
					col_2 = j;
				}
			}
		}
		
		if(row_1 == row_2 && col_1 == col_2)	// If they are in the same position
			return 0;
		if(row_1 == row_2) {			// If they are in the same row
			num = row_1 - row_2;
			if(num < 0)
				return num * (-1);
			else 
				return num;
		} else if(col_1 == col_2) {			// If they are in the same column 	
			num = col_1 - col_2;
			if(num < 0)
				return num * (-1);
			else 
				return num;
		} else if( (row_1 - 1 == row_2 && (col_1 + 1 == col_2 || (col_1 - 1 == col_2) )) || (row_1 + 1 == row_2 && (col_1 + 1 == col_2 || col_1 - 1 == col_2)) )
			return 2;
		
		if( ((row_1 + 2 == row_2 || row_1 - 2 == row_2) && (col_1 + 1 == col_2 || col_1 - 1 == col_2)) || ((col_1 + 2 == col_2 || col_1 - 2 == col_2) && (row_1 - 1 == row_2 || row_1 +1 == row_2)) )
			return 3;
		else 
			return 4;
	}
	
	public static int checkFrontier(Node[] f, Node[][] e, int num) {
		// The purpose of this method is to see if any of the states that are in the frontier 
		// have already been expanded. This method sifts through the expanded hash table using the
		// cost of the state as the index. If a state has already been visited it will be deleted
		// from the frontier and num will be reduced by one.
		int temp = num;	// If num needs to be reduced temp will keep track of it
		int count = 0;	// Indexes through the 2nd dimension of the hash table
		boolean repeat = true, runWhile = true;
		
		//System.out.println("The number of states in the frontier is: " + num);
		
		for(int i = 0; i < num; i++) {		// Runs through all states in the frontier
			int pra = f[i].getCost();
			Node[] tlo = e[pra];
			System.out.println("First index = " + pra);
			System.out.println("Count = " + count);
			System.out.println("i = " + i);
			System.out.println("num = " + num);
			tlo[count].print();
			while(e[f[i].getCost()][count] != null && runWhile) {	// While the explored list is not null for the specified index
				for(int j = 0; j < 3; j++) {							// Runs through the state's puzzle in frontier and explored
					for(int k = 0; k < 3; k++) {						// and compares the two
							if(f[i].puzzle[j][k] != e[f[i].getCost()][count].puzzle[j][k])	// If one term from the puzzles does not match
								repeat = false;												// the states are not equal to one another
					}
				}
				count++;
				if(repeat) {			// If the states are equal	
					temp--;		
					f[i] = null;		// Remove the state from the frontier
					runWhile = false;	// Stop looking at the explored list with this state
				}
			}
			repeat = true;
			count = 0;
		}
		
		if(num != temp) {		// If a state was deleted then shift over the frontier
			for(int l = 0; l < num; l++) {
				if(f[l] == null) {
					f[l] = f[l + 1];
					f[l + 1] = null;
				}
			}
			num = temp;		// Adjust num
		}
		return num;
	}
	
	public static boolean checkGoal(Node min, int[][] g) {
		// This method will keep track of the node in the frontier with the lowest
		// cost and it will also search for a goal state. If the goal state is the
		// lowest cost it will return true.
		boolean goal = true;
		
		for(int j = 0; j < 3; j++) {		// Compares the goal state and current state
			for(int k = 0; k < 3; k++) {
				if(min.getPuzzle()[j][k] != g[j][k])
					goal = false;
			}
		}
		return goal;
	}
	
	public static int[][] fillPuzzle() {
		// This method randomly fills an array with the numbers 0 - 8
		// and then returns it.
		Random r = new Random();
		int x = r.nextInt(9);	// Generates a random number from 0 - 8
		int[][] puz = new int[3][3];
		
		for(int k = 0; k < puz.length; k++) {			// Sets all numbers to 10 
			for(int l = 0; l < puz[k].length; l++) {	
				puz[k][l] = 10;
			}
		}
		
		for(int i = 0; i < puz.length; i++) {
			for(int j = 0; j < puz[i].length; j++) {		
				while(puzzleContains(i, j, x, puz)) {	// has already been added to the puzzle
					x = r.nextInt(9);
				}
				puz[i][j] = x;
			}
		}
		return puz;
	}
	
	public static Node findMin(Node[] f, int num) {
		// This method runs through all states in the frontier and returns
		// the state with the lowest cost;
		Node min = f[0];
		int index = 0;
		
		for(int i = 1; i < num; i++) {
			if(min.getCost() > f[i].getCost()) {
				min = f[i];
				index = i + 1;
			}
		}
		if(min.getNumOfChildren() != 0) {
			if(index < num) {
				for(int j = index; j < num; j++) {
					if(min.getCost() == f[j].getCost() && f[j].getNumOfChildren() == 0)
						return f[j];
						
				}
			}
			else {
				for(int k = 1; k < 30; k++) {
					for(int l = 0; l < num; l++) {
						if(f[l].getCost() <= (min.getCost() + k) && f[l].getNumOfChildren() != 0)
							return f[l];
					}
				}
			}
		}
		for(int m = 0; m < num; m++) {
			if(f[m].getNumOfChildren() == 0)
				return f[m];
		}
		
		for(int z = 0; z < num; z++) {
			System.out.println(f[z].getNumOfChildren()); 
			System.out.println("----------------------");
		}
		return null;
	}
	
	public static Node findNewMin(Node[] f, int num, Node m) {
		// This method runs through all states in the frontier and returns
		// the state with the lowest cost that isn't the min
		Node min = m;
		int index = 5;
		boolean match = true;
			
		for(int i = 0; i < num; i++) {
			for(int j = 0; j < 3; j++) {
				for(int k = 0; k < 3; k++) {
					if(f[i].puzzle[j][k] != m.puzzle[j][k]) {
						match = false;
					}
				}
			}
			if(match) 
				index = i + 1;
		}
		for(int n = 0; n < 40; n++) {
			for(int l = index; l < num; l++) {
				if(f[l].getCost() == min.getCost() + n)
					return f[l];
			}	
		}
		return f[num - 1];
	}
	
	public static boolean puzzleContains(int i, int j, int x, int[][] puz) {
		// This method determines whether or not a number is already in
		// the puzzle. If it is it returns true and false if otherwise.
		
		for(int row = 0; row <= i; row++) {	// Checks up to the row that is currently being filled
			for(int col = 0; col < puz[row].length; col++) {
				if(puz[row][col] == x)
					return true;
			}
		}
		return false;
	}
	
	public static int expandNode(Node n, Node[] frontier, int num) {
		// This method will expand the node into all possible results based on its
		// current state. These expanded nodes are the children of the node that
		// was passed in. The maximum number of children possible is 4 and all 
		// children will be stored in an array which will then be returned. If the 0 index of
		// pos is the row of 0's location and the 1 index is the col of 0's location.
		int[] instructions;	// Holds the position of 0 and the direction needed
		
		System.out.println("\nBefore the node expands it has this many children " + n.getNumOfChildren());
		System.out.println("And the number of states in the frontier is: " + num);
		if(n.getNumOfChildren() != 0) {
			System.out.println("-------------------------Frontier------------------------------");
			for(int q = 0; q < num; q++) {
				frontier[q].print();
				System.out.println("\n" + frontier[q].getCost());
			}
			System.out.println("-------------------------------------------------------");
		}
			
		instructions = n.findZero();
		
		if(instructions[2] == 0) {	
			frontier[num++] = n.swap(instructions, 0);		// swap up
			frontier[num++] = n.swap(instructions, 1); 		// swap right
			frontier[num++] = n.swap(instructions, 2);		// swap down
			frontier[num++] = n.swap(instructions, 3);		// swap left
		} else if(instructions[2] == 1) {
			frontier[num++] = n.swap(instructions, 0);		// swap up
			frontier[num++] = n.swap(instructions, 3);		// swap left
		} else if(instructions[2] == 2) {
			frontier[num++] = n.swap(instructions, 0);		// swap up
			frontier[num++] = n.swap(instructions, 1); 		// swap right
		} else if(instructions[2] == 3) {
			frontier[num++] = n.swap(instructions, 2);		// swap down
			frontier[num++] = n.swap(instructions, 3);		// swap left
		} else if(instructions[2] == 4) {
			frontier[num++] = n.swap(instructions, 1); 		// swap right
			frontier[num++] = n.swap(instructions, 2);		// swap down
		} else if(instructions[2] == 5) {
			frontier[num++] = n.swap(instructions, 1); 		// swap right
			frontier[num++] = n.swap(instructions, 2);		// swap down
			frontier[num++] = n.swap(instructions, 3);		// swap left
		} else if(instructions[2] == 6) {
			frontier[num++] = n.swap(instructions, 0);		// swap up
			frontier[num++] = n.swap(instructions, 1); 		// swap right
			frontier[num++] = n.swap(instructions, 3);		// swap left
		} else if(instructions[2] == 7) {
			frontier[num++] = n.swap(instructions, 0);		// swap up
			frontier[num++] = n.swap(instructions, 1); 		// swap right
			frontier[num++] = n.swap(instructions, 2);		// swap down
		} else if(instructions[2] == 8) {
			frontier[num++] = n.swap(instructions, 0);		// swap up
			frontier[num++] = n.swap(instructions, 2);		// swap down
			frontier[num++] = n.swap(instructions, 3);		// swap left
		}
		return num;
	}
}

Node.java

/***************************************************************************
* Name: David Emmanuel 
* Date: Oct 15, 2015
* Class: CS 420
* Description:
***************************************************************************/
public class Node {
///////////////////////////////////// Attribute
	
	public int[][] puzzle = new int[3][3];
	private int cost = 0, gCost = 0, numOfChildren = 0;		// numOfChildren is the index for the array of children
	private Node parent;
	private Node[] children = new Node[4];

///////////////////////////////////// Constructor
	
	public Node() {		// Initialize the root node without a constructed puzzle
		parent = null;
	}
	
	public Node(int[][] puz) {	// Initialize the root node while passing in a puzzle
		parent = null;
		
		for(int i = 0; i < puzzle.length; i++) {
			for(int j = 0; j < puzzle[i].length; j++) {
				puzzle[i][j] = puz[i][j];
			}
		}
	}
	
	public Node(int[][] puz, Node p) {	// Initialize a child node with a puzlle and a parent
		parent = p;
		
		for(int i = 0; i < puzzle.length; i++) {
			for(int j = 0; j < puzzle[i].length; j++) {
				puzzle[i][j] = puz[i][j];
			}
		}
	}
	
///////////////////////////////////// Methods
	
	public void print() {
		// This method prints out the puzzle
		System.out.println();
		for(int i = 0; i < puzzle.length; i++) {
			System.out.println();
			for(int j = 0; j < puzzle[i].length; j++) {
				System.out.print(puzzle[i][j] + " ");
			}
		}
	}
	
	public Node getParent() {
		return parent;
	}
	
	public void setParent(Node p) {
		parent = p;
	}
	
	public void setChild(Node c) {
		children[numOfChildren] = c;
		numOfChildren++;
	}
	
	public void setCost(int c) {
		cost = c;
	}
	
	public void setGCost(int g) {
		gCost = g;
	}
	
	public void setPuzzle(int[][] puz) {
		
		for(int i = 0; i < puzzle.length; i++) {
			for(int j = 0; j < puzzle[i].length; j++) {
				puzzle[i][j] = puz[i][j];
			}
		}
	}
	
	public void setNumOfChildren(int x) {
		numOfChildren = x;
	}
	
	public int getNumOfChildren() {
		return numOfChildren;
	}
	
	public int getCost() {
		return cost;
	}
	
	public int[][] getPuzzle() {
		return puzzle;
	}
	
	public int getGCost() {
		return gCost;
	}
	
	public int[] findZero() {
		// This method locates where the 0 space is and returns the 
		// row and column number of its location. The zero index is the 
		// row number and the 1 index is the column number. The second index
		// holds a number that determines how the stae can be expanded
		int[] ans = new int[3];		// Holds the row and column of the zero and the direction needed
		
		for(int i = 0; i < 3; i++) {
			for(int j = 0; j < 3; j++) {
				if(puzzle[i][j] == 0) {
					ans[0] = i;
					ans[1] = j;
				}
			}
		}
		
		if(ans[0] == 0 && ans[1] == 0)
			ans[2] = 4;
		else if(ans[0] == 0 && ans[1] == 1)
			ans[2] = 5;
		else if(ans[0] == 0 && ans[1] == 2)
			ans[2] = 3;
		else if(ans[0] == 1 && ans[1] == 0)
			ans[2] = 7;
		else if(ans[0] == 1 && ans[1] == 1) 
			ans[2] = 0;
		else if(ans[0] == 1 && ans[1] == 2)
			ans[2] = 8;
		else if(ans[0] == 2 && ans[1] == 0)
			ans[2] = 2;
		else if(ans[0] == 2 && ans[1] == 1)
			ans[2] = 6;
		else if(ans[0] == 2 && ans[1] == 2)
			ans[2] = 1;
		else 
			ans[2] = -1;
		return ans;
	}
	
	public Node copy() {
		// This method returns an exact copy of the Node being copied
		Node temp;
		int[][] puz = new int[3][3];
		
		for(int i = 0; i < 3; i++) {
			for(int j = 0; j < 3; j++) {
				puz[i][j] = puzzle[i][j];
			}
		}
		
		temp = new Node(puz, parent);
		for(int k = 0; k < 4; k++) {
			temp.setChild(children[k]);
		}
		temp.setCost(cost);
		temp.setGCost(gCost);
		return temp;
	}
	
	public Node swap(int[] ins, int d) {
		// This method uses the current node so generate another node that
		// has swapped one position. If d = 0 it swaps up, d = 1 it swaps right,
		// d = 2 it swaps down, and if d = 3 it swaps left.
		Node child = new Node(puzzle, this);
		int temp, row = ins[0], col = ins[1];

		child.setParent(this);
		child.setCost(0);
		//child.setNumOfChildren(0);
		
		if(d == 0) {	// Swap up
			temp = child.puzzle[row][col];
			child.puzzle[row][col] = child.puzzle[row - 1][col];
			child.puzzle[row - 1][col] = temp;
			child.setGCost(1 + gCost);
			children[numOfChildren++] = child; 
			//child.print();
			//System.out.println('\n' + numOfChildren + " 0");
			return child;
		} else if(d == 1) { // Swap right
			temp = child.puzzle[row][col];
			child.puzzle[row][col] = child.puzzle[row][col + 1];
			child.puzzle[row][col + 1] = temp;
			child.setGCost(1 + gCost);
			children[numOfChildren++] = child;
			//child.print();
			//System.out.println('\n' + numOfChildren + " 1");
			return child;
		} else if(d == 2) {	// Swap down
			temp = child.puzzle[row][col];
			child.puzzle[row][col] = child.puzzle[row + 1][col];
			child.puzzle[row + 1][col] = temp;
			child.setGCost(1 + gCost);
			children[numOfChildren++] = child;
			//child.print();
			//System.out.println('\n' + numOfChildren + " 2");
			return child;
		} else {
			temp = child.puzzle[row][col];
			child.puzzle[row][col] = child.puzzle[row][col - 1];
			child.puzzle[row][col - 1] = temp;
			child.setGCost(1 + gCost);
			children[numOfChildren++] = child;
			//child.print();
			//System.out.println('\n' + numOfChildren + " 3");
			return child;
		}
		
	}
}