15パズル
15パズルは、スライディングブロックパズル（Sliding puzzle）の一種である。4×4のボードの上に4×4-1すなわち15枚の駒があり、1駒分の空所を利用して駒をスライドし、駒を目的の配置にする。3×3のボード上で8枚の駒で同様に遊ぶものは8パズルと呼ばれる。m×nのボードとm×n-1個の駒（m, n ≧ 2）に一般化できる。右下の隅または左上の隅を空所とした配置を最終目標とするものが多い。
原案は1874年にノイス・チャップマン（Noyes Palmer Chapman）が、GEM PUZZLEとして考案していたものである。
概要編集
空所を利用した駒の移動のみが正しい手として許され、複数個の駒を外して並べ直すといったことが許されない等は他のスライディングブロックパズルと同様である。左上からカレンダーのような順に並べた配置に戻す、あるいはそのような配置から何らかの配置へ並べ替えるパズルである。
冒頭の図では 12 の駒または 15 の駒を移動させることができる。空所に隣接する縦または横に連続した複数の駒を一斉にスライドさせても良い。例えば冒頭の図で 8 と12、13 と 14 と 15を動かす等である。コンピュータゲームでは、スワイプ等でそのような操作を許すようプログラミングされているものもある。ただし、最短手数などの評価では「1手」が異なったものになる。
「数字の渦巻き」という問題を例とする。まず、初期配置は以下の通りである。
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
ひとつの手法として、まず上辺や左辺を目的の配置にして固定してしまうことでより小さなサイズのパズルに帰着させ、再帰的に解くというものがある。ただし駒が番号ではなく絵柄等の場合、端の行や列がわかりづらいこともある。コンピュータに解かせる場合も、全局面をなんらかの探索手法で探索して一定時間内に目的の配置に近づく手順が見つからない場合に、同様に部分問題に持ち込むようフォールバックを入れる場合がある。
不可能な配置編集
1878年、パズル作家のサム・ロイド[1]が「15パズルで、14と15 を入れ替えた状態を元に戻す」という、絶対に解けることのない問題に、1,000ドルの賞金をかけて出題した。このパズルで中毒になる人もおり、その懸賞により15パズルは大きく普及。商品も多く販売されるようになった。
不可能な配置については一般化も可能であるが、以下の解説では上記を例とする。
15パズルを数学的に分析すると、1個の駒のスライドという操作は、空所と、その駒の入換えと見ることができ、これは群論でいう「互換」である。ここで、ある状態から操作を続け、空所が元の位置に戻ったとすると、それには必ず偶数回の操作＝偶数回の入換えが必要であり、その配置は元の配置からの偶数回の互換（偶置換）となっている。一方、14と15の入換えは1回の入換えであり、奇置換である。従って、14と15を入れ替えた状態から目的の配置にすることはできない。一般化すると、15パズルではランダムな配置から指定された配置への変換はできないことがある。
これらの解につながる指針は、パズルにおいて「パリティ」とも称される。
外してバラバラにできる駒だと、駒を紛失してしまうこともあるため、スライドはできるが駒を外すことができない構造にした製品などもある。これは、解く事が不可能な状態にしてしまうことが無い、という利点がある一方、パズルとしてはいきなりバラバラの配置にしてしまうことができない、という欠点もある。コンピュータゲームでもmacOSのDashboardウィジェットなどのように、いきなりランダムな配置になるのではなく、目的の配置からバラバラになってゆくようなデモ式のものがある（参考プログラムを参照）。
困難性編集
n×nパズルにおいて、最短手数を求める問題はNP困難である。最短手数の定数倍の変形を求める多項式時間アルゴリズムが提案されている。
8パズルは任意の可能な配置へ31手以内で変形でき、31手が必要な配置は確認されている。15パズルは任意の可能な配置へ80手以内で変形でき、80手が必要な配置は確認されている。
簡単なソルバーをプログラミングする場合、評価関数を各駒の目的の位置までのマンハッタン距離の和とするのが手頃である。
日本での動向編集
日本では明治40年（1907年）に書かれた書物「世界遊戯法大全」に「十五置き換え遊び」の名で紹介されている。
他の古典的スライディングブロックパズルと同様、多数のパズル業者が製造・販売している。前述のように駒が外れない構造のものもある。また番号でなく何らかの絵柄をあしらって、いわゆるキャラクター商品等とするにも手頃であるため、そういった商品も多く「セイカのパズル できるんです！」等がある。絵柄の場合ジグソーパズル等と違い、区別が不可能な駒は避ける必要がある。
コンピュータゲーム編集
コンピュータゲームとしての実装も多く、macOSのDashboard用Widgets（ウィジェット）やWindows Vistaのガジェット等、デスクアクセサリ型アプリが多い。『ファイナルファンタジー』（第一作、作中のミニゲーム）や『ゼルダの伝説 風のタクト』（作中のミニゲーム）など、ミニゲームとして仕込まれることも多い。
15パズルのルールを応用した落ち物パズルゲームの一種としては、1990年に発売されたメガドライブ用ソフト『メガパネル』がある。
参考プログラム編集
コンピュータプログラムで動作する15パズル（外部リンク） - 総合情報通信技術研究機関 ADS 名古屋電算技術室
ページ下部にある「Script samples」の中から「Sliding 15 puzzle」を探し、1回押すと、ページ上部のFormulaウィンドウに15パズルを再現する式が入力される（押した数だけ入力されるため、連続押下に注意されたい）。その状態で演算ボタン（画面内キーボード最下段の右隅にある「＝」ボタン）を押すとページがリロードされ、Answerウィンドウに15パズルが再現される。
シャッフルの無効化編集
本プログラムには「不可能な配置」項で触れた「目的の配置からバラバラになってゆくデモ」を再現するコードも含まれており、デフォルトの式では開始時にシャッフルが実行される。この処理は式の末尾に記述されている ,s=setInterval(m,1); を除去するか、以下のように当該コードの直前に // を挿入し
visibility=h//,s=setInterval(m,1);
それ以降の記述をコメント扱いにすることで無効化できる。
不可能な配置の再現編集
式中にある以下の部分を次のように変更し
for(i=1;17>i;i++)
↓
for(i=0;16>i;i++)
(i-1) を i に変更し
(i-1) → i
さらに2箇所に存在する $[15] を $[0] に変更すると
$[15] → $[0]
先に示した「不可能な配置」に等しい状態を意図的に作り出すことも可能である。その場合の初期配置を図で示すと以下のようになる。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
この配置も、14と15を入れ替えた状態に等しい意味を含む。すなわち上述のコンピュータプログラムを用いて検証すれば、14と15を入れ換えた状態から「右下を空所とする目的の配置」には並べられないが、図の「左上を空所とする目的の配置」には並べることが可能であり、反対に14と15を入れ替えたに等しい状態となっておらねば、図の配置には並べられないことが分かる。
参考文献編集
- 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
注編集
外部リンク編集
- 14-15パズルはなぜ解けないか？ - archive.today（2015年1月1日アーカイブ分） - 松井知己[リンク切れ]