15パズル（読み）じゅうごパズル（英語表記）Fifteen Puzzle

ブリタニカ国際大百科事典 小項目事典

15パズル
じゅうごパズル
Fifteen Puzzle

1～15の番号が書かれた 15個の正方形の駒を，4×4の碁盤目状のボード上で一つだけ空いた枡に動かすことにより，番号順に並べ替えるパズル。ジェム・パズル，ボス・パズル，ミスティック・スクエアとも呼ばれる。1878年頃にサム・ロイドが考案したとされるが，もっと早くにつくられていたことを示す文献もある。1880年頃，ヨーロッパ中で一斉に人気を博した。20兆通り以上もの異なる駒の配置がありうるといわれたが，1879年に 2人のアメリカ合衆国の数学者が，解くことができる配置は 10兆通り前後であることを証明した。数学的な解析によれば，左上から右下へ駒が正規の配置に並んでいる場合，それぞれの駒の番号は，前に置かれたどの駒よりも大きい。つまり，どの駒も自分より小さい番号の駒の前に置かれることはない。一方，正規以外の配置では，一つ以上の駒が自分より小さい番号の駒の前に置かれる。このような配置を「転置」と呼ぶ。たとえば，9，5，3，4という数列では，9は自分より小さい番号の三つの駒の前，5は自分より小さい番号の二つの駒の前にあり，計五つの転置があることになる。転置の総数が偶数であれば，駒を正規の配置に戻すことができるためパズルは解けるが，転置の総数が奇数だと解けない。このパズルにはもっと大きなボードを用いることも理論上は可能で，枡目が m×nのボードの場合，1～（mn－1）の番号をふった駒を使う。

出典　ブリタニカ国際大百科事典 小項目事典