posted 14 years ago
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!