feature image

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

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

この記事は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 icon
この記事を書いた人
RyoTei

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

この記事をシェア

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

関連する記事

ERC20トークンを用いた宝探しゲーム(真)の提案【アドベントカレンダー2018 10日目】 feature image
2018年11月3日
ERC20トークンを用いた宝探しゲーム(真)の提案【アドベントカレンダー2018 10日目】
Azon icon Azon
2018年12月12日
多重スリーブの世界と,各種進捗報告。
Silviase icon Silviase
2018年12月23日
LogicProXでのサラウンド設定,オーケストラ用テンプレ作成,その他の小ネタ
SolunaEureka icon SolunaEureka
2018年12月16日
ICPCアジア地区横浜大会参加記【アドベントカレンダー2018 52日目】
eiya icon eiya
2018年11月30日
Flutterでスマホアプリを作ってみ(た | よう)【アドベントカレンダー2018 37日目】
Fourmsushi icon Fourmsushi
2018年12月23日
線形解読法
nari icon nari
記事一覧 タグ一覧 Google アナリティクスについて