15個のパズル

ジョンソンとストーリー（1879）は、パリティの議論を用いて、 nパズルの初期配置の半分は、何手進んでも解けないことを示した。これは、有効な移動に対して不変なタイル配置の二値関数を考え、それを用いて、可能なすべてのラベル付き状態の空間を、互いにアクセスできない同じサイズの2つの同値類に分割することによって行われた。これは、すべての配置の半分が解けないことを意味するが、残りの半分については何も示していない。

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

ジョンソンとストーリー（1879）は、 m × nのサイズの盤面（mとnはともに 2 以上）では、すべての偶順列が解けることを示した。これは、 m = n = 2から始めて、mとnに関する帰納法で証明できる。これは、相互にアクセス可能な配置の同値類がちょうど 2 つ存在し、記述されたパリティが唯一の非自明な不変量であることを意味するが、同値な記述も存在する。

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

ウィルソン (1974) は、 15 パズルを任意の有限グラフに一般化する研究を行った。元の問題は 4×4グリッド グラフの場合であった。この問題には、答えが自明であるか、またはいくつかの部分グラフ上の同じ問題の答えの単純な組み合わせであるような退化したケースがいくつかある。すなわち、パスと多角形の場合、パズルには自由度がない。グラフが非連結の場合、「空スペース」を持つ頂点の連結成分のみが関係する。また、関節頂点がある場合、問題はその頂点の双連結成分のそれぞれで同じパズルに帰着する。これらのケースを除外すると、ウィルソンは、7 つの頂点を持つ 1 つの例外的なグラフを除いて、グラフが二部グラフでない限り、すべての順列を取得できることを示した。二部グラフの場合は、偶数順列のみを取得できる。例外的なグラフは、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パズルは交代グループで表現できることが証明できます。${\displaystyle A_{15}}$[ ^{15 ]}実際、^どんな${\displaystyle 2k-1}$同じサイズの正方形タイルを使ったスライドパズルは次のように表すことができます。${\displaystyle A_{2k-1}}$。

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

その後、ロイドが、ロイドが指定した特定の組み合わせ、つまり14と15を反転させるという組み合わせを実現できる人に1,000ドルの賞金（ 2025年換算で35,833ドルに相当）を提供すると申し出たことで、関心が高まりました。ロイドはこの組み合わせを14-15パズルと呼んでいました。^{[ 1 ]}これは、偶数順列から奇数順列への変換が必要となるため、10年以上前にジョンソンとストーリー（1879）によって示されたように不可能です。