2018年11月15日 | ブログ記事

転倒数と15パズル【アドベントカレンダー2018 22日目】

RyoTei

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

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

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

以下常体です。


転倒数とは

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

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

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

より1手なので転倒数は

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

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

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

もう少しちゃんとした計算方法 例えば[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パズルを例として挙げる。

あみだくじ

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

A B C D E
| | | | |
|ー| |ー| |
| |ー| |ー|
| | |ー| |
| |ー| | |
|ー| | |ー|
| | | | |
A B C D E

[A,B,C,D,E]→[E,B,D,C,A]になっている。この転倒数は8。
ここであみだくじの横線は転倒数を計算するときと同じように隣の物を交換しているので、横棒の数は実質転倒数と分かる。

A B
|ー|
|-|
A B

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

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

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

15パズル

11/15だし…


①②③④
⑤⑥⑦⑧
⑨⑩⑪⑫
⑬⑭⑮✕

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

①②③④
⑤⑥⑦⑧
⑨⑩⑪⑫
⑬⑮⑭✕

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


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

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

✕①②③
④⑤⑥⑦
⑧⑨⑩⑪
⑫⑬⑭⑮

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

①②③⑦
④⑤⑥⑪
⑧⑨⑩⑮
⑫⑬⑭✕

を考えて、これを[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]の転倒数は
3つ目を表す[1,2,3,7,4,5,6,11,8,9,10,15,12,13,14]の転倒数は

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

①②③④ ✕①②③
⑤⑥⑦⑧ ④⑤⑥⑦
⑨⑩⑪⑫ ⑧⑨⑩⑪
⑬⑭⑮✕ ⑫⑬⑭⑮

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


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

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


おわりに

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

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

この記事を書いた人
RyoTei

18の競プロのアマ。Pythonを勉強している。謎解きが趣味

この記事をシェア

このエントリーをはてなブックマークに追加

関連する記事

2018年12月19日
ゾーマからの脱出〜後編〜
ran
2018年12月18日
ゾーマからの脱出~前編~
Meffi
2018年12月17日
ワンモデ参加記
nao
2018年12月16日
2018年のクッキー職人が知っておくべきこと
spa
2018年12月16日
ICPCアジア地区横浜大会参加記【アドベントカレンダー2018 52日目】
eiya
2018年12月15日
合宿免許【アドベントカレンダー2018 52日目】
osushi

活動の紹介

カテゴリ

タグ