Created: 2011-07-13 10:16
Updated: 2018-11-09 11:43


What it currently does

Solves not too difficult instances of the 15 puzzle [6] using IDA* with the Manhattan distance heuristic. By "not too difficult" I mean the instance must be solvable using at most 65 moves. The hardest instances of the 15 puzzle (see the veryhard input file) require as many as 80 moves to solve and the Manhattan distance heuristic in the current implementation isn't strong enough to prune the search space sufficiently.

There is a (slow) A* implementation and a memory efficient (and faster) IDA* implementation inside.

$ g++ -std=c++11 -O3 15puzzle.cpp
$ time ./a.out < input

This puzzle is not solvable.
This puzzle is not solvable.

real	0m8.112s
user	0m8.105s
sys	0m0.004s

What needs to be done

A heuristic generated by disjoint pattern databases [1] would be necessary to quickly solve the 15 puzzle. Some multithreading maybe? Bidirectional search?

In the future

Some attempts at the 24 puzzle perhaps.


  1. R. E. Korf and A. Felner, Disjoint pattern database heuristics
  2. R. Zhou and E. Hansen, Space-efficient memory-based heuristics
  3. A. Felner and A. Adler, Solving the 24 Puzzle with Instance Dependent Pattern Databases
  4. R. C. Holte, J. Newton, A. Felner, R. Meshulam, D. Furcy, Multiple Pattern Databases
  5. R. E. Korf, Depth-First Iterative-Deepening- An Optimal Admissible Tree Search
  6. Wm. W. Johnson, Notes on the 15-Puzzle
  7. R. C. Holte, A. Felner, J. Newton, R. Meshulam, D. Furcy, Maximizing over Multiple Pattern Databases Speeds up Heuristic Search
  8. A. Felner, R. E. Korf, S. Hanan, Additive Pattern Database Heuristics
Cookies help us deliver our services. By using our services, you agree to our use of cookies Learn more