15パズル

15 パズル(ジェムパズル、ボス パズル、ゲーム オブ フィフティーン、ミスティック スクエアなどとも呼ばれる) は、スライディング パズルです。高さ 4 タイル分、幅 4 タイル分、空き位置が 1 つあるフレームに、1 から 15 までの番号が付けられた 15 個の正方形タイルがあります。空き位置と同じ行または列にあるタイルは、それぞれ水平または垂直にスライドして移動できます。パズルの目的は、タイルを番号順 (左から右、上から下) に配置することです。

15 パズルは、フレーム内のタイルの数にちなんで名付けられており、タイルの総容量を暗示して「16 パズル」と呼ばれることもあります。3×3 のフレームに 8 個のタイルがある 8 パズルなど、15 パズルの異なるサイズのバリエーションにも同様の名前が使用されています。

nパズルは、ヒューリスティックスを含むアルゴリズムをモデル化する 古典的な問題です。この問題でよく使用されるヒューリスティックスには、配置ミスしたタイルの数を数えることと、各ブロックと目標構成での位置との間のタクシー距離の合計を見つけることが含まれます。 ^{[1]どちらも}許容可能であることに注意してください。つまり、それらは残りの移動回数を過大評価することはなく、 A*などの特定の検索アルゴリズムの最適性を保証します。^[1]

ジョンソンとストーリー (1879) は、パリティ論法を用いて、 nパズルの開始位置の半分は、何度移動しても解決できないことを示しました。これは、有効な移動に対して不変であるタイル構成の 2 進関数を考慮し、これを使用して、すべての可能なラベル付き状態の空間を、同じサイズの相互にアクセスできない 2 つの同値クラスに分割することによって行われます。これは、すべての位置の半分は解決不可能であることを意味しますが、残りの半分については何も述べていません。

不変量は、16 個のすべての正方形の順列の偶奇性と、右下隅からの空の正方形のタクシー距離(行数と列数の合計) の偶奇性を加えたものです。これは、各移動によって順列の偶奇性とタクシー距離の偶奇性の両方が変化するため不変量です。特に、空の正方形が右下隅にある場合、残りのピースの順列が偶数である場合にのみパズルを解くことができます。

ジョンソンとストーリー (1879) は、m × n のサイズのボード ( mとnは両方とも 2 以上) では、すべての偶数順列が解けることも示しました。これは、 m = n = 2から始めて、mとnに関する帰納法で証明できます。これは、相互にアクセス可能な配置の同値クラスが正確に 2 つ存在し、同等の記​​述は存在するものの、記述されたパリティが唯一の非自明な不変量であることを意味します。

アーチャー（1999）は、ハミルトン経路を介して同値類を定義することに基づいて別の証明を与えた。

ウィルソン (1974) は、15 パズルの任意の有限グラフへの一般化を研究した。元の問題は 4×4グリッド グラフの場合である。この問題には、答えが自明であるか、またはいくつかのサブグラフ上の同じ問題に対する答えの単純な組み合わせである退化したケースがいくつかある。つまり、パスとポリゴンの場合、パズルには自由度がない。グラフが切断されている場合、頂点の「空きスペース」との接続コンポーネントのみが関連し、連結頂点がある場合、問題はその頂点の各2 連結コンポーネント上の同じパズルに縮小される。これらのケースを除外すると、ウィルソンは、7 頂点上の 1 つの例外的なグラフを除いて、グラフが2 部グラフでない限り、すべての順列を取得できることを示した。2 部グラフの場合は、正確に偶数順列を取得できる。例外的なグラフは、1 つの対角線と中心の頂点が追加された正六角形であり、 ⁠1/6⁠の順列が達成され、 S ₅からS ₆へのエキゾチックな埋め込みの例が得られます。

nパズルのより大きなバージョンでは、解法を見つけるのは簡単です。しかし、最短の解法を見つける問題はNP 困難です。最小のスライドを加法定数内で近似することも NP 困難ですが、多項式時間定数係数近似があります。^{[2] [3]} 15 パズルの場合、最適解の長さは 0 から 80 の単一タイルの移動 (80 の移動を必要とする構成は 17 個あります) ^{[4] [5]}または 43 の複数タイルの移動の範囲です。^[6] 8 パズルは常に 31 の単一タイルの移動または 24 の複数タイルの移動 (整数シーケンス A087725) 以内で解くことができます。複数タイルのメトリックは、同じ方向への空のタイルの後続の移動を 1 としてカウントします。^[6]

24パズルの可能な位置の数は⁠25！/2⁠ ≈7.76 × 10 ²⁴であり、これは力ずくの方法で神の数を計算するには多すぎる。2011年には、1牌で152回、複数牌で41回という下限値と、1牌で208回、複数牌で109回という上限値が確立されていた。 ^{[7] [8] [9] [10]} 2016年には、上限値が205回に改善された。^[11]

15のパズルの変形は群体（すべての動きを合成できるわけではないので群ではない）を形成します。^{[12] [13] [14]}この群体は構成に作用します。

15パズルの組み合わせは3サイクルで生成できるため、15パズルは交代群 で表すことができることが証明できます。^[15]実際、同じ大きさの正方形のタイルを持つスライディングパズルはすべて で表すことができます。 ${\displaystyle A_{15}}$${\displaystyle 2k-1}$${\displaystyle A_{2k-1}}$

このパズルは、ニューヨーク州カナストータの郵便局長だったノイエス・パーマー・チャップマン^[16]によって「発明」されました。彼は1874年には早くも友人たちに、4列に並べると合計が34になる16個の番号付きブロックからなるパズルの前身を見せていたと言われています（魔方陣を参照）。改良された15パズルのコピーは、チャップマンの息子フランクを通じてニューヨーク州シラキュースに渡り、そこからさまざまなつながりを通じてロードアイランド州ウォッチヒル、そして最終的にコネチカット州ハートフォードに渡り、そこでアメリカ聾学校の生徒たちがパズルの製造を開始しました。1879年12月までに、これらは地元とマサチューセッツ州ボストンの両方で販売されました。ボストンで木工事業を営んでいたマティアス・ライスは、このパズルの1つを見せられ、1879年12月頃にパズルの製造を開始し、「ヤンキー・ノーションズ」という雑貨商を説得して「ジェム・パズル」という名前で販売させた。1880年1月下旬、マサチューセッツ州ウースターの歯科医チャールズ・ピーヴィーは、15パズルの解答者に賞金を出すと申し出て注目を集めた。^[16]

このゲームは1880年にアメリカで大流行した。 ^[17]

チャップマンは1880年2月21日に「ブロックソリティアパズル」の特許を申請した。しかし、この特許は却下された。おそらく、アーネスト・U・キンゼイに1878年8月20日に付与された「パズルブロック」の特許（US 207124）と十分に異なっていなかったためと思われる。^[16]

1891年から1911年に亡くなるまで、サム・ロイドは自分がこのパズルを発明したと主張していた。しかし、ロイドはパズルの発明や初期の人気とは無関係だった。ロイドがパズルについて初めて論文を発表したのは1886年で、彼が発明者だと主張したのは1891年になってからだった。^{[16] [18]}

ロイドが指定した特定の組み合わせ、つまり14と15を逆にするパズルを解いた人に1,000ドル（2023年の時点で33,911ドルに相当）の賞金を出すとロイドが申し出たことで、後に関心が高まりました。ロイドはこれを14-15パズルと呼びました。^[1]これは不可能であり、10年以上前にジョンソンとストーリー（1879）によって示されていました。なぜなら、偶数から奇数への順列変換が必要だからです。

ソ連で製造されたマイナスキューブは、 15パズルと同様の操作を行う 3Dパズルです。

15 パズルのバージョンには、8 パズルや 24 パズルなど、異なる数のタイルが含まれます。

チェスの世界チャンピオン、 ボビー・フィッシャーは15のパズルを解く達人だった。^[19]彼は25秒以内に解くことができると計測され、フィッシャーは1972年11月8日のジョニー・カーソン主演のトゥナイト・ショーでこれを実演した。^{[20] [21]}

• 組み合わせパズル
• タカンゲーム、15パズルの動きに似たスキューヤングタブローの操作
• クロツキ
• 機械パズル
• 小石の動きの問題
• ルービックキューブ
• 3つのカップの問題

ウィキメディア・コモンズには、 15 パズルに関連するメディアがあります。

• 15パズルの歴史
• 15のパズルの解答
• 15 パズルの m × n 一般化に必要な最大移動数
• 15 パズルの最適ソルバー (Herbert Kociemba 提供) (ダウンロード可能)