• 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

need help figurng out what is wrong with my A* search algorithm for an eight puzzle

 
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hello, this is my first post!
I am coding an 8 puzzle program to solve any instance of the eight puzzle. An input file for this program contains an initial state and a goal state separated by a blank line. 'B' Stands for the blank in the puzzle. Top is initial bottom is goal state. For this particular instance the algorithm does not work:
321
4B6
875

123
456
B78

There are many others it does not work for, this is just one. I find one thing weird is that when checking the open list for a node with the same state with a greater gcost value(level in the tree), it never has a greater cost and never gets updated with a lesser cost. Not sure if this is a problem though. The only code that you most likely have to look at is solvePuzzle() and inListWithGreaterCost(). inListWithGreaterCost() checks a list(open) to see if there is a Node with the same state with a better cost than its current level. If the gcost of the node in the list is lower, the new Node updated with the lesser cost and the old one is removed. The open list is sorted by heuristic + gcost(level of tree) on every iteration of A* algorithm to prioritize open list. Can someone please help me out, I am very stuck as it seems that i am following the algorithm's pseudocode perfectly(I have found many versions). Here is most of the code for the EightPuzzle class, it is lengthy but you will most likely have to look at those two functions i mentioned. I just wanted to post all so you will have a better reference. I'm just not so sure what is wrong with my code that is causing me to repeat states and the loop runs infinitely, can someone please help point out what is wrong? I also posted the tree and node classes for reference,Thanks!
 
Bartender
Posts: 2700
IntelliJ IDE Opera
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
First of all welcome to JavaRanch. Please read our HowToAskQuestionsOnJavaRanch FAQ. Because none of us is going to read and debug almost 800 lines of code. Try to localize the problem and then we'll try to help you.
 
Badri Verma
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Wouter Oet wrote:First of all welcome to JavaRanch. Please read our HowToAskQuestionsOnJavaRanch FAQ. Because none of us is going to read and debug almost 800 lines of code. Try to localize the problem and then we'll try to help you.


I did localize the problem, i put all 800 lines of code just incase anyone wants to run it as well as help me debug it. I said in my initial post that the problem is in solvePuzzle() and in inListWithGreaterCost(). My problem is with updating the cost of the child node if it is in the open or closed lists i believe. I think I am not understanding that part of the A* algorithm, because I think I am following A* perfect but nothing is working. States are repeating infinitely and I am not sure how to fix it.
 
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
As you've been told, no one is likely to wade through that much code, but one guess would be here:

It is usually not a good idea to compare reference types with ==, you're more likely to get the results you expect if you use the equals() method.
 
Badri Verma
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Garrett Rowe wrote:As you've been told, no one is likely to wade through that much code, but one guess would be here:

It is usually not a good idea to compare reference types with ==, you're more likely to get the results you expect if you use the equals() method.


i am comparing characters, not a reference type, thanks.
 
Bartender
Posts: 1561
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Badri Verma wrote:I did localize the problem, i put all 800 lines of code just incase anyone wants to run it as well as help me debug it.


This is a noble effort, but regardless, I second the reply that the daunting amount of code posted will prevent many from taking the time to read it or search for your localization. One useful tool that may help you with this problem (and would likely help us help you) is the Short, Self Contained, Correct (Compilable), Example or SSCCE where you post a smaller amount of code that compiles and demonstrates your problem and has no extraneous code. It's well worth the look.

Best of luck in this endeavor!
 
reply
    Bookmark Topic Watch Topic
  • New Topic