• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1994
  • Last Modified:

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.
2 Solutions
meinnitAuthor 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.
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now