料理が作れるわけではないです。パズルとか謎解きとかを好んでやっています。今日はパズルの話です。転倒数をざっくりと話して15パズルの話をします。転倒数とは最短何手で入れ替えることが出来るかの数のこと。[1,2,3,4,5,6,7,8,9,10]→[10,9,8,7,6,5,4,3,2,1]となった場合を考える。この時、各要素において本来自分より前にあるものが何個かを数える。操作後の8の前には10と9があるが、元々はどちらも8より後にあるべきものであるため、転倒数に2を追加する。これを繰り返すと、転倒数が45であると分かる。何の役に立つのかあみだくじと15パズルを例として挙げる。あみだくじ例えばこういうあみだくじがあるとする。E[A,B,C,D,E]→[E,B,D,C,A]になっている。ここであみだくじの横線は転倒数を計算するときと同じように隣の物を交換しているので、横棒の数は実質転倒数と分かる。Bこういうあみだくじを考えると[A,B]→[A,B]なのに横棒の数は0ではない。横棒の数は転倒数と確実に同じという訳ではない。2ずつ増えることは確かなようだ。ここで重要な概念として偶置換・奇置換というものがある。説明すると「[A,B]→[A,B]というあみだくじにおいて横線が奇数本である物は存在しない」みたいな感じ。これを15パズルに応用する。15パズル11/15だし...123456789101112131415✕15パズルは一般的には上図を目指す遊び。123456789101112131514✕でも先ほどの奴から上図は作れない。これは先ほどの偶置換・奇置換から説明が出来る。直接的な入れ替えという操作が出来ない以上無理なものは無理である。2つめに上げたやつをどうにか動かすと以下のようになる。✕123456789101112131415動かして成立するということは両者の偶奇は一致しているし、一番最初の奴と偶奇は一致しない。上図を少し動かした123745611891015121314✕を考えて、これを[1,2,3,7,4,5,6,11,8,9,10,15,12,13,14]とする。[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]を一つ目かつ基準とすると2つ目を表す[1,2,3,4,5,6,7,8,9,10,11,12,13,15,14]の転倒数は13つ目を表す[1,2,3,7,4,5,6,11,8,9,10,15,12,13,14]の転倒数は9と、確かに2つ目と3つ目の偶奇は一致しているし1つ目(転倒数0)との偶奇は一致していない。12131415のどちらかの形には必ずなると分かった。これを応用した15パズルを実際に作ってみた。転倒数を数えないと余計に手数がかかるので、計算する暇がある人は挑戦してみてね~。おわりに転倒数と15パズルのお話でした。明日のアドベントカレンダーの担当はryuonさんです!楽しみ~この記事を書いた人RyoTei18の競プロのアマ。Pythonを勉強している。