この記事はtraP Advent Calender 2018 22日目の記事です。

18の料亭です。料理が作れるわけではないです。
パズルとか謎解きとかを好んでやっています。

今日はパズルの話です。転倒数をざっくりと話して15パズルの話をします。

以下常体です。

転倒数とは

最短何手で入れ替えることが出来るかの数のこと。

[七,八,転,倒]　→　[七,転,八,倒]　なら

[七,八,転,倒]→[七,転,八,倒]

より１手なので転倒数は１

[八,転,七,倒]　→　[七,転,八,倒]　なら

[八,転,七,倒]→[転,八,七,倒]→[転,七,八,倒]→[七,転,八,倒]

より３手なので転倒数は３　という感じになる。

何の役に立つのか

あみだくじと15パズルを例として挙げる。

あみだくじ

例えばこういうあみだくじがあるとする。

Ａ　Ｂ　Ｃ　Ｄ　Ｅ
｜　｜　｜　｜　｜
｜ー｜　｜ー｜　｜
｜　｜ー｜　｜ー｜
｜　｜　｜ー｜　｜
｜　｜ー｜　｜　｜
｜ー｜　｜　｜ー｜
｜　｜　｜　｜　｜
Ａ　Ｂ　Ｃ　Ｄ　Ｅ

[Ａ,Ｂ,Ｃ,Ｄ,Ｅ]→[Ｅ,Ｂ,Ｄ,Ｃ,Ａ]になっている。この転倒数は８。
ここであみだくじの横線は転倒数を計算するときと同じように隣の物を交換しているので、横棒の数は実質転倒数と分かる。

Ａ　Ｂ
｜ー｜
｜－｜
Ａ　Ｂ

こういうあみだくじを考えると[Ａ,Ｂ]→[Ａ,Ｂ]なのに横棒の数は０ではない。
つまり、横棒の数は転倒数と確実に同じという訳ではない。でも２ずつ増えることは確かなようだ。

ここで重要な概念として偶置換・奇置換というものがある。

ざっくり説明すると
「[Ａ,Ｂ]→[Ａ,Ｂ]というあみだくじにおいて横線が奇数本である物は存在しない」
みたいな感じ。これを15パズルに応用する。

15パズル

11/15だし…

15パズルは一般的には上図を目指す遊び。

でも先ほどの奴から上図は作れない。

これは先ほどの偶置換・奇置換から説明が出来る。直接的な入れ替えという操作が出来ない以上無理なものは無理である。

さて、２つめに上げたやつをどうにか動かすと以下のようになる。

動かして成立するということは両者の偶奇は一致しているし、一番最初の奴と偶奇は一致しない。例えば上図を少し動かした

を考えて、これを[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]を一つ目かつ基準とすると

２つ目を表す[1,2,3,4,5,6,7,8,9,10,11,12,13,15,14]の転倒数は１
３つ目を表す[1,2,3,7,4,5,6,11,8,9,10,15,12,13,14]の転倒数は９

と、確かに２つ目と３つ目の偶奇は一致しているし１つ目(転倒数０)との偶奇は一致していない。転倒数は偶数または奇数であるため、

のどちらかの形には必ずなると分かった。

これを応用した15パズルを実際に作ってみた。

転倒数を数えないと余計に手数がかかるので、計算する暇がある人は挑戦してみてね～。

おわりに

転倒数と15パズルのお話でした。

明日のアドベントカレンダーの担当はryuonさんです！楽しみ～