ふつうのハノイの塔は、棒が3本です。では、棒を1本増やして4本にしたら、どうなるでしょうか。ルールは同じで、1回に1枚ずつ、小さい円盤の上に大きい円盤を置かずに、塔を別の棒へ移します。

1本増えるだけで、手数は大きく減る

使える置き場所が1つ増えるので、円盤をどかすのがずっと楽になります。最少手数を比べると、その差は枚数が増えるほど大きくなります。

円盤の枚数棒が3本棒が4本
3枚7手5手
4枚15手9手
5枚31手13手
6枚63手17手
7枚127手25手
8枚255手33手
10枚1,023手49手
64枚約1845京手18,433手

3本の棒では、64枚を移すのに1秒に1手でも約5845億年かかります(円盤64枚だと何年かかる?)。ところが4本なら18,433手、1秒に1手で約5時間です。伝説の僧たちが棒を1本増やしていたら、世界はその日のうちに終わっていたことになります。

デュードニーの「チーズのパズル」

4本の棒のハノイの塔を広く紹介したのは、イギリスのパズル作家ヘンリー・デュードニーです。1907年の本『カンタベリー・パズル』の中で、「レーヴのパズル」として出題しました。レーヴ(リーヴ)は、荘園の管理人のことです。

デュードニーの問題では、円盤の代わりに大きさの違う8つのチーズを、4つの腰かけのあいだで移します。小さいチーズの上に大きいチーズを載せてはいけません。答えは33手で、上の表の8枚と同じです。

フレーム・スチュワートの解き方

4本の棒で少ない手数で移す方法は、1941年にJ・S・フレームとB・M・スチュワートが、それぞれ同じ考え方を発表しました。n枚の塔を移すとき、

  1. 上のk枚を、4本の棒を全部使って、移したい棒以外の棒へ移す。
  2. 残りのn−k枚を、上のk枚がいる棒を使わずに、3本の棒だけで移したい棒へ移す(2ⁿ⁻ᵏ−1手)。
  3. 1でどかしたk枚を、4本の棒を全部使って、移したい棒へ移す。

という3つに分けます。1と3は同じ問題の小さい版なので、再帰の考え方が使えます(アルゴリズムの記事)。あとは、上に何枚(k枚)残すといちばん少なくなるかを選ぶだけです。8枚なら、上の4枚か5枚を先にどかすのがいちばん少なく、33手になります。

100年近く証明されなかった「いちばん少ない」

フレーム・スチュワートの方法で少ない手数で移せることは分かりました。ところが、これより少ない方法が本当にないのかは、長いあいだ誰にも証明できませんでした。

3本の棒なら、「いちばん大きい円盤を動かす瞬間、ほかの円盤は全部1本に集まっていなければならない」という1つの事実から、最少手数がすぐに証明できます(最少手数の公式)。4本になると、大きい円盤を動かす瞬間に、ほかの円盤が残りの2本へどう分かれていてもよいので、考えられる手順が一気に増えてしまうのです。

コンピューターで全部の置き方を調べて、30枚ほどまではこの方法が最少だと確かめられていました。そしてデュードニーの出題からおよそ100年後の2014年、フランスの数学者ティエリー・ブーシュが、何枚であってもフレーム・スチュワートの方法が最少であることを証明しました。棒が5本以上の場合は、今も証明されていないとされています。

自分でも試せる

4本の棒のハノイの塔は、作り方の記事の厚紙の作り方で、置き場所の丸を4つにすれば作れます。3枚を5手、4枚を9手で移せるか、試してみてください。3本のときとの違いを体で感じられます。