File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes need help figurng out what is wrong with my A* search algorithm for an eight puzzle Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Java 8 in Action this week in the Java 8 forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "need help figurng out what is wrong with my A* search algorithm for an eight puzzle" Watch "need help figurng out what is wrong with my A* search algorithm for an eight puzzle" New topic
Author

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

Badri Verma
Greenhorn

Joined: Mar 28, 2010
Posts: 3
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

Joined: Oct 25, 2008
Posts: 2700

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.


"Any fool can write code that a computer can understand. Good programmers write code that humans can understand." --- Martin Fowler
Please correct my English.
Badri Verma
Greenhorn

Joined: Mar 28, 2010
Posts: 3
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

Joined: Jan 17, 2006
Posts: 1296
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.


Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
Badri Verma
Greenhorn

Joined: Mar 28, 2010
Posts: 3
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

Joined: Feb 23, 2007
Posts: 1561
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
 
subject: need help figurng out what is wrong with my A* search algorithm for an eight puzzle
 
Similar Threads
August Newsletter Puzzle
In Dire Need of Data Structure Advice
SoDuko puzzle
July Newsletter Puzzle (Maze Solver)
June Newsletter Puzzle