15パズル

15パズルの目的の配置、ないし初期配置

15パズルは、スライディングブロックパズル(Sliding puzzle)のひとつである。4×4のボードの上に4×4-1すなわち15枚のがあり、1駒ぶんの空きを利用して駒をスライドし、駒を目的の配置にする。3×3のボード上で8枚の駒で同様に遊ぶものは8パズルと呼ばれる。m×nのボードとm×n-1個の駒(m, n ≧ 2)に一般化できる。目的の配置において右下の隅ないし左上の隅を空きとしたものが多い。

目次

  • 概要 1
  • 不可能な配置 2
  • 困難性 3
  • 日本での動向 4
  • コンピュータゲーム 5
  • 参考文献 6
  • 7
  • 外部リンク 8

概要

空所を利用した駒の移動のみが正しい手として許され、複数個の駒を外して並べ直すといったことが許されない等は他のスライディングブロックパズルと同様である。左上からカレンダーのような順に並べた配置に戻す、あるいはそのような配置から何らかの配置へ並べ替えるパズルである。

冒頭の図では 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

ひとつの手法として、まず上辺や左辺を目的の配置にして固定してしまうことでより小さなサイズのパズルに帰着させ、再帰的に解くというものがある。ただし駒が番号ではなく絵柄等の場合、端の行や列がわかりづらいこともある。コンピュータに解かせる場合も、全局面をなんらかの探索手法で探索して一定時間内に目的の配置に近づく手順が見つからない場合に、同様に部分問題に持ち込むようフォールバックを入れたりする。

天才パズル作家・サム・ロイド[1]が「15パズルで、14と15 を入れ替えた状態を元に戻す」という(絶対に解けることのない(後述))問題に1,000ドルの賞金をかけて出題したため、その懸賞により15パズルは大きく普及し、15パズルの商品も多く販売されるようになった。

不可能な配置

解けない問題

このパズルの初期配置として有名な例に「目的の配置から14と15を入れ替えた状態」というものがある。一般化も可能だが、まずはこれを例として考える。

15パズルを数学的に分析すると、1個の駒のスライドという操作は「空き」とその駒の入換えと見ることができ、これは群論でいう「互換」である。ここで、ある状態から操作を続けて元の位置に空きが戻ったとすると、それには必ず偶数回の操作=偶数回の入換えが必要であり、その配置は元の配置からの偶数回の互換(偶置換)となっている。一方、14と15の入換えは1回の入換えであり、奇置換である。従って、14と15を入れ替えた状態から目的の配置にすることはできない。一般化すると、15パズルではランダムな配置から指定された配置への変換はできないことがある。[2]

パズルでは「パリティの考え方」といったようにも言われる。

外してバラバラにできる駒だと、駒を紛失してしまうこともあるため、スライドはできるが駒を外すことができない構造にした製品などもある(後述。自作例もある[3])。副作用として、上述のような不可能な状態にしてしまうことが無い、という利点がある一方、パズルとしてはいきなりバラバラの配置にしてしまうことができない、という欠点とも言える。コンピュータゲームでも、いきなりランダムな配置になるのではなく、目的の配置からバラバラになってゆくようなデモ式のものがある(OS XのDashboardウィジェットなど)。

困難性

n×nパズルにおいて、最短手数を求める問題はNP困難である。最短手数の定数倍の変形を求める多項式時間アルゴリズムが提案されている。

8パズルは任意の可能な配置へ31手以内で変形でき、31手が必要な配置は確認されている。15パズルは任意の可能な配置へ80手以内で変形でき、80手が必要な配置は確認されている。

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

日本での動向

日本では明治40年(1907年)に書かれた書物「世界遊戯法大全」に「十五置き換え遊び」の名で紹介されている。

他の古典的スライディングブロックパズルと同様、多数のパズル業者が製造・販売している。前述のように駒が外れない構造のものもある。また番号でなく何らかの絵柄をあしらって、いわゆるキャラクター商品等とするにも手頃であるためそういった商品も多く「セイカのパズル できるんです!」等がある。絵柄の場合ジグソーパズル等と違い、区別が不可能な駒は避ける必要がある。

コンピュータゲーム

コンピュータゲームとしての実装も多く、Mac OS XDashboard用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

  1. ^ 伴田良輔『巨匠の傑作パズルベスト100』 〈文春新書 2008年〉pp.26-30に詳しいが、1878年、ロイドが37歳で出したパズルで「中毒」になる人もいた。原案は1874年にノイス・チャップマン(Noyes Palmer Chapman)がGEM PUZZLEとして考案していたが、ロイドは不可能を知っていたからこそ賞金をかけた。
  2. ^ 注意: ここでは「偶置換であれば必ず解ける」かどうかについては議論していない。
  3. ^ http://kmaebashi.com/essay/puzzle.html

外部リンク

  • 14-15パズルはなぜ解けないか? - 松井知己
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.