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 and Master 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.

Here is a general overview of the directories:

catalogues
	PDB catalogues

cmd	programs to solve the 24 puzzle and for related purposes

doc	measurements and results

test	test programs and experiments

util	source code generators and templates

The following programs are included:

cmd/addmoribund
	Add moribund state tables to a finite state machine that doesn't
	have them.

cmd/binpdb
	Compress PDBs to one bit per entry using a differential encoding

cmd/compilefsm
	Compile a set of loop descriptions (see cmd/genloops) into a
	finite state machine for pruning.

cmd/etacount
	Compute eta for a PDB by counting its entries.  Note that this
	code is defective due to wrong entry weighting.  I never managed
	to actually finish it.

cmd/genloops
	Compute a set of loops (i.e. pairs of paths that lead to the
	same configuration) by breadth-first search.  This is used to
	build finite state machines for pruning.

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/pdbcount
	Count the number of truly distinct PDBs.

cmd/pdbmatch
	Find optimal 6-6-6-6 partitionings by matching all possible
	6-tile PDBs with each other and approximating the quality of the
	result.  Another unfinished experiment.

cmd/pdbquality
	Print the quality and related data about a pattern database.
	This program correctly computes the quality of single pattern
	databases.

cmd/pdbsearch
	Solve a single puzzle.

cmd/pdbstats
	Print a histogram of the entires of a PDB.

cmd/puzzledist
	Compute the number of puzzles at each distance from the solved
	configuration by exhaustive breadth-first search.  Gets to a
	distance of about 30 given 1 TB of RAM.

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

cmd/randompdb
	Generate a random partitioning of the tiles into PDBs

cmd/sampleeta
	Compute the heuristic quality eta by sampling spheres

cmd/spheresample
	Sample spheres by means of random walks to generate samples
	for cmd/sampleeta

cmd/verifypdb
	Verify the correctness of a pattern database.

test/bitpdbtest
	Verify that a PDB and its corresponding BitPDB yield the same
	h values

test/etatest
	Compute eta by stratified sample.

test/expansions
	Compute statistics about the average number of vertices
	expanded at each distance for a given heuristic.

test/explore
	Interactively explore puzzles.

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

test/indexbench
	Index function benchmark.

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

test/morphtest
	Verify the correctness of morphed pattern databases.

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.

test/samplegen
	Generate random samples and classify them by distance to the
	solved configuration.  This was an early attempt to sample
	spheres.  Finding it too inefficient, I replaced it by
	cmd/spheresample.

test/statmerge
	Merge sets of samples generated by test/samplegen.

test/walkdist
	Perform random walks with a fixed distance and evaluate the
	distance distribution of the vertices encountered

util/rankgen
	Generate the file ranktbl.c