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困難こんなんである^[2]。最短さいたん手数てかずの定数ていすう倍ばいの変形へんけいを求もとめる多項式たこうしき時間じかんアルゴリズムが提案ていあんされている。

8パズルは任意にんいの可能かのうな配置はいちへ31手て以内いないで変形へんけいでき、31手てが必要ひつような配置はいちは確認かくにんされている^[3]。15パズルは任意にんいの可能かのうな配置はいちへ80手て以内いないで変形へんけいでき、80手てが必要ひつような配置はいちは確認かくにんされている^[4]。

簡単かんたんなソルバーをプログラミングする場合ばあい、評価ひょうか関数かんすうを各かく駒こまの目的もくてきの位置いちまでのマンハッタン距離きょりの和わとするのが手頃てごろである。

日本にっぽんでの動向どうこう[編集へんしゅう]

日本にっぽんでは明治めいじ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
Brüngger, A.; Marzetta, A.; Fukuda, K.; Nievergelt, J. (1999), “The parallel search bench ZRAM and its applications”, Annals of Operations Research 90 (2): 45–63, doi:10.1023/A:1018972901171
Ratner, D.; Warmuth, M. (1990), “The $(n 2 -1)$ -puzzle and related relocation problems”, Journal of Symbolic Computation 10 (2): 111–137, doi:10.1016/S0747-7171(08)80001-6
Reinefeld, A. (1993), “Complete solution of the eight-puzzle and the benefit of node ordering in IDA*” (PDF), Proceedings of the 13th international joint conference on Artificial intelligence 1: 248–253