こんにちは！半沢です！
今回の記事では群論における15パズル(15 puzzle)について解説します。
スマホゲームの広告などでよく見る15ゲームは，実は群論によって可解性を判定することができます。
さらにその理論の中に，\(\,15\,\)次交代群が長さ\(\,3\,\)の巡回置換で生成されることが絡んでくるなど，群論的な観点からも非常に興味深いものです。
少々難しいと思いますが，できるだけ分かりやすく解説したので，読んでいただけると嬉しいです。
15パズル(15 puzzle)
遊び方
定義
次のルールで進行されるパズルを15パズル(15 puzzle)と呼ぶ。
\([1]\,\)\(1\sim 15\,\)の数字が書かれた，大きさは均一の\(\,15\,\)個の小さな正方形(以下，ブロックと呼ぶ)と，
そのブロックが\(\,16\,\)個収納できる大きな正方形の枠でパズルは行われる(よって\(\,1\,\)つ空きマスができる)。
\([2]\,\)プレイヤーがブロックを動かせる手段は，ブロックを空きマスにスライドさせることのみである。
\([3]\,\)プレイヤーはブロックを，与えられた配置(初期配置)から，特定の配置(目的配置)に組み替えることができたらパズルクリアである。
多くの場合，上の図の配置を目的配置としてパズルを行うことが多いです。
その場合の15パズルは“ゲームのるつぼ”というサイトで無料で遊べるので，慣れていない方は遊んでみることをおススメします。
さて，これからこの15パズルの数学的構造について議論していきましょう。
サム・ロイド(Sam Loyd)の問題
15パズルとして次の問題を考えてみましょう。
サム・ロイド(Sam Loyd)の問題
\(14,15\,\)ブロックだけを入れ替えた初期配置から，元の右の配置へと組み替えよ。
パズル作家のサム・ロイドさんは1878年に上のような問題を出題し，さらに1000$を懸賞金としました。
私もこの問題に一万円ほどの懸賞金を設定するので，問題に挑戦してみてください。
挑戦してみると実感すると思いますが，このパズル解けません。
では，なぜ解けないのでしょうか？
それには置換の偶奇性が関わってきます。
ここからは，必要最小限に留めますが，群論を用いた説明になります。
群論に慣れていない方は難しく感じると思いますが，そういった方は雰囲気だけでも味わっていってください。
まず空白の部分も一つのブロックとみなします(\(16\,\)番目のブロックと考えると良いでしょう)。
このとき15パズルを解く手順は\(\,16\,\)個のブロックの置換とみなせることの注意しましょう。
次に，ブロックの入るコマを下図のように赤・青で2つにグループ分けします。
空白のブロックは，初期位置では赤マスに位置しますね。
そして空白のブロックを他のブロックと互換させる毎に赤\(\to\)青\(\to\)赤\(\to\cdots\)のように
空白の下のマスの色はきれいに交互に入れ替わっていきますね。
そのため空白の下のマスの色は，互換が偶数回なら赤マス，奇数回なら青マスとなります。
そして最終的には元の位置，つまり赤マスに戻ってくる必要があります。
したがって問題を解く手順をブロックの置換とみなすと，解法は偶数個の互換によって構成されています。
しかし一方で目的の配置は初期配置から\(\,14,15\,\)ブロックを入れ替え直すという\(\,1\,\)回の互換，すなわち奇数回の互換によって得られる必要があります。
すなわち解法は奇数回の互換になっている必要があるため，解法は奇数個の互換によっても構成される必要があります。
置換の偶奇は置換ごとに定まる不変な量なので，これは矛盾です。
したがってサム・ロイドの問題は解けないことが分かりました。
このサム・ロイドの問題を解くために用いた手法は，15パズルの可解配置に関するヒントを与えてくれます。
つまり初期配置から，そのブロックを奇置換で動かした配置は実現することはできないということです。
このことから初期配置を固定すると，目的配置として可解なものの総数は，全ブロックの配置
\(\,16!=20,922,789,888,000\,\)
の半分である
\(\,\dfrac{16!}{2}=10,461,394,944,000\,\)
以下ということになります。
この証明ではあくまで「以下」ということしか示されていません。
なぜなら初期配置から偶置換で作り上げられた配置が実現可能か示されていないからです。
※サム・ロイドの問題によって15パズルが有名になったなどの，サム・ロイドと15パズルの歴史を耳にすると思いますが，実際は眉唾物のようです。
\([2]\)によると，SlocumとSonneveldさんの研究(\([2]\)の一部もSlocumさんが寄稿しています)により，これらの歴史の一部はでたらめであることが報告されています。
サム・ロイドさんは，自身の著作の中で真実を誇張しがちな人物だったようです。
15パズルの可解性
この章では前節で残った疑問
初期配置から偶置換で作り上げられた配置は実現可能なのか？
を紐解いていきましょう。
この問題は1879年にW. E. Storyさんが解決しました。
※よく一緒に名前を出されるW. W. Johnsonさんは同年1879年に，奇置換による配置は実現不可能であることを示した人物です。
この記事では，A. F. Archerさんによって現代的な手法を用いて書かれた論文\([1]\)に沿って解説していきます。
準備
まずは15パズルを数学的に取り扱いやすくするための準備をしましょう。
用語の確認からです。次のように用語を定義します。
定義
ブロック(block)\(\,\cdots\,\)パズル盤内の小さな正方形。
マス(cell)\(\,\cdots\,\)パズル盤内のブロック\(\,1\,\)個が収まる空間
ただし空きマスにも一つの特別なブロック(
配置(placement)\(\,\cdots\,\)\(16\,\)個のブロックの集合から\(\,16\,\)個のマスへの全単射。
また番号の付け方は人間の勝手ですので，マスの番号をここまで取り扱ってきたものと異なり，次のように蛇のような経路(以後，蛇行路(snaking path)と呼びます)に沿って付けます。
※以下から各ブロックの右上の小さな数が下のマスの番号を表すこととします。
このように番号を振るのは，空ブロックが番号を辿る経路に沿って全てのマスを巡ることができるようにするためです。
次に自由自在に動く空ブロックを，ある意味，固定したような状況を考えるために配置の集合\(\,P\,\)に次のような同値関係を導入します(同値関係になることは定義から自明です)。
定義
配置の集合\(\,P\,\)上の同値関係\(\,\sim\,\)を，\(\,Pl_1,Pl_2\in P\,\)に対して
\(\phantom{\Leftrightarrow}\,PL_1\sim PL_2\)
\(\Leftrightarrow \,\)\(PL_1\,\)の空ブロックを蛇行路に沿ってうまく動かすと配置\(\,PL_2\,\)になる
またこの同値関係により得られる同値類\(\,Cf\in P/{\sim}\,\)を配列(configuration)と呼ぶ。
あともう一つ定義させてください。
ブロック・マスは割り振られた番号で「ブロック\(\,1\,\)」のように呼ぶものとします。
ただし空ブロックだけは振られた番号もないので，そのまま「空ブロック」で呼ぶものとし，上のように番号で表す名称からは除外されるものとします。
このとき番号が振られたブロックに対して，次の用語を定義します。
定義
ブロック\(\,i\,\)がマス\(\,j\,\)にはめ込まれている(in slot)とは，
ブロック\(\,i\,\)がマス\(\,j\,\)の上にある，かつ空ブロックは\(\,j\,\)よりも大きい番号のマスの上にあることである。
この条件が満たされていないとき，ブロック\(\,i\,\)はマス\(\,(j-1)\,\)にはめ込まれているとする。
一見複雑そうな定義ですが，仕組みを知れば簡単です。
例えば左の配置のブロックがどのマスにはめ込まれているのか知りたいとします。
空ブロックの位置するマスより小さい番号のマスの上にあるブロックについては，
定義から，そのまま各ブロックの下のマスにはめ込まれていますね。
空ブロックの位置するマスより大きい番号のマスの上にあるブロックについては，
各ブロックの下の番号から\(\,1\,\)引いた番号のマスにはめ込まれていることになります。
これは，上図のように空ブロックを蛇行路に沿って左下のマスに沿って動かしたときの下のマスに，各ブロックがはめ込まれていることを意味します。
\(-1\,\)が蛇行路を一つ戻ることを意味していると気づくと分かりやすいでしょう。
つまりブロックがどこにはめ込まれているかを知りたかったら，
空ブロックを左下のマスに持って来て，各ブロックの下の番号を読み取れば良いというだけです。
この空ブロックを蛇行路に沿って左下のマスに持ってきた状態を以後，標準形と呼ぶことにします。
またこの議論から，配列\(\,Cf\in P/{\sim}\,\)の代表元によらず，\(\,Cf\,\)からブロック\(\,i\,\)にはめ込まれているマスの番号が定まることが分かります。
故に\(\,Cf\,\)に対し，ブロック\(\,i\,\)がはめ込まれているマスの番号を\(\,a_i\,\)と書くことにすると，
\(Cf\mapsto [a_1,a_2,\cdots,a_{15}]\)
のように，配列\(\,Cf\,\)に対し，マスの\(\,1\sim 15\,\)の番号の順列\(\,[a_1,a_2,\cdots,a_{15}]\,\)を紐づけることができます(しかもこの紐づけは全単射)。
そこで以下では，配列\(\,Cf\,\)の表記方法として\(\,[a_1,a_2,\cdots,a_{15}]\,\)採用することにします。
以上の問題設定の準備は完了です。
スライドによる置換
前節で行った準備の上で，空きマスの所へのブロックのスライドはどのように表現されるでしょうか。
空きマスには空ブロックが位置していると考えているため，空ブロックとの入れ替えを考えれば良いですね。
例えばマス\(\,11\,\)にあった空ブロックを，マス\(\,14\,\)に持ってくる操作\(\,\sigma_{11,14}\,\)を考えましょう(空ブロックを灰色で表しています)。
するとこの操作の前後で，配列の番号は次のように置換されてます。
配列の番号が確認しやすい分かりやすいように，上の図に変化前後の標準形も載せているので，確認してみてください。
赤ブロックがはめ込まれているマス\(\,\cdots\,11\to 12\)
青ブロックがはめ込まれているマス\(\,\cdots\,12\to 13\)
緑ブロックがはめ込まれているマス\(\,\cdots\,13\to 11\)
それ以外のブロックがはめ込まれているマス\(\,\cdots\,\)変化なし
つまり空ブロックの入れ替えの操作\(\,\sigma_{11,14}\,\)は配列\(\,[a_1,\cdots,a_{15}]\,\)の置換となることが分かり，
それは巡回置換\(\,\sigma_{11,14}=(11,12,13)\,\)と表されるということです。
そこで考え得る，空ブロックと他のブロックとの入れ替えに対しても，同様に置換で表してみましょう。
マス\(\,i\,\)にあった空ブロックを，マス\(\,j\,\)に持ってくる操作を\(\,\sigma_{i,j}\,\)で表すとします。
定義より明らかに\(\,\sigma_{i,i+1}=\mathrm{id}_{P/{\sim}}\,\)ですね(蛇行路に沿って動かすだけなので)。
また\(\,\sigma_{j,i}=\sigma_{i,j}^{-1}\,\)となることも明らかですね。
これらを踏まえると本質的な操作は次の\(\,9\,\)個だと分かります。
\(\sigma_{1,8}=(1,2,3,4,5,6,7)\)
\(\sigma_{2,7}=(2,3,4,5,6)\)
\(\sigma_{3,6}=(3,4,5)\)
\(\sigma_{5,12}=(5,6,7,8,9,10,11)\)
\(\sigma_{6,11}=(6,7,8,9,10)\)
\(\sigma_{7,10}=(7,8,9)\)
\(\sigma_{9,16}=(9,10,11,12,13,14,15)\)
\(\sigma_{10,15}=(10,11,12,13,14)\)
\(\sigma_{11,14}=(11,12,13)\)
もちろん逆に15パズルで可能な操作はこれらの合成によって表されます。
そのため，これらが\(\,15\,\)次対称群\(\,\mathfrak{S}_{15}\,\)内で生成する部分群を\(\,G\,\)とおくと，
この\(\,G\,\)の正体が分かれば，どのような操作が15パズルで可能なのかがはっきりします。
つまり，問題は部分群\(\,G\,\)の正体を突き止めることに集約しました。
対称上の考察
さてこの節では前節で定義した部分群\(\,G\,\)の正体を突き止めます。
前節で確認したように\(\,G\,\)は偶置換で生成されるので，\(\,15\,\)次交代群\(\,A_{15}\,\)に含まれることが分かります。
さらに\(\,G=A_{15}\,\)となることを示すのがこの節の目的です。
そのことを段階的に示していきましょう。
まずは補題1です。
補題1
\(A_n\,\,(n\geq 3)\,\)は長さ\(\,3\,\)の巡回置換によって生成される。
\(A_n\,\)は二つの互換の積によって生成されるので，二つの互換の積を長さ\(\,3\,\)の巡回置換の積で表すことができれば良いですね。
\(a,b,c,d\,\)を相異なる\(\,1\sim n\,\)の数とすると，
\((a,b)(c,d)=(a,b,c)(b,c,d)\)
\((a,b)(b,c)=(b,c,a)\)
\((a,b)(a,b)=\mathrm{id}_{P/{\sim}}\)
と実際に二つの互換の積は，長さ\(\,3\,\)の巡回置換の積で表せるので，補題1は示されました。\(\quad\square\)
※元論文と異なり，置換を左から作用するものと考えているので，表記が異なっています。
続いて補題2です。
補題2
\(A_n\,\,(n\geq 3)\,\)は連続的な長さ\(\,3\,\)の巡回置換の集合\(\,T_n\coloneqq\{(1,2,3),(2,3,4),\ldots,(n-2,n-1,n)\}\,\)によって生成される。
帰納法により示します。\(\,n=3\,\)のときは明らかです。
\(n=k\,(\geq 3)\,\)のとき成り立つと仮定し，\(\,n=k+1\,\)のときについて考えましょう。
補題1より\(\,A_{k+1}\,\)は長さ\(\,3\,\)の巡回置換で生成されるので，\(\,T_{k+1}\,\)がそれらを生成することを言えば十分ですね。
ここで\(\,T_{k+1}=\{(1,2,3),\ldots,(k-2,k-1,k)\}\cup\{(2,3,4),\ldots,(k-1,k,k+1)\}\,\)で，
帰納法の仮定より\(\,\{(1,2,3),\ldots,(k-2,k-1,k)\},\{(2,3,4),\ldots,(k-1,k,k+1)\}\,\)はそれぞれ\(\,A_k\,\)と同型な群を生成します。
そのため\(\,1,k+1\,\)の一方のみしか現れない長さ\(\,3\,\)の巡回置換は\(\,T_{k+1}\,\)によって生成されることが分かります。
また\(\,(1,k+1,x)=(1,x,k+1)^2\,\)なので，\(\,(1,x,k+1)\,\,(x\not=1,k+1)\,\)という形のものを生成することを言えば十分になります。
\(k+1\geq 4\)より，\(\,y\in \{1,\ldots,k+1\}\setminus\{1,x,k+1\}\,\)が取れるので，それを利用すると
\((1,x,k+1)=(1,x,y)(y,x,k+1)\)
と\(\,1,k+1\,\)の一方のみしか現れない長さ\(\,3\,\)の巡回置換で表すことができます。
故に帰納法によって，補題2は示されました。\(\quad\square\)
ようやく目玉の定理です。
定理3
15パズルの操作によって生成される部分群\(\,G\,\)は\(\,A_{15}\,\)である。
補題2より\(\,G\,\)の生成元が\(\,(1,2,3),\ldots,(13,14,15)\,\)を生成することを言えば良いです。
巡回置換の公式\(\,\sigma(a_1,\ldots,a_k)\sigma^{-1}=(\sigma(a_1),\ldots,\sigma(a_k))\,\)を利用すると，
\(-2\leq n \leq 2\,\)について
となるので，題意は示されました。\(\quad\square\)
結論
15パズルの可解性
配置\(\,Pl_1,Pl_2\,\)の属する配列をそれぞれ\(\,Cf_1,Cf_2\,\)とおく。このとき次の必要十分条件が成り立つ。
\(\phantom{\Leftrightarrow}\,\)初期配置\(\,Pl_1\,\)から目的配置\(\,Pl_2\,\)へ組み替えることができる。
\(\Leftrightarrow\,\)配列\(\,Cf_2\,\)は配列\(\,Cf_1\,\)を偶置換で並び替えたものになっている。
これまでの議論をまとめると上のようになります。
15パズルは結局，配列に\(\,15\,\)次交代群\(\,A_{15}\,\)の元を作用させていくものと証明したからですね。
配列はあくまで，配置の同値類なので，分かりやすいように配置の言葉に置き換えて表現しましょう。
サム・ロイド(Sam Loyd)の問題のときと同様に色分けし，
配置\(\,Pl_1,Pl_2\,\)の空ブロックの乗っているマスが同じ色なら，\(\,n(P_1,P_2)=0\,\)
異なる色なら\(\,n(Pl_1,Pl_2)=1\,\)
と定めます。
このとき\(\,n(Pl_1,Pl_2)\,\)は，\(\,Pl_1,Pl_2\,\)は空ブロックを揃えるのに必要な互換の個数の合計の偶奇に一致しますね。
あくまで「配列」ではなく「配置」なので，この時点では\(\,16\,\)個のマスの番号の置換としての意味であることに注意してください。
空ブロックの位置を揃えた状態では，残りの\(\,15\,\)ブロックを揃えるという問題に帰着され，これは先ほどの配列において考えた問題として捉えられます。
※少々分かりづらいですが，配置\(\,Pl_1,Pl_2\,\)を標準形にそろえたとき，実質的に配列にみなせることを意識すると個人的には分かりやすいと思います。
そうすると，配置の言葉では次のように表されることが分かります。
15パズルの可解性
\(n(Pl_1,Pl_2)=0\,\)のとき
\(\phantom{\Leftrightarrow}\,\)初期配置\(\,Pl_1\,\)から目的配置\(\,Pl_2\,\)へ組み替えることができる。
\(\Leftrightarrow\,\)配置\(\,Pl_2\,\)は配置\(\,Pl_1\,\)を偶置換で並び替えたものになっている。
\(n(Pl_1,Pl_2)=1\,\)のとき
\(\phantom{\Leftrightarrow}\,\)初期配置\(\,Pl_1\,\)から目的配置\(\,Pl_2\,\)へ組み替えることができる。
\(\Leftrightarrow\,\)配置\(\,Pl_2\,\)は配置\(\,Pl_1\,\)を奇置換で並び替えたものになっている。
これにて15パズルの可解性ははっきりしました。
またこのことから，初期配置を固定したとき，目的配置として可解なものの個数はちょうど
\(\,\dfrac{16!}{2}=10,461,394,944,000\,\)
であることも言えました。
まとめ
今回の記事では15パズル(15 puzzle)を解説いたしました。
簡単そうに見えたパズルに，ここまで豊かな群論の世界が秘められていて，非常に興味深い話題でした。
参考にした論文\(\,[1]\,\)ではさらに発展させて，15パズルの一般化についても触れられています。
その一般化においても特別な場合を除いて，パズルの操作によって生成される群は交代群\(\,A_n\,\)か対称群\(\,\mathfrak{S}_n\,\)になるなどの発展的な話題に触れられています。
気になった方は元論文で，その出典などについて述べられているので，軽く覗いてみてください。
もし「説明がわかりにくい」などご要望・ご感想がありましたら，
X（旧:Twitter）で#サイエンティクスでつぶやいていただけると，できる限り対応します。
ここまで読んでいただき，ありがとうございました。
参考図書
- \([1]\) Archer, A. F. (1999). A Modern Treatment of the 15 Puzzle. The American Mathematical Monthly, 106(9), 793–799. https://doi.org/10.1080/00029890.1999.12005124
- \([2]\) “15 Puzzle — from Wolfram MathWorld”.Wolfram.https://mathworld.wolfram.com/15Puzzle.html
- \([3]\) オキト.“15パズル | 無料ゲームは「ゲームのつぼ」”.ゲームのつぼ.https://www.afsgames.com/15puzzle.htm..2025-08-26参照
