Skip to content →

The hardest eight-puzzle instances take 31 moves to solve

I’m sure this information is available elsewhere, but I couldn’t find it with a quick google search — the two hardest 8-puzzle instances are:

 8 6 7
 2 5 4
 3 . 1
 
 6 4 7
 8 5 .
 3 2 1

Both require at least 31 moves to solve. All other instances can be solved in 30 moves or less. (Found using breadth-first graph search, starting at the goal state). Somewhat interestingly, they are not obviously symmetric, but differ only in the locations of the even pieces.

Published in Uncategorized

25 Comments

  1. Mati

    But which is the final state for those puzzles?
    Cause there are two disconnected parts in the search space for this problem.
    Thx!

  2. Jason Wolfe

    Good point. The post was referring to the standard version where the final state is:

    1 2 3
    4 5 6
    7 8 .

  3. mimighost

    I got your blog from google.
    This is indeed a very difficult puzzle, i wrote a python program and using the A* to solve it, and it takes a really long time.
    So, my question is how long does it take for your program to find the answer? Is there any special optimization? I rsearch the web but can’t find many useful information.

    • Jason Wolfe

      There are only (9 !) / 2 = 181,440 reachable states in the 8-puzzle, so you should be able to solve any instance pretty quickly (on the order of seconds or less) even using brute force, with a decently fast implementation. Repeated-state checking (i.e., a closed list) and proper data structures are essential, of course.

  4. solnit

    These two states are the same state really. Let’s take first position.

     8 6 7
     2 5 4
     3 . 1
    

    You can reflect this position about main diagonal.

     8 2 3
     6 5 .
     7 4 1
    

    Then you can rename pieces. More precisely, you can swap pieces 2-4, 3-7 and 6-8. It is because in goal state these pieces are symmetric.

     6 4 7
     8 5 .
     3 2 1
    

    Note that this is second hardest position.
    Now try to do the same two steps for, say, the following position:

    Position A
     1 2 3
     . 5 6
     4 7 8
    

    After reflection:

     1 . 4
     2 5 7
     3 6 8
    

    After renaming pieces 2-4, 3-7 and 6-8:

    Position B
     1 . 2
     4 5 3
     7 8 6
    

    Position A can be solved in three moves: U L L (U means “move piece up”).
    Position B also can be solved in three moves: L U U.
    Moreover, solution to the position B can be obtained by replacing moves U,L,D,R with moves L,U,R,D respectively.
    The following position is self-symmetric:

     . 8 7
     6 5 4
     3 2 1
    

    If you reflect this position and then rename tiles you will return to the same position.

  5. Era Ahmadian

    Hi Solnit
    we are working on an Optimezd Program which is solved 8 puzzle problem with A* algorithm and with OOP methods in C# .
    Our Program Can solve the 31-depth instance easily!
    but i have a question of you?!
    why u said The hardest eight-puzzle instances take 31 moves to solve?how can u prove it?!
    we have of instances that they needs more moves for solving!!!
    and the second question is the reflection instances are the same state with every goals position or just the standard one?
    truly yours,Era

  6. Nihal

    For some reason my BFS algorithm got the first one in 27 states. Ive penned them down as a list.

    [3, 4, 0, 6, 1, 8, 2, 5, 7]
    [3, 4, 8, 6, 1, 0, 2, 5, 7]
    [3, 4, 8, 6, 0, 1, 2, 5, 7]
    [3, 0, 8, 6, 4, 1, 2, 5, 7]
    [0, 3, 8, 6, 4, 1, 2, 5, 7]
    [6, 3, 8, 0, 4, 1, 2, 5, 7]
    [6, 3, 8, 2, 4, 1, 0, 5, 7]
    [6, 3, 8, 2, 4, 1, 5, 0, 7]
    [6, 3, 8, 2, 0, 1, 5, 4, 7]
    [6, 3, 8, 2, 1, 0, 5, 4, 7]
    [6, 3, 0, 2, 1, 8, 5, 4, 7]
    [6, 0, 3, 2, 1, 8, 5, 4, 7]
    [6, 1, 3, 2, 0, 8, 5, 4, 7]
    [6, 1, 3, 0, 2, 8, 5, 4, 7]
    [0, 1, 3, 6, 2, 8, 5, 4, 7]
    [1, 0, 3, 6, 2, 8, 5, 4, 7]
    [1, 2, 3, 6, 0, 8, 5, 4, 7]
    [1, 2, 3, 0, 6, 8, 5, 4, 7]
    [1, 2, 3, 5, 6, 8, 0, 4, 7]
    [1, 2, 3, 5, 6, 8, 4, 0, 7]
    [1, 2, 3, 5, 6, 8, 4, 7, 0]
    [1, 2, 3, 5, 6, 0, 4, 7, 8]
    [1, 2, 3, 5, 0, 6, 4, 7, 8]
    [1, 2, 3, 0, 5, 6, 4, 7, 8]
    [1, 2, 3, 4, 5, 6, 0, 7, 8]
    [1, 2, 3, 4, 5, 6, 7, 0, 8]
    [1, 2, 3, 4, 5, 6, 7, 8, 0]
    27 states in solution

    • Nihal

      sorry my bad. was checking something else -_-

  7. agv

    [[[8, 6, 7] [2, 5, 4] [3, 0, 1] -1]
    [[8, 6, 7] [2, 0, 4] [3, 5, 1] 0]
    [[8, 0, 7] [2, 6, 4] [3, 5, 1] 0]
    [[8, 7, 0] [2, 6, 4] [3, 5, 1] 3]
    [[8, 7, 4] [2, 6, 0] [3, 5, 1] 2]
    [[8, 7, 4] [2, 0, 6] [3, 5, 1] 1]
    [[8, 7, 4] [0, 2, 6] [3, 5, 1] 1]
    [[8, 7, 4] [3, 2, 6] [0, 5, 1] 2]
    [[8, 7, 4] [3, 2, 6] [5, 0, 1] 3]
    [[8, 7, 4] [3, 2, 6] [5, 1, 0] 3]
    [[8, 7, 4] [3, 2, 0] [5, 1, 6] 0]
    [[8, 7, 4] [3, 0, 2] [5, 1, 6] 1]
    [[8, 7, 4] [0, 3, 2] [5, 1, 6] 1]
    [[0, 7, 4] [8, 3, 2] [5, 1, 6] 0]
    [[7, 0, 4] [8, 3, 2] [5, 1, 6] 3]
    [[7, 4, 0] [8, 3, 2] [5, 1, 6] 3]
    [[7, 4, 2] [8, 3, 0] [5, 1, 6] 2]
    [[7, 4, 2] [8, 0, 3] [5, 1, 6] 1]
    [[7, 4, 2] [8, 1, 3] [5, 0, 6] 2]
    [[7, 4, 2] [8, 1, 3] [0, 5, 6] 1]
    [[7, 4, 2] [0, 1, 3] [8, 5, 6] 0]
    [[0, 4, 2] [7, 1, 3] [8, 5, 6] 0]
    [[4, 0, 2] [7, 1, 3] [8, 5, 6] 3]
    [[4, 1, 2] [7, 0, 3] [8, 5, 6] 2]
    [[4, 1, 2] [7, 5, 3] [8, 0, 6] 2]
    [[4, 1, 2] [7, 5, 3] [0, 8, 6] 1]
    [[4, 1, 2] [0, 5, 3] [7, 8, 6] 0]
    [[0, 1, 2] [4, 5, 3] [7, 8, 6] 0]
    [[1, 0, 2] [4, 5, 3] [7, 8, 6] 3]
    [[1, 2, 0] [4, 5, 3] [7, 8, 6] 3]
    [[1, 2, 3] [4, 5, 0] [7, 8, 6] 2]
    [[1, 2, 3] [4, 5, 6] [7, 8, 0] 2]]

  8. agv

    [[[6, 4, 7] [8, 5, 0] [3, 2, 1] -1]
    [[6, 4, 0] [8, 5, 7] [3, 2, 1] 0]
    [[6, 0, 4] [8, 5, 7] [3, 2, 1] 1]
    [[6, 5, 4] [8, 0, 7] [3, 2, 1] 2]
    [[6, 5, 4] [0, 8, 7] [3, 2, 1] 1]
    [[6, 5, 4] [3, 8, 7] [0, 2, 1] 2]
    [[6, 5, 4] [3, 8, 7] [2, 0, 1] 3]
    [[6, 5, 4] [3, 0, 7] [2, 8, 1] 0]
    [[6, 5, 4] [3, 7, 0] [2, 8, 1] 3]
    [[6, 5, 4] [3, 7, 1] [2, 8, 0] 2]
    [[6, 5, 4] [3, 7, 1] [2, 0, 8] 1]
    [[6, 5, 4] [3, 0, 1] [2, 7, 8] 0]
    [[6, 0, 4] [3, 5, 1] [2, 7, 8] 0]
    [[0, 6, 4] [3, 5, 1] [2, 7, 8] 1]
    [[3, 6, 4] [0, 5, 1] [2, 7, 8] 2]
    [[3, 6, 4] [2, 5, 1] [0, 7, 8] 2]
    [[3, 6, 4] [2, 5, 1] [7, 0, 8] 3]
    [[3, 6, 4] [2, 0, 1] [7, 5, 8] 0]
    [[3, 6, 4] [2, 1, 0] [7, 5, 8] 3]
    [[3, 6, 0] [2, 1, 4] [7, 5, 8] 0]
    [[3, 0, 6] [2, 1, 4] [7, 5, 8] 1]
    [[0, 3, 6] [2, 1, 4] [7, 5, 8] 1]
    [[2, 3, 6] [0, 1, 4] [7, 5, 8] 2]
    [[2, 3, 6] [1, 0, 4] [7, 5, 8] 3]
    [[2, 3, 6] [1, 4, 0] [7, 5, 8] 3]
    [[2, 3, 0] [1, 4, 6] [7, 5, 8] 0]
    [[2, 0, 3] [1, 4, 6] [7, 5, 8] 1]
    [[0, 2, 3] [1, 4, 6] [7, 5, 8] 1]
    [[1, 2, 3] [0, 4, 6] [7, 5, 8] 2]
    [[1, 2, 3] [4, 0, 6] [7, 5, 8] 3]
    [[1, 2, 3] [4, 5, 6] [7, 0, 8] 2]
    [[1, 2, 3] [4, 5, 6] [7, 8, 0] 3]]
    با الگوریتم پس گرد 🙂

  9. Carlos

    How many nodes expand your program?,

    since I am trying to run it. however it couldn’t complete 🙁

    Regards!

  10. I solved it, but my algorithm took 32 moves to do it and I don’t know why yet.
    mimighost you have to remove from your frontier when the state is already visited to get better performance.

  11. Nicholas Estrada

    I’m using an iterative Priority Queue with the priority being based on the number of tiles misplaced and mine gets it in 31 moves in significantly less than a second.

    • Ven S

      Can you please send your Python code of how to pass the all 181400 states and capture 31 moves and their solution paths. I got 181440 moves. How do I pass states, capture, moves and solution path and report the largest moves and two starting states. I am using BFS.

  12. swap

    [] + []=8
    + +
    [] – []=6
    = =
    13 8

  13. The first puzzle can be solved in 27 moves and the second one in 25 moves. Perhaps your BFS algorithm was off a bit. I’ve tested this using BFS, DFS, and A*.

    • eric

      @Nathan Burgess

      Your goal state was 0,1,2,3,4,5,6,7,8.
      OP’s goal state was 1,2,3,4,5,6,7,8,0.

      He mentioned this in the comments.

    • Lucky

      Which heuristics did you use?
      I’m using Manhattan distance and my code solves the puzzle in 45 moves. Is it possible to use both hamming and Manhattan distance? If yes: how? Do I add them together or subtract?

      Your help will be greatly appreciated.

    • Ven S

      Can you please send your Python code of how to pass the all 181400 states and capture 31 moves and their solution paths. I got 181440 moves. How do I pass states, capture, moves and solution path and report the largest moves and two starting states.

  14. Thierry Parmentelat

    as for me I find these 2 boards to be at distances 23 and 25 resp.

    00-> [8 6 7 – 2 5 4 – 3 0 1]
    01 -> [8 6 7 – 2 0 4 – 3 5 1] (Up)
    02 -> [8 0 7 – 2 6 4 – 3 5 1] (Up)
    03 -> [0 8 7 – 2 6 4 – 3 5 1] (Left)
    04 -> [2 8 7 – 0 6 4 – 3 5 1] (Down)
    05 -> [2 8 0 – 7 6 4 – 3 5 1] (Up)
    06 -> [2 8 4 – 7 6 0 – 3 5 1] (Down)
    07 -> [2 8 4 – 7 6 1 – 3 5 0] (Down)
    08 -> [2 8 4 – 7 6 1 – 3 0 5] (Left)
    09 -> [2 8 4 – 7 0 1 – 3 6 5] (Up)
    10 -> [2 8 4 – 7 1 0 – 3 6 5] (Right)
    11 -> [2 8 4 – 7 1 3 – 0 6 5] (Down)
    12 -> [2 8 4 – 0 1 3 – 7 6 5] (Up)
    13 -> [2 8 4 – 1 0 3 – 7 6 5] (Right)
    14 -> [2 0 4 – 1 8 3 – 7 6 5] (Up)
    15 -> [0 2 4 – 1 8 3 – 7 6 5] (Left)
    16 -> [1 2 4 – 0 8 3 – 7 6 5] (Down)
    17 -> [1 2 0 – 4 8 3 – 7 6 5] (Up)
    18 -> [1 2 3 – 4 8 0 – 7 6 5] (Down)
    19 -> [1 2 3 – 4 8 5 – 7 6 0] (Down)
    20 -> [1 2 3 – 4 8 5 – 7 0 6] (Left)
    21 -> [1 2 3 – 4 0 5 – 7 8 6] (Up)
    22 -> [1 2 3 – 4 5 0 – 7 8 6] (Right)
    23 -> [1 2 3 – 4 5 6 – 7 8 0] (Down)

    00-> [6 4 7 – 8 5 0 – 3 2 1]
    01 -> [6 4 7 – 8 5 1 – 3 2 0] (Down)
    02 -> [6 4 7 – 8 5 1 – 3 0 2] (Left)
    03 -> [6 4 7 – 8 0 1 – 3 5 2] (Up)
    04 -> [6 4 7 – 8 1 0 – 3 5 2] (Right)
    05 -> [6 4 7 – 8 1 3 – 0 5 2] (Down)
    06 -> [6 4 7 – 0 1 3 – 8 5 2] (Up)
    07 -> [0 4 7 – 6 1 3 – 8 5 2] (Up)
    08 -> [4 0 7 – 6 1 3 – 8 5 2] (Right)
    09 -> [4 1 7 – 6 0 3 – 8 5 2] (Down)
    10 -> [4 1 7 – 0 6 3 – 8 5 2] (Left)
    11 -> [4 1 0 – 7 6 3 – 8 5 2] (Up)
    12 -> [4 1 3 – 7 6 0 – 8 5 2] (Down)
    13 -> [4 1 3 – 7 6 8 – 0 5 2] (Down)
    14 -> [4 1 3 – 7 6 8 – 5 0 2] (Right)
    15 -> [4 1 3 – 7 6 8 – 5 2 0] (Right)
    16 -> [4 1 3 – 7 6 0 – 5 2 8] (Up)
    17 -> [4 1 3 – 7 0 6 – 5 2 8] (Left)
    18 -> [4 1 3 – 7 2 6 – 5 0 8] (Down)
    19 -> [4 1 3 – 7 2 6 – 0 5 8] (Left)
    20 -> [4 1 3 – 0 2 6 – 7 5 8] (Up)
    21 -> [0 1 3 – 4 2 6 – 7 5 8] (Up)
    22 -> [1 0 3 – 4 2 6 – 7 5 8] (Right)
    23 -> [1 2 3 – 4 0 6 – 7 5 8] (Down)
    24 -> [1 2 3 – 4 5 6 – 7 0 8] (Down)
    25 -> [1 2 3 – 4 5 6 – 7 8 0] (Right)

    now this is my first ever program written in Rust so pardon me if there are remaining bugs in there

    for what it’s worth – and provided that it is bug-free of course – my program computes all the shortest distances to the 9!/2 reachable boards in 2.2s on a macbook pro

  15. Thierry Parmentelat

    well, obviously there remained a bug in the logic that finds the neighbour boards; so thank you for publishing this as I would probably have easily overlooked that bug without your post ! performance is unchanged though 🙂

    thanks !

  16. Lebelo Kamogelo

    Initial State
    8 6 7
    2 5 4
    3 0 1

    Iteration 1
    8 6 7
    2 0 4
    3 5 1

    Iteration 2
    8 6 7
    0 2 4
    3 5 1

    Iteration 3
    8 6 7
    3 2 4
    0 5 1

    Iteration 4
    8 6 7
    3 2 4
    5 0 1

    Iteration 5
    8 6 7
    3 0 4
    5 2 1

    Iteration 6
    8 6 7
    3 4 0
    5 2 1

    Iteration 7
    8 6 7
    3 4 1
    5 2 0

    Iteration 8
    8 6 7
    3 4 1
    5 0 2

    Iteration 9
    8 6 7
    3 4 1
    0 5 2

    Iteration 10
    8 6 7
    0 4 1
    3 5 2

    Iteration 11
    0 6 7
    8 4 1
    3 5 2

    Iteration 12
    6 0 7
    8 4 1
    3 5 2

    Iteration 13
    6 4 7
    8 0 1
    3 5 2

    Iteration 14
    6 4 7
    8 5 1
    3 0 2

    Iteration 15
    6 4 7
    8 5 1
    3 2 0

    Iteration 16
    6 4 7
    8 5 0
    3 2 1

  17. Anamaya Sharma

    Hey, I was also working on this problem and in my calculations I found the hardest/not solvable by my computer was the transpose of goal state. i.e
    [[1,4,7],
    [2,5,8],
    [3,6,.]]
    Please if you be so kind enough to run it and share the solution so I can reassess my approaches. Great Work!

    • Jason Wolfe

      Unfortunately I don’t have the code to go with this post anymore. Note that not all instances are solvable, so that could be the case for the example you’re looking at (I’m not sure).

Leave a Reply to swap

Your email address will not be published. Required fields are marked *