Solve 24 puzzles using zero-aware pattern databases
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
catalogues
cmd
doc
test
util
.gitignore
COPYING
Makefile
README
builtins.h
catalogue.c
catalogue.h
cindex.c
histogram.c
ida.c
index.c
index.h
moves.c
parallel.c
parallel.h
pdb.c
pdb.h
pdbdiff.c
pdbdom.c
pdbgen.c
pdbident.c
pdbverify.c
puzzle.c
puzzle.h
random.c
rank.c
search.c
search.h
tileset.c
tileset.h
validation.c

README

This repository contains code to solve the 24 puzzle using pattern
databases.  The code in here was written as a part of the author's
Bachelor thesis and is made available under the terms and conditions
of the 2-clause BSD license.

The 24 puzzle is a variant of the 15 puzzle played on a 5x5 tray.  The
solved configuration looks like this:

        1  2  3  4
     5  6  7  8  9
    10 11 12 13 14
    15 16 17 18 19
    20 21 22 23 24

Puzzle configurations are specified as a comma-separated list of tiles:

    24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0

To solve a puzzle, use the pdbsearch program.  The program first
generates or loads (if -d pdbdir has been provided) pattern databases
and then prompts you for a puzzle instance.  Use it like this:

    pdbsearch -j jobs catalogue.cat

where jobs is the number of threads to use for PDB generation and
catalogue.cat is the PDB catalogue to use.  Some PDB catalogues are
provided in the catalogues directory, I recommend the catalogue
small-compound.cat.  The program always finds the shortest possible
solution, this may take a while.  You can find some sample instances in
doc/korf.txt.

To compile this code, use GNU make.  A C11 compatible C compiler is
required.  Adjust CC and CFLAGS as needed.  For best performance,
make sure that at least SSE4.2 support is enabled.  Ideally, AVX2 and
BMI2 should be available.

The following programs are included:

cmd/diffcode
	Prepare pattern databases for compression by applying a
	differential encoding.  Data compression has not been
	implemented any further.

cmd/genpdb
	Generate a single pattern database.  This command is not
	needed anymore as pattern databases are generated as needed by
	pdbsearch and parsearch.

cmd/parsearch
	Search puzzle solutions in parallel.  While this implementation
	of IDA* is not parallel, this program searches for the solutions
	of multiple puzzles at once to gain a similar speedup.

cmd/pdbsearch
	Solve a single puzzle.

cmd/pdbstats
	Print pattern database statistics.

cmd/puzzlegen
	Generate random puzzle instances.  The instances are guarantted
	to be solvable.

cmd/reducepdb
	Prepare pattern databases for compression by computing
	dominating sets.

cmd/verifypdb
	Verify the correctness of a pattern database.

test/hitanalysis
	Analyse which tile combinations are accounted for by a given PDB
	catalogue.

test/indextest
	Verify the correctness of the pattern database index function.

test/qualitytest
	Analyse the heuristic quality of a PDB catalogue.

test/rankcount
	Count zero tile regions for a given tile set size.

test/ranktest
	Verify the correctness of the rank() and unrank() functions.

util/rankgen
	Generate the file ranktbl.c