ハノイの塔とは (ハノイノトウとは) [単語記事]

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

概要

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

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

ルール

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

最短手数

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

円盤が5枚の場合
初期位置	1手目	2手目	3手目

4手目	5手目	6手目	7手目

8手目	9手目	10手目	11手目

12手目	13手目	14手目	15手目

16手目	17手目	18手目	19手目

20手目	21手目	22手目	23手目

24手目	25手目	26手目	27手目

28手目	29手目	30手目	31手目

伝説

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

前述したとおり、n枚の円盤を移し終えるには最少でも2ⁿ-1の手数が必要であるため、円盤が64枚の場合に必要な手数は途轍もない数となる。仮に一度も間違えることなく1秒に1回のペースで円盤を動かし続けるとすると2⁶⁴-1秒、約5845億年の時間が掛かることになる。移し終える前に人類は滅亡してしまうだろう。