前置き
世の中に数多あるパズルの中に、
ハノイの塔
というものがあります。
toy1972.hatenablog.com
形状は、
- 3本の杭が(一列に)立っていて、
- 杭に大きさの異なる円盤が刺さっている
というものです。
遊び方は、
- 一方の端の杭に全ての円盤が大きさ順に刺さっていて、
- もう一方の端の杭に全ての円盤を移せれば完成
となります。
円盤を移すにあたって制約があります。
- 一番上の円盤のみ、他の2本の杭に移すことができます。
- ただし、小さい円盤の上に大きい円盤を乗せることはできません。
1手で1つの円盤を動かすものとして、何手かかるのか、見ていきましょう。
説明の都合上、杭にラベルを付けます。
- A┅初期状態で円盤が刺さっている杭
- B┅真ん中の杭
- C┅移す先の杭
円盤にもラベルを付けます。
- 上から順に1, 2,…
とします。
こんな感じです。
どの円盤をどこに移すかを、
- 「移した先の杭のラベル」
- 「動かした円盤の番号」
を並べて表すことにします。
例えば、1番の円盤をCの杭に移す場合、
- C1
と書くことにします。
将棋の棋譜の書き方を真似ました。
さて、ここでは、円盤の動かし方に制約を付けてみましょう。
1番上の円盤を真ん中の杭Bに移動させない
この制約でどうなるか、みていきましょう。
- B1が禁じ手
ということになります。
1段の場合
1段の場合は簡単です。
- C1
これだけです。1手です。
2段の場合
2段の場合を見ていきます。
- C1
- B2
- A1
- C2
- C1
以上です。5手です。
制約があるので、手数が多くなっています。
3段の場合
- C1
- B2
- A1
- C2
- C1
- B3
- A1
- B2
- C1
- A2
- A1
- C3
- C1
- B2
- A1
- C2
- C1
で完成です。17手かかります。
最大の円盤が、ずい、ずいと前に出て行く