Solve 8-puzzle game

c++ algorithm distance puzzle sliding-tile-puzzle
pluralism picture pluralism · Mar 26, 2013 · Viewed 7.2k times · Source

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):

enter image description here

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

MvG picture MvG · Mar 26, 2013

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.

Related questions

Finding maximum distance between (x,y) coordinates

Im trying to calculate the maximum manhattan distance of a large 2D input , the inputs are consisting of (x, y)s and what I want to do is to calculate the maximum distance between those coordinates In less than O(…

Read More
How to replace all occurrences of a character in string?

What is the effective way to replace all occurrences of a character with another character in std::string?

Read More
What is the most effective way for float and double comparison?

What would be the most efficient way to compare two double or two float values? Simply doing this is not correct: bool CompareDoubles1 (double A, double B) { return A == B; } But something like: bool CompareDoubles2 (double A, double B) { diff = …

Read More