ハノイの塔

ネタ切れなので、今回はお蔵入りだったはずのボツネタです。

ハノイの塔というパズルがありまして、簡単に言えば「インドのお坊さんが世界を破滅させるために物凄い速さで円盤を上げ下げするけど時間がかかっちゃって大変」というものです。
例によって細かいルールはWikipediaとかを読んでください。

さて、こいつはアルゴリズムとか再帰的処理で良く知られていて、「どんなアルゴリズムで解けるか」「最短手数は何手か」というのが問題になったりします。
ですが、パズルとして考えるとなんというか...あまりに簡単じゃないですかね。アルゴリズム的に考えなくても、適当に動かしていれば大体最短手数でクリアできちゃうと思うんですよ。

いや、ちょっと盛りました。
途中で間違った動かし方をしたとしても、少し進めば「今の手順が間違っていること」「どこでどうすれば正しかったか」が分かるので、その度に「ごめん、さっきの間違ってたからやりなおすわ」ってけばおのずと最短手順になるんじゃないですかね。

迷路でたとえるならばこんな感じ。

行き止まりに着いたら前の分かれ道まで戻ってやり直すだけで自動的に最短ルートが見つかります。

対して、複雑なパズルというのはこんな感じ。

Aルートはゴールできませんが、「ゴールできない」ことを発見するためには時間がかかるかもしれません。
B～Dはどれもゴール可能ですが、どれが最短かは全てのゴール可能なルートを発見して比較しなければ分かりません。

ようするに、ハノイの塔は前者なんじゃねっていう主張です。

さて、ハノイの塔では円盤の位置は有限通りで、ある状態からの動かし方は3通りしかないため、状態遷移図を描いてみるのが良さそうです。
状態の表し方として、小さい円盤から順に置いてある棒の番号を並べることとします。
例えば、円盤が3枚のときに[111]は全て1番の棒に刺さっていること、[112]は最小円盤と中円盤が1番の棒に、最大の円盤が2番の棒に差さっていることを表します。円盤は必ず大きい順に刺さるため、複数の円盤が同じ棒の中で何番目か、ということは考える必要がありません。

初期状態は[111]で、ここからできることは最小円盤をどちらかの棒に移す2通りです。どっちに移すのも同じなので同一視して1通りと見なしてもいいのですが、今回は左右対称とかも全て別状態と見なします。
移した後の状態は[211]か[311]。この2つの状態は互いに行き来できますし、[111]に戻ることもできます。
図に表すとこんな感じ

おやおや、これってばシェルピンスキーのギャスケットだ。
フラクタルというやつで、円盤の数を増やしても同じような形になるというやつ。
例えば、円盤を3枚→4枚に増やすと、
1. 円盤を1枚足す毎に状態の数は3倍になる([111]が[1111][1112][1113]の3つに分裂する)ため、上の図を3個描く

2. 一つの三角形から別の三角形への移動は、一番大きい円盤を動かすことと等しいため、三角形の頂点から以下の様にしか移動できない。

3. 繋がりを保ったまま、良い感じに図を動かす

という感じで、以下円盤4枚→5枚以降も同様です。

さて、次はこのパズルを解く人がどう動くのかを検証します。
まず、以下の場所は明らかに通る意味が無い場所です。

次に、以下の動きも明らかな無駄です。

こういう動きをしそうになったら「やっぱやーめた」って言って[231]まで戻ります。
となると、ゴールまで行けるルートはこの2つだけ。

うっかり間違って迂回ルートを進んでしまった場合、[312]→[322]あたりで遠回りしていることに気づいて、
気づい...気づけるのか？

うーん、一番上の円盤は他の円盤に関係なく1手で好きなところへ動かせるから無いものと考えると最小の三角形は一つの点と見なせて再帰のレベルが1つ下がるので無駄ルートだと気づける、としても円盤の数が多くなって再帰のレベルもそれだけ多く下げようとするとルートが無駄かどうかも再帰的に考えなきゃなくなるし判定のために必要な過去の道筋も再帰的に増えるので
ので、
ということで、
つまり、ボツ！