Jump to content
• Advertisement

# A* with 8 Puzzle Problem

This topic is 5012 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

## Recommended Posts

Firstly if you are unfamiliar with the 8 puzzle problem take a look at http://www.permadi.com/java/puzzle8/ I have decided to go with using the manhattan distance as my heurisitc, is this the best approach? Secondly what should I do if two states come out with the same value for the heuristic? How do should the program decide which path to follow? At the moment my program is always just following the first state, however this does not always lead to the optimal solution.

#### Share this post

##### Share on other sites
Advertisement
The optimality of the solution doesn't depend on the order in which you consider moves with equal heuristic value. As long as your heuristic never overestimates the number of moves left, you should get optimal solutions.

The Manhattan distance is a conservative estimate of the number of moves left, therefore you should be getting optimal solutions. I would say there is a mistake somewhere in your program.

#### Share this post

##### Share on other sites
Quote:
 Original post by Tech19Firstly if you are unfamiliar with the 8 puzzle problem take a look at http://www.permadi.com/java/puzzle8/I have decided to go with using the manhattan distance as my heurisitc, is this the best approach? Secondly what should I do if two states come out with the same value for the heuristic? How do should the program decide which path to follow? At the moment my program is always just following the first state, however this does not always lead to the optimal solution.

Your heuristic must be admissible, in that it won't ever over estimate the cost of reaching your goal node. If this is the case, A* will always find an optimal solution so you must be doing something wrong. As for picking which state to go to, if two or more states have exactly the same score with your heuristic, there isn't any logical reason to pick one over the other so just do what's easiest.

#### Share this post

##### Share on other sites
The manhatten distance is the standard heuristic used for this sort of problem. I'm sure other more interesting heuristics exist, but they are probably a lot more computationaly expensive, and not much better at evaluating states.

The total cost of a state consists of the cost of getting to that state plus the estimated cost of getting to the solution state (the heuristic). If two states have the exact same cost, then it doesn't really matter which one you investigate first as you have no way of knowing which is actually superior. Whichever state you expand first you are still gauranteed to get the optimum solution if your heuristic underestimates the true cost of a state.

If you're not getting the optimal solution then you havn't implemented the A* search properly.

#### Share this post

##### Share on other sites
How are the closed and open lists best organised in an A* search of the 8-puzzle?

#### Share this post

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
2. 2
3. 3
Rutin
22
4. 4
frob
17
5. 5
• Advertisement

• 9
• 33
• 13
• 13
• 10
• ### Forum Statistics

• Total Topics
632580
• Total Posts
3007194

×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!