An optimal implementation of the 15-puzzle problem in C++11
Switch branches/tags
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
m4
src
.gitignore
.travis.yml
CMakeLists.txt
COPYING
INSTALL
Makefile.am
README.md
configure.ac

README.md

kpuzzle3

Biagio Festa

Overview An optimal implementation of the 15-puzzle problem (http://en.wikipedia.org/wiki/15_puzzle).

881374368-hard.png

News Compared to the previous versions, this project is based on:

  • 64 bit CPU architecture power. A configuration state is exactly stored into a 64 bit memory location. That approach allows optimizations about the CPU-Caches, and operations on the state itself (which are done bit per bit). That's why it is very important that the program has to be compiled for a 64 bit arch version. (Despite of that the application will run on 32 bit arch also, quite fast).

  • Iterative deepening depth-first search (IDDFS) which allows linear space complexity.

  • C++11 (Windows Visual Studio 2013/2015 is supported).

Pattern Database It can exploit a faster and more precise heuristic measure. It take a while for the database generation but following readings are quite fast. The implementation of the database is done through a standard c++11 hashmap, or a tbb hashmap. More Info Here.

Additional Libraries No Additional Libraries needed! Just STL!

Compilation Guide For any plattaform you want to compile the software, use CMake (it requires CMake 3.1 or above).

In particular with linux:

git clone https://github.com/BiagioFesta/kpuzzle3 && \
cd kpuzzle3 && \
mkdir build && \
cd build && \
cmake .. -DCMAKE_BUILD_TYPE=Release && \
make && \
./kpuzzle3