File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

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

 
Badri Verma
Greenhorn
Posts: 3
  • 0
  • Mark post as helpful
  • send pies
  • 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!
 
Wouter Oet
Saloon Keeper
Posts: 2700
IntelliJ IDE Opera
  • 0
  • Mark post as helpful
  • send pies
  • 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
  • 0
  • Mark post as helpful
  • send pies
  • 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.
 
Garrett Rowe
Ranch Hand
Posts: 1296
  • 0
  • Mark post as helpful
  • send pies
  • 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
  • 0
  • Mark post as helpful
  • send pies
  • 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.
 
pete stein
Bartender
Posts: 1561
  • 0
  • Mark post as helpful
  • send pies
  • 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!
 
I agree. Here's the link: http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic