I am developing an
8-puzzle game and I am looking for a solution to 8-puzzle problem using the `A* Algorithm`. I found
this project on the internet. Please see the files - `proj1` and `EightPuzzle`. The proj1 contains the entry point for the program(the `main()` function) and EightPuzzle describes a particular state of the puzzle. Each state is an object of the 8-puzzle.
I feel that there is nothing wrong in the logic. But it loops forever for these two inputs that I have tried :
`{8,2,7,5,1,6,3,0,4}` and
`{3,1,6,8,4,5,7,2,0}`. Both of them are valid input states. What is wrong with the code?
----------
Note
- For better viewing copy the code in a Notepad++ or some other text
editor(which has the capability to recognize
java source file)
because there are lot of comments in the code.
- Since A* requires a heuristic, they have provided the option of using
manhattan distance and a heuristic that calculates the number of
misplaced tiles. And to ensure that the best heuristic is executed
first, they have implemented a `PriorityQueue`. The `compareTo()`
function is implemented in the `EightPuzzle` class.
- The input to the program can be changed by changing the value of `p1d` in the `main()` function of `proj1` class.
- The reason I am telling that there exists solution for the two my above inputs is because the
applet here solves them. Please ensure that you select 8-puzzle from the options in the applet.
This is the piece of code(in proj1-astar()) where the whole looping takes place
openset is the PriorityQueue which contains the unexpanded states.
closedset is the linked list that contains already expanded states. The while loop because of which infinite looping happens is the one
EDIT1I gave this input `{0,5,7,6,8,1,2,4,3}`. It took about `10 seconds` and gave a result with **26 moves**. But the applet gave a result with `24 moves` in `0.0001 seconds` with `A*`.
EDIT2
While debugging I noticed that as nodes are expanded, the new nodes, after sometime, all have a heuristic - `f_n` as `11` or `12`. They never seem to decrease. So after sometime all the states in the `PriorityQueue(openset)` have a heuristic of 11 or 12. So there is not much to choose from, to which node to expand. As the least is 11 and the highest is 12. Is this normal?
For quick reference I have pasted the the two classes without the comments :
EightPuzzle
-----------
proj1
-----