Solve 8-puzzle game

Question

I'm trying to code a 8-puzzle game solver in C++, but I'm having a lot of problems while doing it. The program is currently working, but it takes too much steps to solve the puzzle. I mean, sometimes it can find the optimal solution, sometimes it takes as much as 400 steps to solve it. My main doubt is the following.. Imagine I have this diagram(this is just a draft):

I'm using Manhattan Distance as the heuristic function. After the first step we have two states where f(n)=5, so I expanded the tree. After expanding I still got two states where f(n)=2. Here is my doubt.. Do I still need to expand the tree till I got a unique lowest f(n)?

Thanks in advance!

Answer 1

Do I still need to expand the tree

You can't solve this puzzle greedily: always taking the branch with lower heuristic value will not lead you to the final solution every time. So you have to keep the other states around for backtracking. The order in which you expand them, whether simple BFS or heuristics-based A*, is up to you.

Answer 2

here you can find processing applet that uses A* algorithm to find the shortest path from an initial state to the goal state. The code in the applet is available free.