A* Algorithm 8-puzzle

Question

I have read many pseudo code for the A* algorithm, but neither of them actually explain how to output the solution. I believe I understand the concept of using a priority queue for the not yet visited and a has table for the explored, but when I go through the algorithm I don't know at what point to print out the result. Does any one have a pseudo code that actually show how to output the path?

Id really appreciate it. I have been trying to use the algorithm to implement the 8-puzzle problem

Here's my code:

public class Board{

private int[][] squares;
private int f;
private int g;
private int h;

private int size;
private Board parent;

public Board(Board current, Board parent)
{
    this(current);
    g = current.getG();
    h = current.getH();
    f = current.getF();
    this.parent = parent;

}

public void solveH1()
{

    while(!frontier.isEmpty())
    {
        board = frontier.poll();

        ArrayList<Board> successors = new ArrayList<Board>();
        Board b1 = new Board(board.moveDown(),board);
        Board b2 = new Board(board.moveUp(),board);
        Board b3 = new Board(board.moveLeft(),board);
        Board b4 = new Board(board.moveRight(),board);
        if(!b1.equals(board))
            successors.add(b1);
        if(!b2.equals(board))
            successors.add(b2);
        if(!b3.equals(board))
            successors.add(b3);
        if(!b4.equals(board))
            successors.add(b4);
        for(int i=0; i<successors.size(); i++)
        {
            if(successors.get(i).isGoal())
            {
                break;
            }
            int g = board.getG()+1;
            int h = successors.get(i).getH1Cost();
            successors.get(i).setG(g);
            successors.get(i).setH(h);
            successors.get(i).setF(g+h);

            if(frontier.contains(successors.get(i)))
            {
                Iterator<Board> iterator = frontier.iterator();
                Board b = null;
                while(iterator.hasNext())
                {
                    b = iterator.next();
                    if(b.equals(successors.get(i)))
                    {
                        break;
                    }
                }
                if(b.getG() < successors.get(i).getG())
                {
                    break;
                }
            }
            if(exploredSet.contains(successors.get(i)))
            {
                int index = exploredSet.indexOf(successors.get(i));
                if(exploredSet.get(index).getG() < successors.get(i).getG())
                    break;
            }
            else
            {
                frontier.add(successors.get(i));
            }
        }
        exploredSet.add(board);
    }
    printPath();
}
public void printPath()
{

    ArrayList<Board> path = new ArrayList<Board>();
    cursor = board;
    while(cursor.getParent()!=null)
    {
        path.add(cursor);
        cursor = cursor.getParent();
    }
    for(int i=0; i<path.size(); i++)
        System.out.println(path.get(i));
}

for some reason, this just prints one node, and it's bot even the goal. Can anyone tell me what I am missing?

Answer 1

When you push the node onto queue you also save (push) the parent of it, that is, the node you've visited it from.

class NodeWrapper {
 public float cost;
 public Node node;
 public Node parentNode;
 public NodeWrapper(Node node, Node parentNode) {
   this.node = node;
   this.parentNode = parentNode;
 }
}

And then

openQueue.push(new NodeWrapper(neihgbouringNode, currentNode));

And when you reach the end node, you then just trace your way back from it.

List<Node> out = new ArrayList<Node>();
while (currentNode != null) {
   out.add(currentNode.node);
   currentNode = currentNode.parentNode;
}
return out; 

Here's a demo of a A* pathfinder.