Optimal 8/15Puzzle Solver
The 8puzzle is a classic problem in AI that can be solved with the A* algorithm.
 A* maintains two lists, called open and closed.
 At the beginning of the algorithm, the initial node is placed on the open list. The list is sorted according to an admissible heuristic that measures how close the state of the node is to the goal state.
 At each step, bestNode is removed from the open list. In this case, bestNode is always the head of the open list. If the state of bestNode is the goal state, then the algorithm terminates. Otherwise bestNode is expanded (we determine all the possible states that can be reached within a single move), and bestNode is placed on the closed list.
 The successors of bestNode are placed on the open list if either:
 the successor is not already on the open or closed list, or
 the successor is already on the open or closed list but has a lower cost.
Many 15puzzles cannot be solved with the A* algorithm, since it generates too many new states and consumes a lot of memory maintaining these lists. To solve this larger puzzle, IterativeDeepeningA* (IDA*) can be used. Like the A* algorithm, it finds optimal solutions when paired with an admissible heuristic but is much more efficient with respect to space. IDA* is described as follows:
 Set threshold equal to the heuristic evaluation of the initial state.
 Conduct a depthfirst search, pruning a branch when the cost of the latest node exceeds threshold. If a solution is found during the search, return it.
 If no solution is found during the current iteration, increment threshold by the minimum amount it was exceeded, and go back to the previous step.
Three heuristics have been implemented for comparison's sake:
 Manhattan Distance
 Manhattan Distance + Linear Conflict
 Additive Pattern Database Heuristic with Static 663 Partitioning
A. Felner, R. Korf, and S. Hanan, "Additive Pattern Database Heuristics," Journal of AI Research, Vol. 22, pp. 279318, 2004.
This JAR file is about 5.8 MB. Please be patient while it loads.
Download executable JAR: PuzzleSolver.jar
 Source Code

Implementation
This applet provides a means of comparing how different algorithms and heuristics perform on the slidingtile puzzles. A* is more than acceptable for solving the the 8puzzle, with its 9! / 2 = 181,440 states and optimal solutions of up to 31 moves. It becomes painfully slow, however, for even average length solutions of the 15puzzle, which has 16! / 2 = 10,461,394,944,000 states and optimal solutions of up to 80 moves.
IDA* works well on most 15puzzle configurations, especially when paired with the additive pattern database heuristic. 663 partitioning provides a good compromise between speed and the amount of memory required to hold the statetocost mappings, of which there are 11,534,880. The application runs slightly faster on 64bit systems running a 64bit JVM, since there are operations on long primitives.
Starting with version 2.2.0, multithreaded IDA* can be used to more efficiently solve puzzles. This new algorithm starts with a breadthfirst search of the tree to a level that has a number of nodes greater than or equal to the number of threads. Any nodes that contain the same board configuration are pruned before starting the thread pool. Then multiple depthfirst search workers crawl through the search space, looking for a solution of up to threshold moves, as discussed above.
The number of threads is curently hardcoded at twice the number of available cores. This seemingly unusual number has provided the best performance in most cases on my AMD Phenom II x6. Ideally, we want the algorithm to minimize CPU idle time. Idle time occurs toward the end of an iteration in IDA*, when the depthfirst search workers start to taper off. Without more complicated code, the next iteration cannot start until we are certain there is no solution for the given threshold. Thus, starting more threads than cores keeps the CPU at max capacity over most of the iteration and generally performs better than when starting fewer threads, even with the added cost of context switching.
Why bother with multithreading? A singlethreaded Java implementation of IDA* cannot compete with the same C implementation. When profiling this code, one will observe that a large majority of execution time is spent in looking up costs in Node.h(). This section of this method that implements with the pattern database heuristic is simple, but Java's array bounds checking truly hinders performance. In a simple test of Java versus C (compiled with gcc, O2) where array elements are accessed in random order millions of times, C outperformed Java by a factor of 8. When applying the applet's pattern database heuristic, arrays are used only for cost lookups and to store the path to the goal state. Everything else has been implemented with primitives and shift operations. So, in order to improve performance, one must turn to multithreading.
Usage
The 8/15Puzzle Solver is easy to use. The options should be straightforward. To enter the configuration of a puzzle, simply list the numbers of the tiles from left to right, top to bottom, each separated by a comma. Enter 0 for the space. For example, "2,4,0,1,8,5,3,6,7" is what you would enter for the board configuration below:
2  4  
1  8  5 
3  6  7 
Note that you must use IDA* to solve 15puzzles, as the A* option has been purposefully disabled. Multithreading is not available unless you accept the certificate, since the thread pool cannot be shutdown with the default policy settings, and is not available with the 8puzzle (since a single thread is more than sufficient).
Oracle and Java are registered trademarks of Oracle and/or its affiliates.
Last modified on December 29, 2021.
© 20002002, 20112013 Brian S. Borowski. All Rights Reserved.