15 パズル

遊び方

• 空きマスと同じ行か列にあるタイルをクリック（タップ）すると、間のタイルごと空きマスのほうへ滑ります。盤の上でスワイプすると、その向きへタイルを 1 つ動かします。
• キーボードでは矢印キーで、その向きへタイルを 1 つ動かします。U キーで 1 手戻し、H キーでヒントを出します。
• 「ヒント」で、いまの盤から最短で完成させるための次の 1 手（動かすタイル）を枠で示します。「自動で解く」を押すと、いまの盤から最短の手順で完成させる様子を見られます。
• 大きさ（3×3・4×4）と崩し方（かんたん・ふつう・ばらばら）ごとに、最速の時間と完成させた回数、最短の手数で完成させた回数をブラウザに保存します。自動で解く機能を使ったゲームは記録に残しません。

ルール

• 空きマスの隣にあるタイルを、空きマスへ動かせます。
• 左上から 1, 2, 3, … の順に並べ、右下を空きマスにしたら完成です。正しい位置にあるタイルは色が変わります。
• 手数はタイルを 1 つ動かすごとに 1 と数えます。列ごと滑らせたときは、動いたタイルの数だけ増えます。
• 「かんたん」「ふつう」は完成形からタイルを 20 回・60 回動かして崩します。「ばらばら」は、完成できる並びの中から等しい確率で 1 つ選びます（タイルの並べ方のうち、ちょうど半分はどう動かしても完成できません）。
• 時間は最初の 1 手から計り始め、完成したら止まります。別のタブを開いている間は止まります。

最短手順の求め方

• 最短の手順は IDA*（反復深化 A*）で探します。「ここまでの手数 + 残りの手数の見積もり」が閾値を超えない局面だけを深さ優先でたどり、見つからなければ閾値を上げてやり直します。見積もりが本当の手数を超えないので、最初に見つかった手順が最短です。
• 見積もりには、各タイルの完成形の位置までの縦横の距離の和（マンハッタン距離）、同じ行・列で順番が逆のタイルがよけ合う 2 手を足した線形衝突、4×4 ではタイルを 5 枚ずつ 3 組に分けて組ごとの最短手数を前もって全部調べておくパターンデータベースを使います。見積もりが正確なほど、調べる局面が減ります。
• 「いまの盤で見積もり方を比べる」で、同じ盤を 3 つの見積もり方で解いたときの局面の数と時間を比べられます。200 万局面を超えたら打ち切ります。