Complexity of 8 Puzzle

Posted on 2006-03-25
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.
Question by:meinnit
    LVL 10

    Assisted Solution


    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.
    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

    Featured Post

    Better Security Awareness With Threat Intelligence

    See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

    Join & Write a Comment

    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.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    17 Experts available now in Live!

    Get 1:1 Help Now