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