すのものの「15 パズル（およびその拡張）を解く」

このページは，英語で書いた a simple proof on the solvability of the 15 puzzle (and the extended ones) の日本語訳として置いたもので，理論的な解があることだけを示すものだったが， 検索で上のほうにくるようになったので， 実用的な解き方を求めてきた人をがっかりさせないよう， それをここに記しておくことにした。

（これは，私のオリジナルではありません。 ネット上で，多くのかたが，類似の方法を述べておられるようです。）

まず，2×3 のパズルで練習をする。

 1  2  3
 4  5

右下が空白である。 これ以外のコマを裏返すなどして，このサイズでよく練習しよう。 ランダムに 5 つのコマを置くと，次のどちらかにたどりつける。

 1  2  3        1  2  3
 4  5           5  4

最大で 14 手かかるので，それほど自明ではない。

これができたら，15 パズルに取り組む。 まず，大かっこ [ ] で囲んだ中に 1 と 2 のコマと空白をもってくる。 これは何とかできるはずだ。

[?  ?  ?] ?
[?  ?  ?] ?
 ?  ?  ?  ?
 ?  ?  ?  ?

ここで前の練習を思い出せば，1 と 2 と正しい位置に移動できる。

次に，1 と 2 は動かさずに，3 と 4 と空白を次の図の大かっこの中にもってくる。

 1  2 [?  ?]
 ?  ? [?  ?]
 ?  ? [?  ?]
 ?  ?  ?  ?

そして 2×3 のときを思い出し，3 と 4 を正しい位置に移動する。 ここはさっきの練習とはちょっと様子が違うが，次の図のようになればあとはすぐである。

 1  2 [?  3]
 ?  ? [?  4]
 ?  ? [?  ?]
 ?  ?  ?  ?

次は，1 から 4 までは動かさずに，5 と 6 と空白を次の図の大かっこの中にもってくる。

 1  2  3  4
[?  ?  ?] ?
[?  ?  ?] ?
 ?  ?  ?  ?

そしてこの大かっこの中だけで移動をおこない，5 と 6 を正しい位置にもってくる。

次は，1 から 6 までは動かさずに，7 と 8 と空白を次の図の大かっこの中にもってきて， それから，7 と 8 を正しい位置に移動する。

 1  2  3  4
 5  6 [?  ?]
 ?  ? [?  ?]
 ?  ? [?  ?]

次は，1 から 8 までは動かさずに，9 と 13 と空白を次の図の大かっこの中にもってきて， それから，9 と 13 を正しい位置に移動する。

 1  2  3  4
 5  6  7  8
[?  ?  ?] ?
[?  ?  ?] ?

あとは，残った五個のコマを正しい位置に移動する。 これは失敗することもある。最終的には，次のどちらかがゴールである。

 1  2  3  4     1  2  3  4
 5  6  7  8     5  6  7  8
 9 10 11 12     9 10 11 12
13 14 15       13 15 14

（以上から，最初のコマの配置が偶置換であれば，解けることがわかる。 解けなければ奇置換であるから。）

（次の行から， a simple proof on the solvability of the 15 puzzle (and the extended ones) の日本語版が始まる。）

もしもコマの置換が偶置換であれば 15 パズルには（理論的な）解があることを示す。

15 個のコマを下のループに沿って動かす。

ゲームの目的を，このループに沿って 1, 2, 3, ..., 15 と並べること，に取り換えてもよい。

コマ "c" を右に動かす。

すると "...abc..." が "...cab..." に変わる。

これを二回おこなうと次のようになる。 "...abcd..." → "...adbc..." → "...badc...".

これを二回おこなうと次のようになる。 "...abcdef..." → "...badcef..." → "...bacdfe..."。 三度おこなうと次のようになる。 "...abcdefgh..." → "...badcefgh..." → "...bacdfegh..." → "...bacdefhg..."。

"...ab...cd..." を考えよう。 もしも "ab" と "cd" との間のコマの数が奇数であれば， "cd" と "ab" との間のコマの数は偶数である。 なぜなら，コマの数は全部で奇数個であるから。 （あるいは， ...abxcd... → ...abdxc... → ...axbdc... → ...baxdc... などを使う。）

これで， “隣り合ったペア”の任意のペアに同時に転置をおこなうことができるとわかった。 つまり，次ができる。 "...ab...cd..." → "...ba...dc...".

残りは，置換群とその元の符号を知っていればほとんど明らかである。 まず，上の操作で 14 と 15 を隣り合わせにする。 次に，1 から 13 までのコマのうち隣り合ったペアと， ペア 14, 15 に同時に転置をほどこす。 これをくり返して， 1, 2, ..., 14, 15 とできれば成功， 1, 2, ..., 15, 14 となったら失敗である。

3×3 - 1 パズル

最初に 1 を固定する。

それから，次のループに沿って動く。

動くコマの数は奇数であることに注意。

N×N - 1 パズル（N は奇数，3 以上)

最初に中央のコマ "*" を固定する。

それから，次のループに沿って動く。

あるいは次でもよい。

2×N - 1 パズル（N は 2 以上）

次のループに沿って動く。

M×N - 1 パズル（N は偶数，4 以上）

次のループに沿って動く。

M×N - 1 パズル（M, N は奇数，3 以上，M ≠ N）

M < N と仮定してよい。N - M は偶数であることに注意。

参考：(123)(234) = (12)(34), (123)(234)(345) = (12)(45).

《すのものの「風変わりなソートアルゴリズム（15 パズルに関連）」》も見られたい。 わずかだがより実践的な解法が得られる。

《すのものの「15 パズルを解く C プログラム」》もご覧いただきたい。