Solving The 8 Puzzle With A* Algorithm

Question

I would like to solve/implement the 8 puzzle problem using the A* algorithm in Java. Am asking if someone can help me by explaining to me the steps i must follow to solve it. I have read on the net how the A* works but i don't know how to begin the implementation in Java.

I will be very grateful if you guys can help me and give me the guidelines so that i can implement it myself in Java. I really want to do it to be able to understand it, so i just need the guidelines to start.

---

I will use priority queues and will read the initial configuration from a text file which looks like for example this:

4  3  6
1  2  5
7  8  

Pointers to other sites for more explanation/tutorials are welcome.

Answer 1

I'd begin with deciding how you want to represent the game board states, then implement the operators (eg. move (blank) tile up, move (blank) tile down, ...). Typically you will have a data structure to represent the open list (ie. those states discovered but as yet unexplored (ie. compared with goal state) and another for the closed list (ie. those states discovered and explored and found not to be the goal state). You seed the open list with the starting state, and repeatedly take the "next" state to be explored from the open list, apply the operators to it to generate new possible states and so on ...

There is a tutorial I prepared many years ago at:

http://www.cs.rmit.edu.au/AI-Search/

It is far from the definitive word on state space searching though, it is simply an educational tool for those brand new to the concept.