Solved

# Complexity of 8 Puzzle

Posted on 2006-03-25
1,286 Views
Last Modified: 2008-01-09
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.
0
Question by:meinnit
3 Comments

LVL 10

Assisted Solution

0

Author Comment

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

LVL 14

Accepted Solution

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

## Join & Write a Comment Already a member? Login.

### Suggested Solutions

Displaying an arrayList in a listView using the default adapter is rarely the best solution. To get full control of your display data, and to be able to refresh it after editing, requires the use of a custom adapter.
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

#### 734 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

#### Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!