• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

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

 
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
-----


 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have cleaned up this thread. Please keep all replies civil, polite, and professional.
 
fred rosenberger
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 5
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Ashwin Bhaskar
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 5
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Joel Salatin has signs on his property that say "Trespassers will be Impressed!" Impressive tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic