15パズル
1878年、パズル作家のサム・ロイドが「15パズルで、14と15 を入れ替えた状態を元に戻す」という、絶対に解けることのない問題に、1,000ドルの賞金をかけて出題した。このパズルで中毒になる人もおり、その懸賞により15パズルは大きく普及。商品も多く販売されるようになった。
不可能な配置については一般化も可能であるが、以下の解説では上記を例とする。
15パズルを数学的に分析すると、1個の駒のスライドという操作は、空所と、その駒の入換えと見ることができ、これは群論でいう「互換」である。ここで、ある状態から操作を続け、空所が元の位置に戻ったとすると、それには必ず偶数回の操作=偶数回の入換えが必要であり、その配置は元の配置からの偶数回の互換(偶置換)となっている。一方、14と15の入換えは1回の入換えであり、奇置換である。従って、14と15を入れ替えた状態から目的の配置にすることはできない。一般化すると、15パズルではランダムな配置から指定された配置への変換はできないことがある。
これらの解につながる指針は、パズルにおいて「パリティ」とも称される。
外してバラバラにできる駒だと、駒を紛失してしまうこともあるため、スライドはできるが駒を外すことができない構造にした製品などもある。これは、解く事が不可能な状態にしてしまうことが無い、という利点がある一方、パズルとしてはいきなりバラバラの配置にしてしまうことができない、という欠点もある。コンピュータゲームでもmacOSのDashboardウィジェットなどのように、いきなりランダムな配置になるのではなく、目的の配置からバラバラになってゆくようなデモ式のものがある(参考プログラムを参照)。