See papers:

In the 1996 paper, 10 instances of the 24-puzzle problem are looked at. Nine of ten of those instances are solved in the paper, with a lower bound for the tenth being established.

I have implemented a solver that can solve all 10 instances. This can be reproduced by running ./run from this commit 4f2a1be.

Instance Nodes Generated1 Time taken (s) Optimal Solution
17 1 20 9 16 2 22 19 14 5 15 21 0 3 24 23 18 13 12 7 10 8 6 4 11 6,508,216,548 168 100
14 5 9 2 18 8 23 19 12 17 15 0 10 20 4 6 11 21 1 7 24 3 16 22 13 3,949,323,558 176 95
7 13 11 22 12 20 1 18 21 5 0 8 14 24 19 9 4 17 16 10 23 15 3 2 6 74,382,671,211 3172 108
18 14 0 9 8 3 7 19 2 15 5 12 1 13 24 23 4 21 10 20 16 22 11 6 17 75,528,769,943 1928 98
2 0 10 19 1 4 16 3 15 20 22 9 6 18 5 13 12 21 8 17 23 11 24 7 14 127,858,033,287 5536 101
16 5 1 12 6 24 17 9 2 22 4 10 13 18 19 20 0 23 7 21 15 11 8 3 14 373,302,608,938 8572 96
21 22 15 9 24 12 16 23 2 8 5 18 17 7 10 14 13 4 0 6 20 11 3 1 19 330,453,737,334 17656 104
6 0 24 14 8 5 21 19 9 17 16 20 10 13 2 15 11 22 1 3 7 23 4 18 12 68,097,975,369 3146 97
3 2 17 0 14 18 22 19 15 20 9 7 10 21 16 6 24 23 8 5 1 4 11 12 13 492,114,567,189 24793 113
23 14 0 24 17 9 20 21 2 18 10 13 22 1 3 11 4 16 6 5 7 12 8 15 19 10,172,974,643,392 422230 114
  1. The nodes generated does not include the last iteration, so these values are in reality a bit higher.

Run on Ubuntu 20.04 with a Ryzen r9-3900x CPU with 32GB ram.

The solution to the tenth instance, using a demo from Michael Kim:

The demo can be reproduced using these strings:

To generate the board from a reverse board (empty on top left):
L U R U L L D R D R U U L L L D L D R U R U U R R D L D L U L D R D L U L U R U U R D R U R D D D L D L U L L D R U U U U L D D D R U U U R D D D L U U U R D D R D L L U R R U U R D D D D L U U U L L D R D D L U R R U R D D L L

To solve the board (a reverse sequence of above with inverted operators):
R R U U L D L L D R U U L U R R D D D R U U U U L D D L L D R R U L U U L D D D R U U U L D D D L U U U R D D D D L U R R D R U R U U U L D L U L D D L D R D R U L U R D R U R U L L D D L D L U R U R R R D D L U L U R R D L D R

A zip containing the log file of all the results is here.

Differences to the implementation in Korf & Taylor paper:

  • Better heuristics were used. This implementation uses walking distance and disjoint pattern databases. Michael Kim talks about it in his blog post. These heuristics made some of the problems easier to solve.
  • Uses multiprocessing to utilise 24 threads. A small BFS is used to generate a pool of starting nodes, which are then used in the IDA* search. Threads are allocated groups of starting nodes to solve for each iteration of the IDA* search. This could be generalised in a distributed system, since it is possible to generate a large pool of nodes to start with. For implementation details, see IdaStarMulti.cpp.
  • The FSM used to prune nodes was smaller. The forbidden words dictionary for this implementation was generated from 16 BFS searches of depth 14, which had 10018 words and 33451 states. Korf & Taylor generated a structure with 619,000 states, so this structure would have pruned many more nodes.