スライドパズルのソルバーとは、任意の解ける開始状態を受け取り、ゴールまでの手順を出力するプログラムです。このツールには2種類のユーザーがいます。詰まっているプレイヤーと、スライドパズルアプリをリリースする必要のある開発者です。
この2つのユーザーは、まったく異なるものを求めています。
プレイヤーがソルバーをほとんど必要としない理由
スライドパズルで詰まったとき、正直な解決策はたいてい「ソルバーを使う」ではありません。次の3つのうちのどれかです：
- 行・列法を覚える。 諦めてしまうプレイヤーのほとんどは、定番の解法を知らないままです。（まず8パズルを試してから規模を拡大しましょう。）
- パズルが解けるか確認する。 どう手を尽くしても解けない場合、アプリが誤って解けない盤面を生成した可能性があります。すぐに確認できます。
- 完全な解答ではなくヒントを使う。 次の1手だけでたいてい詰まりは解消されます。ヒント機能があるアプリ（当アプリのプレミアムにもあります）は、解答全体ではなく1手をオンデマンドで計算することが多いです。
完全な解答を見てもあまり学びになりません。ソルバーは最適な手順を生成しますが、15パズルの難しいケースでは52手になることもあり、スマホで52手の最適解が次々と流れていくのを見ても直感は養われません。
ヒントが適切な単位です。ヒントが必要な状況なら、ソルバーは必要ありません。
開発者がソルバーを常に必要とする理由
スライドパズルアプリを作るということは、いくつかの約束を守ることです：
- すべてのパズルが解けること。
- すべてのパズルが指定された手数程度で解けること（難易度調整）。
- すべてのパズルでオンデマンドにヒントを提供できること。
ソルバーをバックグラウンドで動かすことなしに、これらの約束は守れません。
逆算による生成ではソルバーを生成時に動かすことなく解ける盤面を作れます。ゴール状態から始め、ランダムな有効手を後ろ向きに適用すると、解ける開始状態が保証されます。当アプリを含む多くのアプリがまさにこの方法を使っています。
難易度調整では、パズルが「面白い」ことが求められます。すでにほぼ完成している（簡単すぎる）でも、3×3で60手必要（疲れる）でもない状態です。標準的な手法は、ゴールから適切な距離になるよう逆向きの手を十分に適用することです。3×3なら20〜30手、4×4なら40〜60手が目安です。ソルバーは生成後にその距離を確認します。
ヒントには、数百ミリ秒以内に1つの良い次の手を生成できるソルバーが必要です。完全な最適解よりは速いですが、それでも本格的なアルゴリズム実装が求められます。
どのソルバーを使うか
選択は盤面のサイズによります：
| 盤面 | 推奨アルゴリズム | 1回の計算時間 |
|---|---|---|
| 3×3 | A* + マンハッタン距離 | 1ms未満 |
| 4×4 | IDA* + ウォーキング距離 | 10ms〜1秒 |
| 5×5 | IDA* + 5+5+5+9 パターンDB | 100ms〜数分 |
| 6×6 | IDA* + 大規模パターンDB | 秒〜時間単位 |
3×3なら力まかせのBFSでも動きます。4×4では本格的なヒューリスティックが必要で、マンハッタン距離は1980年代から標準です。5×5ではパターンデータベースが必要です。6×6は研究領域です。
アルゴリズムの詳細は15パズル ソルバーガイドと8パズル ソルバーガイドで説明しています。アルゴリズム比較はスライドパズル ソルバーのページを参照してください。
オンデバイスかサーバーサイドか
ソルバーを実装したモバイルアプリには2つの実装選択肢があります。デバイス上で動かすか、サーバーを呼び出すかです。
オンデバイスは、プライバシーを尊重するアプリにとってより誠実な選択です。ソルバーは数百行のコードで、4×4のパターンデータベースは数メガバイトで収まり、現代のスマホなら15パズルを1秒以内で解けます。パズルの状態をサーバーに送る理由はありません。そして送らないことが、落ち着いたゲームアプリとテレメトリーが必要なアプリを区別するポイントのひとつです。
サーバーサイドは、アプリ開発者がどのパズルでユーザーが詰まっているかを追跡したり、難易度曲線をA/Bテストしたりしたい場合に使われます。これは正当なプロダクト上の理由ですが、プライバシーコストとネットワーク依存が伴います。オフラインでパズルを解けないアプリは、飛行機内で使えないアプリです。
Slide Puzzleは完全にオンデバイスで解きます。4×4のパターンデータベースは約6MBでアプリバンドル内に収録されており、ヒントボタンが直接使います。スマホの外に何のリクエストも出ません。
実用的な注記
「盤面を貼り付けたら答えを教えてくれるソルバーサイト」を探してここにたどり着いた方へ — そういうものは存在します。たいていはウェブベースの8パズルソルバーです。3×3なら問題ありません。4×4以上になると使い勝手が悪くなります。16個の数字を入力し、50手の手順を見て、物理的なボードで50手の特定の手を実行しようとする。誰も楽しくありません。
スライドパズルのソルバーの現実的な用途は：
- 自分の実装をコードで検証する。
- テスト用のボードのコーパスを生成する。
- アプリ内でヒントを計算する。
それ以外の場合は、行・列法を覚える方が早いです。