15パズル
出典: フリー百科事典『ウィキペディア（Wikipedia）』
 |
15パズルは、4×4のボードの上で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 |
[編集] 不可能な配置
この移動という動作は数学的には空いた升目との置換と考えられるので、任意の二つの駒のみを入れ替えて他のものは変えないという操作は不可能である。したがってランダムな配置から指定された配置への変換はできないことがある。
変換不可能な配置に関しては、サム・ロイドの提示した「14 と 15 を入れ替えた状態を元に戻す」という問題が有名である。ロイドは（絶対に解けることのない）この問題に1000ドルの賞金をかけて出題したために、このパズルは欧米でブームとなった（偶置換・奇置換と深く関係する。パリティも参照）。
[編集] その他
15パズルはコンピュータ上のコンピュータゲームとして、バラバラにした画像を元に戻すというパズルゲームにしばしば用いられる。
[編集] 参考文献
- "The 15 Puzzle"（英語・Jerry Slocum著）ISBN 1-890980-15-3
