# need help figuring out what is wrong with my A* search algorithm for an 8 puzzle

• March 28th, 2010, 01:27 PM
javaman87
need help figuring out what is wrong with my A* search algorithm for an 8 puzzle
hello, this is my first post!
I am coding an 8 puzzle program to solve any instance of the eight puzzle. An input file for this program contains an initial state and a goal state separated by a blank line. 'B' Stands for the blank in the puzzle. Top is initial bottom is goal state. For this particular instance the algorithm does not work:
321
4B6
875

123
456
B78

There are many others it does not work for, this is just one. I find one thing weird is that when checking the open list for a node with the same state with a greater gcost value(level in the tree), it never has a greater cost and never gets updated with a lesser cost. Not sure if this is a problem though. The only code that you most likely have to look at is solvePuzzle() and inListWithGreaterCost(). inListWithGreaterCost() checks a list(open) to see if there is a Node with the same state with a better cost than its current level. If the gcost of the node in the list is lower, the new Node updated with the lesser cost and the old one is removed. The open list is sorted by heuristic + gcost(level of tree) on every iteration of A* algorithm to prioritize open list. Can someone please help me out, I am very stuck as it seems that i am following the algorithm's pseudocode perfectly(I have found many versions). Here is most of the code for the EightPuzzle class, it is lengthy but you will most likely have to look at those two functions i mentioned. I just wanted to post all so you will have a better reference. I'm just not so sure what is wrong with my code that is causing me to repeat states and the loop runs infinitely, can someone please help point out what is wrong? I also posted the tree and node classes for reference,Thanks!
Code :

```import java.io.*; import java.text.*; import java.util.*;     public class EightPuzzle{   //puzzle holds current state of puzzle, and goal holds goal state private char [][] puzzle = new char [3][3]; private char [][] goal = new char [3][3];   //moves that can be made for current puzzle state private ArrayList<Character> moves;   //frontier for A* search, static so it doesn't need to be allocated for //each object, and is a member because it is used in multiple methods private static Tree <EightPuzzle> frontier = new Tree<EightPuzzle>();   private static final int STEPCOST = 1;//cost to make a move   //used to keep track of heuristic being used private String heuristicID = new String();   //heuristic value for EightPuzzle to goal, calculated by h1 or h2 private int heuristic;   /* constructor for an EightPuzzle takes a file and saves it in a string and * initializes both goal and puzzle arrays in initialize function. Also gets * the possible moves for the current state of the EightPuzzle and * initializes the frontier for A* search to this object just created. * This is used to construct the initial state of the puzzle. */ public EightPuzzle(File in, String heuristicID) { moves = new ArrayList<Character>(); String str = buildPuzzle(in); this.initialize(str); this.getPossibleMoves(); frontier = new Tree<EightPuzzle>(this); this.heuristicID = heuristicID; if(heuristicID.equals("h1")) this.heuristic = heuristic1(this.puzzle); else if(heuristicID.equals("h2")) this.heuristic = heuristic2(this.puzzle); else this.heuristic = heuristic1(this.puzzle);//default }   /* constructs an EightPuzzle from the array passed in. Sets the puzzle value * to state and gets the possible moves for that state. */ public EightPuzzle(char[][] state,String heuristicID) { moves = new ArrayList<Character>();   this.puzzle = state; this.getPossibleMoves(); this.heuristicID = heuristicID; if(heuristicID.equals("h1")) this.heuristic = new Integer(heuristic1(this.puzzle)); else if(heuristicID.equals("h2")) this.heuristic = new Integer(heuristic2(this.puzzle)); else this.heuristic = new Integer(heuristic1(this.puzzle));//default }   /* copy constructor, makes a deep copy of p. */ public EightPuzzle(EightPuzzle p) { for(int i = 0; i < 3; i++)//deep copy puzzle for(int j = 0; j < 3; j++) { this.puzzle[i][j] = new Character(p.puzzle[i][j]); } this.moves = new ArrayList<Character>(); final int SIZE = p.getMoves().size(); for(int i =0; i < SIZE;i++)//deep copy moves this.moves.add(new Character(p.moves.get(i))); //point to same goal in memory, doesn't need deep copy this.goal = p.getGoal();   if(p.heuristicID.equals("h1")) this.heuristic = new Integer(heuristic1(this.puzzle)); else if(p.heuristicID.equals("h2")) this.heuristic = new Integer(heuristic2(this.puzzle)); else this.heuristic = new Integer(heuristic1(this.puzzle));//default }   //accessor method for puzzle member public char [][] getPuzzle() { return this.puzzle; }   //accessor method for heuristic public int getHeuristic() { return this.heuristic; }   //accessor method for goal member public char [][] getGoal() { return this.goal; }   //accessor method for frontier member public Tree<EightPuzzle> getFrontier() { return frontier; }   //accessor method for moves member public ArrayList<Character> getMoves() { return this.moves; }   //entry point public static void main(String [] args) { //EightPuzzle for h1 EightPuzzle p1 = new EightPuzzle(new File("in.txt"),"h1"); //solve puzzle with heuristic 1 and save it in pathH1 ArrayList<EightPuzzle> pathH1 = p1.solvePuzzle();   System.out.println("Solving with heuristic h1: \n"); final int SIZEH1 = pathH1.size(); for(int i = 0; i < SIZEH1;i++)//print pathH1 { System.out.println("Step " + i + ":"); System.out.println(pathH1.get(i)); } //EightPuzzle for h2 EightPuzzle p2 = new EightPuzzle(new File("in.txt"),"h2"); //solve puzzle with heuristic 2 and save it in pathH2 ArrayList<EightPuzzle> pathH2 = p2.solvePuzzle();   System.out.println("\nSolving with heurstic h2: \n"); final int SIZEH2 = pathH2.size(); for(int i = 0; i < SIZEH2; i++)//print pathH2 { System.out.println("Step "+ i + ":"); System.out.println(pathH2.get(i)); } //write the results to out.txt EightPuzzle.writeResultsToFile("out.txt", pathH1,pathH2); }   /* Writes the results for heuristics 1 and 2 to a textfile specified by the * string file. */ public static void writeResultsToFile(String file, ArrayList<EightPuzzle> pathH1,ArrayList<EightPuzzle> pathH2) { try { BufferedWriter out = new BufferedWriter(new FileWriter(file)); final int SIZEH1 = pathH1.size(); final int SIZEH2 = pathH2.size(); out.write("Solving with heuristic h1: \n\n"); for(int i = 0;i < SIZEH1;i++)//write h1 results to file { out.write("Step " + i + ":\n"); out.write(pathH1.get(i) + "\n"); } out.write("\nSolving with heuristic h2: \n\n"); for(int i = 0;i < SIZEH2;i++)//write h2 results to file { out.write("Step " + i + ":\n"); out.write(pathH2.get(i) + "\n"); } out.close();//closed the buffer }catch(IOException E) { E.printStackTrace(); } }   /*returns a string representation of the puzzle's initial state and goal state from a textfile. */ public String buildPuzzle(File in) { //for building a string to ouput all at once StringBuilder sb = new StringBuilder(); try//buffered reader reads one line at a time { BufferedReader reader = new BufferedReader(new FileReader(in)); try { String line = null; while((line = reader.readLine()) != null) { sb.append(line); sb.append(System.getProperty("line.separator")); } } finally{reader.close();}//close input stream } catch(IOException E)//if file not found { E.printStackTrace(); } return sb.toString(); }   /* * Initializes the char 2-d array puzzle and goal. The string "puzzles" * contains the initial state, which is initialized to puzzle array, and * the goal state is separated by a blank line and is initialized to the * goal array */ public void initialize(String puzzles) { CharacterIterator iter = new StringCharacterIterator(puzzles); int row = 0;//row index for puzzle and goal int column = 0;//column index for puzzle and goal char c; //stop iterating when row and column is equal to 3 so we can assign goal //after done with puzzle assignment for(c = iter.first();(row!=3&& column !=3);c=iter.next()) { //if c is a digit or 'B', save it in puzzle if(Character.isDigit(c) || c == 'B') { this.puzzle[row][column] = c; if(column<2) column++; else { row++; column = 0;//reset column, new line } } } row=column=0;//reset row and column to zero for(c = iter.next();(row!=3&&column!=3);c=iter.next()) { //if c is a digit or 'B', save it in goal if(Character.isDigit(c) || c == 'B') { this.goal[row][column] = c; if(column < 2) column++; else { row++; column = 0;//reset column, new line } } } }   /* Find the possible moves for the current state of the puzzle, finds the * row and column indices of 'B' in the EightPuzzle and adds the * elements at compatible positions that can be swapped with 'B' to the * moves member. */ public void getPossibleMoves() { //row and column index of 'B' in puzzle int row=0; int column=0; //find index of 'B' in for(int i = 0; i < 3;i++) for(int j = 0; j < 3; j++) { if(puzzle[i][j] == 'B') { row = i; column = j; break;//break out of loop, found 'B' }   } //if 'B' is at [0][0], these are the two characters(digits) that it //can be switched with if(row == 0 && column == 0) { moves.add(puzzle[1][0]); moves.add(puzzle[0][1]); } else if(row == 0 && column == 1) { moves.add(puzzle[0][0]); moves.add(puzzle[0][2]); moves.add(puzzle[1][1]); } else if(row == 0 && column == 2) { moves.add(puzzle[0][1]); moves.add(puzzle[1][2]); } else if(row == 1 && column == 0) { moves.add(puzzle[0][0]); moves.add(puzzle[1][1]); moves.add(puzzle[2][0]); } else if(row == 1 && column == 1) { moves.add(puzzle[1][0]); moves.add(puzzle[0][1]); moves.add(puzzle[1][2]); moves.add(puzzle[2][1]); } else if(row == 1 && column == 2) { moves.add(puzzle[1][1]); moves.add(puzzle[0][2]); moves.add(puzzle[2][2]); } else if(row == 2 && column == 0) { moves.add(puzzle[1][0]); moves.add(puzzle[2][1]); } else if(row == 2 && column == 1) { moves.add(puzzle[2][0]); moves.add(puzzle[1][1]); moves.add(puzzle[2][2]); } else if(row == 2 && column == 2) { moves.add(puzzle[2][1]); moves.add(puzzle[1][2]); } }   //returns string representation of the puzzle @Override public String toString() { //use to append each object before returning string StringBuilder sb = new StringBuilder(); for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) { sb.append(puzzle[i][j]); if(j==2)sb.append("\n");//end of line add a newline character } return sb.toString(); }   /* heursitic1() defines the heursitic for the 8 puzzle. It returns how many * misplaced characters are in the 8 puzzle. */ public int heuristic1(char[][] state) { int count = 0; for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) { if(state[i][j] != goal[i][j])//if the character is misplaced count++; } return count; }   /*Returns the sum of the manhattan distance of each misplaced character. *///have not checked if this works public int heuristic2(char [][] state) { //sum will be sum of manhattan distances of all misplaced elements int sum = 0; for(int i = 0; i < 3; i++)//for loops to find a misplaced element for(int j = 0; j < 3; j++) { if(state[i][j]!=goal[i][j]) { //for loops for manhattan distance computation for(int m = 0; m < 3; m++) for(int n = 0; n < 3; n++) { if(state[i][j] == goal[m][n]) { sum += (Math.abs((m-i)) +Math.abs((n-j))); } } } } return sum; }   /* swaps the 'B' element of the EightPuzzle with c if c is in range '1'-'8'. * finds the row and column indice's of 'B' and c in the puzzle and swaps * the two. */ private EightPuzzle swap(char c) { EightPuzzle p = new EightPuzzle(this);   //check if in range if((Character.digit(c, 10) > 0) && (Character.digit(c,10) <9)) { //x is location of row of c, y is column of c, m is row of 'B', //and n is column of 'B' int x,y,m,n; x = y = m = n = 0; for(int i = 0; i < 3; i++)//find 'B' and c for(int j = 0; j < 3; j++) { if(p.getPuzzle()[i][j] == 'B') { m = i; n = j; } if(p.getPuzzle()[i][j] == c) { x = i; y = j; } } //found positions of 'B' and c, so now we swap p.puzzle[m][n] = c; p.puzzle[x][y] = 'B';   } else System.out.println("Illegal move, \'" + c +"\' is out of range!"); return p; }   /* Check if the current state is the goal state. * Checks each element to see if it matches goal[row][column] * if one element does not match, it returns false immediately, * if all match it returns true. */ public boolean goalCheck() { for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) { if(puzzle[i][j] != goal[i][j]) return false; } return true; }   /* solvePuzzle(String heuristic), solves the EightPuzzle using the A* * search algorithm with the heuristic denoted by the string passed in. * open is an ArrayList for the nodes that haven't been examined. closed * is an ArrayList for the nodes that have been examined. path holds all of * the nodes stored in order, so the path can be returned as the solution * to the EightPuzzle. the initial state is added to the open list. while * open isn't empty, items are dequeued from the sorted open list. open is * sorted by increasing heursitic values, and sorted by the method defined * by the heuristic passed in. The node examined is added to path, it is * tested to see if it is the goal state, if so path is returned. Otherwise, * The examined node is added to the closed list, the neighbor nodes are * added to the frontier with getNeighborNodes(). gcost is updated because * we are at a new level in the frontier. this is updated with * node.getData().puzzle and node.getData().moves so the program will not * use the moves and puzzle from the initial state. if the child node is in * the open or closed list with a greater cost than gcost, the cost is * updated in open or closed list. If the child is not in either list, it * is added to the open list and the while loop continues until we find a * solution or the open list runs out. */ public ArrayList<EightPuzzle> solvePuzzle() { //Nodes that haven't been examined yet ArrayList<Node<EightPuzzle>> open = new ArrayList<Node<EightPuzzle>>(); //Nodes that have been examined ArrayList<Node<EightPuzzle>> closed = new ArrayList <Node<EightPuzzle>>(); //Nodes that have been explored, will contain path to goal ArrayList<EightPuzzle> path = new ArrayList<EightPuzzle>(); //keep track of how far down tree we are for comparing gcost's of nodes int gcost = 0; //add the root node to the open ArrayList open.add(frontier.getRoot());   while(!open.isEmpty()) { //sort by best(lowest cost) e(n) = g(n)+h(n) open = sort(open); Node<EightPuzzle> node = new Node<EightPuzzle> (new EightPuzzle(open.get(0).getData())); //this level is STEPCOST + node's gcost //gcost = STEPCOST + node.getgcost(); this.puzzle = node.getData().puzzle;//update this this.moves = node.getData().getMoves();//update this open.remove(0); path.add(node.getData());//keep track of nodes visited in order closed.add(node);//node has been visited //check if we are at the goal if(node.getData().goalCheck()) return path; else {   node.getData().getNeighborNodes(node,open,closed); //this level is STEPCOST + node's gcost //gcost = STEPCOST + node.getgcost(); final int SIZE = node.getNeighbors().size(); for(int i = 0; i < SIZE;i++) {     //if node in the open list with greater cost, update it //with the lower cost inListWithGreaterCost(open,node.getNeighbors().get(i)); //if it is in neither list, add it to open //if node in the closed list with greater cost, update it //with the lower cost inListWithGreaterCost(closed,node.getNeighbors().get(i));   if(!in(open,node.getNeighbors().get(i)) && !in(closed, node.getNeighbors().get(i))) open.add(node.getNeighbors().get(i)); } } } return path; }   /* in() checks if node is in the ArrayList list. Each individual Node in the * list is checked by counting how many elements are the same as node for * that node in the list. If the count is 9, which means all elements are * the same, in returns true, otherwise we keep going until count = 9 or * the list runs out and in returns false when the list runs out because no * match */ private boolean in(ArrayList<Node <EightPuzzle>> list, Node<EightPuzzle> node) { int count = 0; final int SIZE = list.size(); for(int i = 0; i < SIZE;i++) {//check if this element of list is equal to node for(int j = 0; j < 3; j++) for(int k = 0; k < 3; k++) if(list.get(i).getData().puzzle[j][k] == node.getData().puzzle[j][k]) count++; if(count == 9)//the node is in list return true; }//if not in list return false; }   /* inListWithGreaterCost() starts out like in() by checking to see if it * is in list. If it is in the list the index is saved and the node at that * index's gcost is compared to the gcost passed in. If it is less than the * one passed in it is updated with that value and it's parent is updated * and is added to the frontier with node as the parent. */ private void inListWithGreaterCost(ArrayList <Node<EightPuzzle>> list , Node<EightPuzzle> node) { int index = -1;//will be index of node in list after it is found final int SIZE = list.size(); for(int i = 0;i < SIZE;i++) {//check if this member is in the list first, just like in int count = 0; for(int j = 0 ; j < 3; j++) for(int k = 0; k < 3; k++) { if(list.get(i).getData().puzzle[j][k] == node.getData().puzzle[j][k]) count++; } if(count == 9) {//only difference between in and first part of this function index = i; break; } } if(index == -1)//not found in list return; //if gcost passed in is better than the gcost in the found node //update the gcost of the node in the list with gcost else if(node.getgcost() > list.get(index).getgcost()) { //remove node from current parent node.setgcost(list.get(index).getgcost()); list.set(index,node); //list.remove(index);   //list.get(index).getParent().getNeighbors().remove(list.get(index)); //list.get(index).setgcost(gcost);//update gcost of node //list.get(index).setParent(node.getParent());//change the parent to node //append list.get(index) to frontier //frontier.append(node.getParent(),list.get(index)); } return; }   /* sort() sorts list in order of increasing e(n). e(n) = h(n) + g(n). * sort's behavior depends on the heuristic string, if "h1", heuristic1() * is used to sort the list. If "h2", heuristic2() is used to sort the list. * This is a bubblesort method. */ public ArrayList<Node<EightPuzzle>> sort(ArrayList<Node<EightPuzzle>> list) {   boolean swapped = false; do { swapped = false; final int SIZE = list.size(); for(int i = 0; i < SIZE-1;i++) {//if(e(ni) > e(ni+1) swap them if((list.get(i).getData().getHeuristic() + list.get(i).getgcost()) > (list.get(i+1).getData().getHeuristic() + list.get(i+1).getgcost())) { //swap the two members that are out of place Node<EightPuzzle> temp = new Node<EightPuzzle> (new EightPuzzle(list.get(i).getData())); list.set(i, list.get(i+1)); list.set(i+1,temp);//.setData(new EightPuzzle(temp)); swapped = true; }//else if it is equal, deepest node wins else if((list.get(i).getData().getHeuristic() + list.get(i).getgcost()) == (list.get(i+1).getData().getHeuristic() + list.get(i+1).getgcost())) { if(list.get(i).getgcost() < list.get(i+1).getgcost()) { //swap the two members that are out of place Node<EightPuzzle> temp = new Node<EightPuzzle> (new EightPuzzle(list.get(i).getData())); list.set(i, list.get(i+1)); //list.get(i).setData(new EightPuzzle //(list.get(i+1).getData())); list.set(i+1,temp);//.setData(new EightPuzzle(temp)); swapped = true; } } } }while(swapped); return list; } /* getNeighborNodes() adds the neighbor nodes of node to the frontier(tree). * It is done by traversing the moves element of the EightPuzzle contained * in node and creating a new EightPuzzle by swapping the blank with the * character corresponding to the index in moves. */ private void getNeighborNodes(Node<EightPuzzle> node, ArrayList<Node<EightPuzzle>> open, ArrayList<Node<EightPuzzle>> closed) { final int SIZE = node.getData().getMoves().size(); for(int i = 0; i < SIZE;i++)//traverse node.getData().getMoves { //make a new EightPuzzle by swapping the blank('B') with //the corresponding character in the moves ArrayList inside the //node's EightPuzzle member. EightPuzzle p = new EightPuzzle (swap(node.getData().getMoves().get(i))); //Make a node for the new EightPuzzle Node <EightPuzzle> child = new Node<EightPuzzle>(p);   //clear moves because the moves from node's EightPuzzle are copied //to the new EightPuzzle child.getData().moves.clear(); child.getData().getPossibleMoves();//get the available moves if(!in(open,child) && !in(closed,child)){ child.setgcost(STEPCOST + node.getgcost());//set it's gcost frontier.append(node, child);//add to the frontier } } } } import java.util.*; public class Node <E>{ private ArrayList<Node> neighborNodes;//children of this node private E data;//data inside node private Node<E> parent;//parent of this   /*gcost is the cost to get to the current level in the tree, must be assigned it's "real value" as tree is constructed*/ private int gcost = 0; /*assign Node's data value with value passed in constructor we don't set gcost, it could be 1 + parent.gcost, but for root, this would not work*/ public Node(E data) { neighborNodes = new ArrayList<Node>(); this.data=data; }   /*No data assignment, allocates memory for neighborNodes ArrayList*/ public Node() { neighborNodes = new ArrayList<Node>(); }   //accessor method for neighborNodes ArrayList. public List<Node> getNeighbors() { return this.neighborNodes; }   //accessor method for gcost public int getgcost() { return gcost; }   //method for setting gcost member public void setgcost(int n) { gcost = n; }   /*adds n to the neighborNodes ArrayList and sets n's parent to this.*/ public void append(Node<E> n) { n.parent = this; neighborNodes.add(n); }   /*Accessor method for the data member*/ public E getData() { return data; }   /*method for setting the data for the Node*/ public void setData(E data) { this.data = data; }   //accessor method for the parent member public Node<E> getParent() { return this.parent; }   //changes the parent of the current node public void setParent(Node<E> parent) { //check if it has a parent, if so remove it from the parents' //neighborNodes ArrayList if(this.parent != null) parent.neighborNodes.remove(this); this.parent = parent; //add this to make it available in the parents neighborNode ArrayList parent.neighborNodes.add(this); }   } import java.util.*; public class Tree <E> { private Node<E> root;   //constructor: assigns root with data public Tree(E data) { root=new Node(data); } public Tree(){}//empty constructor, no data assignment   //accessor method to return the root of the Tree public Node<E> getRoot() { return root; }   /* Finds the parent by comparing the toString() value of parent and * the current Node in the frontier and making sure it is the same Node by * comparing the gcost of the parent to the node. If it is, the child is * appended to the parent. The search used is Breadth first search */ public void append(Node<E> parent, Node <E> child) { //Node<E> temp = root; ArrayList<Node<E>> frontier = new ArrayList<Node<E>>(); frontier.add(root); while(!frontier.isEmpty()) { Node<E> N = frontier.get(0);//get a Node frontier.remove(0); if(N.getData().toString().equals(parent.getData().toString()) && N.getgcost() == parent.getgcost())//is this the parent? { parent.append(child);//if yes add child break;//no more work to be done! } final int SIZE = N.getNeighbors().size(); for(int i = 0; i < SIZE;i++)//get neigbors frontier.add(N.getNeighbors().get(i));   } } }```