不可能な配置
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/06/02 05:07 UTC 版)
このパズルの初期配置として有名な例に「目的の配置から14と15を入れ替えた状態」というものがある。一般化も可能であるが、まずはこれを例とする。 15パズルを数学的に分析すると、1個の駒のスライドという操作は、空所と、その駒の入換えと見ることができ、これは群論でいう「互換」である。ここで、ある状態から操作を続け、空所が元の位置に戻ったとすると、それには必ず偶数回の操作=偶数回の入換えが必要であり、その配置は元の配置からの偶数回の互換(偶置換)となっている。一方、14と15の入換えは1回の入換えであり、奇置換である。従って、14と15を入れ替えた状態から目的の配置にすることはできない。一般化すると、15パズルではランダムな配置から指定された配置への変換はできないことがある。 パズルでは「パリティの考え方」といったようにも言われる。 外してバラバラにできる駒だと、駒を紛失してしまうこともあるため、スライドはできるが駒を外すことができない構造にした製品などもある。これは、解く事が不可能な状態にしてしまうことが無い、という利点がある一方、パズルとしてはいきなりバラバラの配置にしてしまうことができない、という欠点もある。コンピュータゲームでもmacOSのDashboardウィジェットなどのように、いきなりランダムな配置になるのではなく、目的の配置からバラバラになってゆくようなデモ式のものがある。
※この「不可能な配置」の解説は、「15パズル」の解説の一部です。
「不可能な配置」を含む「15パズル」の記事については、「15パズル」の概要を参照ください。
- 不可能な配置のページへのリンク