15パズルについて | 歴史、偶奇性、サム・ロイドの14-15

1880年のブーム

このパズルは1870年代のニューヨーク州で生まれました。考案者としては、カナストータの郵便局長ノイス・チャップマンの名が挙げられるのが普通です。1880年の初めに大ブームとなり、まずアメリカ全土に、続いてヨーロッパに広がりました。

サム・ロイドの14-15

アメリカのパズル作家サム・ロイドは、のちに自分がこのパズルを考案したと主張し、14と15だけを入れ替えた状態から解けた人には1,000ドルの賞金を出すと語りました。賞金を手にした人はいませんでしたし、いるはずもありませんでした。その局面は解けないからです。考案者だという彼の主張も事実ではありませんでした。

局面の半分が解けない理由

空きマスを16枚目の駒と考えます。スライドのたびに、空きマスと駒が1つ入れ替わります。空きマスが隅に戻るには、左と右に同じ回数、上と下に同じ回数動かなければなりません。そのため、空きマスが隅にある局面は、完成した並びから必ず偶数回の入れ替えだけ離れています。14と15の入れ替えは1回、つまり奇数なので、どんなスライドでもたどり着けません。1879年、ウィリアム・ジョンソンとウィリアム・ストーリーは、すべての並びのちょうど半分に到達できることを証明しました。

どの局面にも使える判定法

枠を1行ずつ読んだときに順序が逆になっている駒の組を数えます。3×3か5×5の盤では、その数が偶数なら局面は解けます。4×4の盤では、空きマスの行を下から数えた数を足します。その和が奇数なら局面は解けます。

コンピューターで解く

コンピューターは A* で元に戻る道筋を探せます。A* は、いつも最も有望な局面から先に調べます。あと何手必要かは、各駒が本来の位置からどれだけ離れているかと、本来の行や列で互いにじゃまをしている駒の組ごとに加える2手から見積もります。大きな盤では、最短の解を見つけるのがとても難しくなります。15パズルで最も難しい局面には80手が必要で、8パズルは31手を超えることはありません。

PictorX で試す

15パズルを開き、駒をクリックしてスライドさせます。「シャッフル」は駒を混ぜて解ける新しい局面を作り、「解く」は解を1手ずつ再生し、「正しい位置の駒を表示」はすでに正しい位置にある駒の数字に色を付けます。「ロイドの14-15」を選ぶと解けない局面が見られ、「サイズ」で3×3、4×4、5×5を切り替えられます。