File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Game Development and the fly likes Why does this 8-puzzle algorithm/code execute infinitely? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Game Development
Bookmark "Why does this 8-puzzle algorithm/code execute infinitely?" Watch "Why does this 8-puzzle algorithm/code execute infinitely?" New topic
Author

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

Ashwin Bhaskar
Greenhorn

Joined: Oct 25, 2012
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

Joined: Oct 02, 2003
Posts: 10916
    
  12

I have cleaned up this thread. Please keep all replies civil, polite, and professional.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10916
    
  12

Ashwin Bhaskar,

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.
Ashwin Bhaskar
Greenhorn

Joined: Oct 25, 2012
Posts: 5
fred rosenberger wrote:Ashwin Bhaskar,

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

Joined: Mar 17, 2011
Posts: 7075
    
  16

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


Isn't it funny how there's always time and money enough to do it WRONG?
Artlicles by Winston can be found here
Ashwin Bhaskar
Greenhorn

Joined: Oct 25, 2012
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.
Ashwin Bhaskar
Greenhorn

Joined: Oct 25, 2012
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
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Why does this 8-puzzle algorithm/code execute infinitely?
 
Similar Threads
Head first Java - Chapter 4 Pool Puzzle p.91
Puzzle 4
need help figurng out what is wrong with my A* search algorithm for an eight puzzle
June Newsletter Puzzle
SoDuko puzzle