ホームページへ戻る
１５パズルを解く for Windows
15puzzle最短経路探索Ver2.0 (2024年9月)
1. ダウンロード
15puz20w.exe
(321KB)
for Windows.
2. 基本的な使い方
[Shuffle] ピースをシャッフルします。
[Solve] 最短経路の解を探します。
[Trace] 解答手順を表示します。
後は、いろいろ試してみて下さい。
3. アルゴリズム
このプログラムは、基本的な検索アルゴリズムとして
IDA*
を使用します。
また、検索の効率を向上させるために
WD(Walking Distance)
を使用します。
WD は MD(Manhattan Distance) よりも厳しい距離が得られます。
また、
PDB(Pattern Data Base)
と
OpenMP
も使用しています。
その詳細について:
WD
１５パズル自動解答プログラムの作り方
または
概要図
PDB
ＰＤＢを使った１５パズル自動解答プログラム
これはWDの弱点を補うために追加されています。
15枚のピースを3種類のピースに見立てて幅優先探索を行った結果を利用します。
このプログラムは２種類のPDBを使います。
OpenMP
4. 旧バージョンとの比較
旧バージョンのVer1.2 では WDのみを使用していました。しかし、WD には弱点があり、右図のような配置は苦手です。
Ver1.2
17992 秒
Ver2.0
281 秒
私が採用した PDBパターンは、この弱点の配置を考慮したものです。
そのため、右図の比較は最も極端な差が出る比較となっています。
通常は、このような極端な差は生じないと思います。
参考までに、下図の配置もWDの弱点となっています。
CPU: Core(TM) i7-13700 2.10GHz 16Core 24Threads
RAM: 16.0GB
5. ソースコード
初めに、Visual Studio Community(無料) のインストールが必要です。
インストール中、最低でも次の2つのモジュールにチェックを入れて下さい。
ウインドウズ型
15puz20w.zip
15puz20w.sln を開く
ソルバー部のコードファイルは同じです。
(15puz20solver.c)
コマンドライン型
(Solver開発用)
15puz20c.zip
15puz20c.sln を開く
Visual Studio Communityでのビルドのやり方やその他の使い方は各自で調べて下さい。
また、ソルバー部のコードを解析するには
最小完全ハッシュ関数の作り方
も参考にして下さい。
ホームページへ戻る
このプログラムは２種類のPDBを使います。
