15パズル

15パズルとは

15パズルは、スライディングブロックパズルの一種で、4x4の盤上に15枚の駒を配置し、空いたスペースを利用して駒をスライドさせ、特定の配置を目指すパズルゲームです。同様のパズルとして、3x3の盤面で8枚の駒を使う8パズルも存在します。このパズルは、m x nの盤面とm x n - 1個の駒に一般化できます。

歴史

15パズルの原案は、1874年にノイス・チャップマンによって考案されました。

ゲーム概要

15パズルのルールは、空所を利用した駒の移動のみが許され、複数個の駒を外して並べ直すことはできません。目的は、左上からカレンダーのように数字を順番に並べた配置に戻すこと、または特定の配置に並べ替えることです。

例えば、空所に隣接する縦または横に連続した複数の駒を一斉にスライドさせることも可能です。コンピュータゲームでは、スワイプ操作でこのような操作を可能にしているものもあります。

解法

一般的な解法として、まず上辺や左辺を目的の配置にして固定し、より小さなサイズのパズルに帰着させて再帰的に解く方法があります。コンピュータに解かせる場合も、探索手法で一定時間内に目的の配置に近づく手順が見つからない場合に、部分問題に分割することがあります。

不可能な配置について

15パズルには、初期配置によってはどうしても解けないパターンが存在します。これは、パズルの状態が偶置換であるか奇置換であるかによって決まります。サム・ロイドが1,000ドルの懸賞金をかけたという話は誤りであることが、近年の研究で明らかになっています。

15パズルを数学的に分析すると、1個の駒のスライドは、空所と駒の入れ替えと見なせます。この操作は群論でいう互換に相当します。ある状態から操作を続け、空所が元の位置に戻った場合、それは偶数回の操作、つまり偶置換となります。したがって、14と15を入れ替えた状態から目的の配置にすることはできません。

製品の工夫

駒を紛失しないように、スライドはできるが駒を外すことができない構造にした製品もあります。これにより、解くことが不可能な状態になることを防ぎますが、パズルをいきなりバラバラの配置にすることができないという欠点もあります。

困難性

n×nパズルにおいて、最短手数を求める問題はNP困難であることが知られています。

8パズルは任意の可能な配置へ31手以内で変形でき、31手が必要な配置も存在します。15パズルは任意の可能な配置へ80手以内で変形でき、80手が必要な配置も存在します。

簡単なソルバーをプログラミングする場合、評価関数として各駒の目的の位置までのマンハッタン距離の和を用いるのが一般的です。

日本での動向

日本では明治時代に「十五置き換え遊び」として紹介されました。多くのパズル業者が製造・販売しており、駒が外れない構造のものや、キャラクター商品など、様々なバリエーションが存在します。

コンピュータゲーム

コンピュータゲームとしても多くの実装があり、ミニゲームとして組み込まれることもあります。15パズルのルールを応用した落ち物パズルゲームも存在します。

参考プログラム

コンピュータプログラムで動作する15パズルの例が公開されており、動作や実装例を確認できます。また、プログラムを改変して駒の数字を絵柄に置き換えることで、絵合わせパズルを制作する試みも行われています。

参考文献

Jerry Slocum「The 15 Puzzle」
Brüngger, A.; 他、「The parallel search bench ZRAM and its applications」
Ratner, D.; Warmuth, M.,「The (n2−1)-puzzle and related relocation problems」
Reinefeld, A.、「Complete solution of the eight-puzzle and the benefit of node ordering in IDA」

外部リンク

俺嫁スレ ゲーム制作プロジェクト - ADS Calculatorでキャラゲーを作ろう -

もう一度検索