# Complexity of 8 Puzzle

I'm looking for a detailed explanation of the complexity of the 8 puzzle problem. I'm guessing A* would be the choice of search algorithm to solve this.
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Author Commented:
Thanks for those, I did come across those when I searched the net. They don't state the overall complexity in Big O notation.
0
Commented:
Using breadth-first, the time complexity of the 8-puzzle problem will be O (b^d), where b is the branching factor of the search tree (the maximum number of next states from any given state), and d is the depth of the solution (number of steps to reach the goal state). Using depth-first search, the complexity is O (b^m), where b is the branching factor, and m is the maximum tree depth.

Given an accurate heuristic, the A* search algorithm will be the fastest to find a solution.

_______________

Nayer Naguib
0

Experts Exchange Solution brought to you by