15puzzle Optimal solver

"15puzzle Optimal solver" for Windows.

Version 2.0 (Sep/2024)

1. DownLoad: 15puz20w.exe (321KB)
for Windows.

2. Basic usage: [Shuffle] Shuffle the pieces.
[Solve] Finds a solution.
[Trace] Works as per solution.
Please try suitably except it.

3. Algorithm

This program uses IDA* as the basic search algorithm.
And this uses WD(Walking Distance) to improve the efficiency of the search.
WD gives severe distance than MD(Manhattan Distance).
It also uses PDB(Pattern Data Base) and OpenMP.
As for the details:

WD	here.(Japanese Written in 2002) or Picture
PDB	here.(Japanese Written in 2002) This is to compensate for the weaknesses of WD. Divide the 15 pieces into 3 groups and do a breadth-first search. And use the results. This program uses two types of PDB.
OpenMP

4. Comparison with older version

The older version, Ver1.2 only used WD. However, WD has a weakness and is not good at arrangements like the one shown on the right.

Ver1.2	17992 sec
Ver2.0	281 sec

The PDB pattern I adopted takes this placement of weak points into consideration.
Therefore, the comparison on the right is the one that will produce the most extreme differences.
Normally, it seems that such extreme differences do not occur.

For reference, the arrangement shown below is also a weak point of WD.

CPU: Core(TM) i7-13700 2.10GHz 16Core 24Threads
RAM: 16.0GB

5. Source code

Visual Studio Community (free) must be installed. During installation,two modules are required.
Please check the icon. Sorry the image is in Japanese.

Windows type	15puz20w.zip	Open 15puz20w.sln	The solver code file is the same. (15puz20solver.c)
Command line type (Solver Research)	15puz20c.zip	Open 15puz20c.sln	The solver code file is the same. (15puz20solver.c)

Please research how to build with Visual Studio Community and other usage methods yourself.
Also, the knowledge required to analyze the solver. here.(Japanese Written in 2002)

INDEX