Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Why does this 8-puzzle algorithm/code execute infinitely?

Greenhorn
Posts: 5
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

EDIT1
I 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
-----

fred rosenberger
lowercase baba
Bartender
Posts: 12127
30
I have cleaned up this thread. Please keep all replies civil, polite, and professional.

fred rosenberger
lowercase baba
Bartender
Posts: 12127
30

First, welcome to the Ranch. We're glad you came by, and hope you stay.

However, let me point you to our FAQ on how to ask questions here. Generally speaking, posting 300+ lines of code and asking "What's wrong with this?" won't get you much help.

Our mission is in teaching and helping you. If you ask a specific, focused question, you will more likely get some useful feedback. You don't even indicate where the code is stuck - I count at least five while-loops.

The easier you make it for someone to help you, the more likely you are to get it.

Greenhorn
Posts: 5

First, welcome to the Ranch. We're glad you came by, and hope you stay.

However, let me point you to our FAQ on how to ask questions here. Generally speaking, posting 300+ lines of code and asking "What's wrong with this?" won't get you much help.

Our mission is in teaching and helping you. If you ask a specific, focused question, you will more likely get some useful feedback. You don't even indicate where the code is stuck - I count at least five while-loops.

The easier you make it for someone to help you, the more likely you are to get it.

I have added the snippet where the whole looping is taking place. Please see that. Do tell me if you need anything else. Meanwhile I am also trying to find out what is wrong here. Thanks.

Winston Gutkowski
Bartender
Posts: 10417
63
Ashwin Bhaskar wrote:I have added the snippet where the whole looping is taking place. Please see that.

Erm...and which one would that be? You shown us three: all, I would say, too big.

First of all: what is an "Eight-puzzle"? My original thought was that it was a program containing eight puzzles, but that appears to be wrong; and your original link contains no help.

Please be specific and TellTheDetails (←click); otherwise, as Fred said, this smacks of a "Help! I've copied someone else's code and now it doesn't work" question; and I hate to say, but you're unlikely to get too many offers of help to solve it.

Winston

Greenhorn
Posts: 5
Winston Gutkowski wrote:
Ashwin Bhaskar wrote:I have added the snippet where the whole looping is taking place. Please see that.

Erm...and which one would that be? You shown us three: all, I would say, too big.

First of all: what is an "Eight-puzzle"? My original thought was that it was a program containing eight puzzles, but that appears to be wrong; and your original link contains no help.

Please be specific and TellTheDetails (←click); otherwise, as Fred said, this smacks of a "Help! I've copied someone else's code and now it doesn't work" question; and I hate to say, but you're unlikely to get too many offers of help to solve it.

Winston

I have given the link to what an 8-puzzle is and all the details regarding valid input states and goal states is present in the link. And I have also the specified the specific while loop.

Greenhorn
Posts: 5
Finally found out the cause of the problem.
This is the condition that is used to check if a node is present in closedset

A linkedlist(closedset) executes the contains() by calling the equals() of the class, in this case EightPuzzle. The equals function in EightPuzzle is defined as follows

But this function was never called because if you want to override the equals() of Object class the correct signature should be.
One more change required - comment the first two lines of the equals()

I got the answer. But the code still takes 25-30 seconds for some inputs. This is not expected with A*. If someone has an idea, how to improve the performance. please do tell me. Thanks