15パズル
15パズルは、4×4のボードの上で15枚の駒を、空いたマス目を利用して動かし、目的の形にするパズルである。3×3のボード上で8枚の駒を同様にして動かすものは8パズルと呼ばれる。スライディングブロックパズルに分類される。
解き方
空白部分に隣接する駒をスライドすることで盤面を操作する(冒頭の図では 12 の駒または 15 の駒を移動させることができる)。空白部分に隣接する、縦又は横に連続した複数の駒を一斉にスライドさせる(例えば冒頭の図で 8 と12、13 と 14 と 15)としても変わらない。
「数字の渦巻き」という問題を例とする。まず、初期配置は以下の通りである。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
たとえば、「8」の駒を下にずらせば次のようになる。
1 2 3 4 5 6 7 9 10 11 8 13 14 15 12
次に「5」を右にずらせば次のようになる。
1 2 3 4 5 6 7 9 10 11 8 13 14 15 12
これを繰り返して目的の形にする。
1 2 3 4 12 13 14 5 11 15 6 10 9 8 7
初期配置が解ける配置である場合には、端の一行一列を目的の配置にすれば、より小さなサイズのパズルに帰着されるので再帰的にパズルを解くことができる。
不可能な配置
15パズルで一つの駒のスライドという動作は数学的には空いたマス目との互換と考えられる。この操作に関して、任意の2つの駒のみを入れ替える(他のものは変えない)ためには、空いたマス目が偶数回の操作を経て元の場所に戻らなければならない。二つの駒を入れ替えることは一つの互換、つまり奇置換で表され、空いたマス目に対する操作は偶置換で表されるため、15パズルで単に二つの駒を入れ替えるという操作は不可能である。したがってランダムな配置から指定された配置への変換はできないことがある。
この例として、サム・ロイドの提示した「14 と 15 を入れ替えた状態を元に戻す」という問題がある。ロイドは（絶対に解けることのない）この問題に1000ドルの賞金をかけて出題した。この懸賞をかけた事により15パズルは大きく普及し、15パズルの商品も多く販売されるようになった。
パズルとして実体化される際には、このような問題が起きないように、15個の駒をケースから外せないように工夫されているものが多い。例えば 15個の駒の上辺と左辺の側面を凹、下辺と右辺の側面を凸にして、スライドできかつケースから取り外されないように(ケースの内側の4辺にも凸凹が施される)工夫がなされている。
困難性
8パズルは任意の可能な配置へ31手以内で変形できる。31手が必要な配置は存在する。15パズルは任意の可能な配置へ80手以内で変形できる。80手が必要な配置は存在する。
n×nパズルにおいて、最短手数を求める問題はNP困難である。最短手数の定数倍の変形を求める多項式時間アルゴリズムが提案されている。
日本での動向
日本では明治40年（1907年）に書かれた書物「世界遊戯法大全」に「十五置き換え遊び」の名で紹介されている。
また、派生商品として1990年ごろに「できるんです」という商品名で、アニメのキャラクターを盤面にプリントした大きめの15パズルが発売されていた。「できるんです」の盤面イラストは基本的に16ピースから成り立っており、左上の駒をさらに上にある、駒が一つだけ入る隙間に一時的にスライドさせて置くことで他の駒を自由にスライドさせることができる。
コンピュータゲーム
コンピュータゲームとして、バラバラにした画像を元に戻すというパズルゲームに用いられることがある。Mac OS Xには Dashboard用Widgets（ウィジェット）の一つとして、Windows Vistaにはガジェットの一つとしてこのパズルが搭載されている。また、ファイナルファンタジーやゼルダの伝説 風のタクトなどでも遊ぶことができる。
関連項目
参考文献
- Jerry Slocum「The 15 Puzzle」ISBN 1-890980-15-3
- A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt ``The parallel search bench ZRAM and its applications," Annals of Operations Research, Volume 90, Number 0, 1999, pp. 45-63.
- Daniel Ratner and Manfred Warmuth ``The (n^2-1)-puzzle and related relocation problems," Journal of Symbolic Computation, Volume 10 , Issue 2 (1990), pp. 111-137
