ハノイの塔

ハノイの塔とは、パズルゲームの一種である。

概要

3本の棒と、中央に穴があいた何枚かの異なる大きさの円盤がある。
ゲームスタート時は一番左の棒に大きい順に円盤が積み重ねられており、所定のルールに従って全ての円盤を一番右の棒に移動させることができれば完成となる。

単純で理解しやすいゲームであり、小学校や中学校で算数・数学の教材に使われることもある。

ルール

• 一手につき1枚しか円盤を動かすことはできない。
• ある円盤の上に、それより大きい円盤を積むことはできない。
• 棒以外のところに円盤を移動させることはできない。

最低必要な手数

上記のルールに従ってn枚の円盤を一番左の棒から一番右の棒へと動かす場合、最低でも2^n-1の手数が必要となることが知られている。たとえば、3枚の場合なら2^3-1=7となり7手必要である。

伝説

「一番左の棒に64枚の円盤を積み、それら全てを一番右の棒に移し終わったとき世界は滅亡する」という旨の伝説があるが、これは考案者の創作であると考えられている。

前述したとおり、n枚の円盤を移し終えるには最低でも2^n-1の手数が必要であるため、円盤が64枚の場合必要な手数は途方もない数となる。仮に一度も間違えることなく1秒に1回のペースで円盤を動かし続けても約5845億年の時間がかかるという。
おそらくその10分の1もいかない内に地球は滅亡しているだろう。地球以外がどうなっているかは知らない。

関連商品

関連項目

• パズル