ハノイの塔

ハノイの塔（ハノイのとう、英: Tower of Hanoi）は、パズルの一種。 バラモンの塔または ルーカスタワー（英: Lucas' Tower）^{[注 1]}とも呼ばれる。

8つの円盤のハノイの塔

ルール

以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。

• 3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
• 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
• 円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

${\displaystyle n}$ 枚の円盤すべてを移動させるには最低 ${\displaystyle 2^{n}-1}$ ^{[注 2]}回の手数がかかる^[1]。

解は、次のように再帰的に考えることができる。塔を「一番下にある円盤」と「残りの円盤群」というように分けてみる。そして、まず「残りの円盤群」を移動させ、次に「一番下にある円盤」を移動し、その上にまた「残りの円盤群」を動かせばよい。

解が再帰的な構造をしているということから、この解の手順を表示させるという問題は、再帰的なコンピュータ・プログラムの単純な例題として多用されている。ただし支配数がメルセンヌ数^{[注 3]}なので、同じく再帰の例題として多用されるフィボナッチ数^{[注 4]}のように、${\displaystyle n}$ が大きくなると結果も膨大となる。

解き方

3本の棒にA,B,Cの名前を付ける。最初Aに n 個の円盤があり、Cにすべての円盤を移動させるとすると、次のようにする。n = 1のときは自明であるから、n > 1の場合、

1. 上から n − 1 個目までの円盤を何らかの方法でAからBに移動する。
2. 残った1枚をAからCに移動する。
3. Bにある円盤を何らかの方法でBからCに移動する。

ここで、1は最初Aに n − 1 個の円盤があり、Bにすべての円盤を移動させるという問題ととらえることができる。そこで、次のようにする。

1. 上から n − 2 個目までの円盤を何らかの方法でAからCに移動する。
2. 残った1枚をAからBに移動する。
3. Cにある円盤を何らかの方法でCからBに移動する。

3も同様にして行うことができ、「何らかの方法」の部分を分解していくと解ける^[1]。

実用的な解法

再帰的でない解き方として、以下のような手順がある^[1]。人間が解く場合にも利用可能である。

• いちばん小さい円盤とそれ以外の円盤を交互に動かす。
• いちばん小さい円盤は常にB→C→A→B(nが偶数の場合)またはC→B→A→C(nが奇数の場合)の順に動かす。
• いちばん小さな円盤以外の円盤を動かす場面では、動かせる方法は1通りしかない。

このような単純なアルゴリズムで表記されるにもかかわらず、実際には 2ⁿ − 1 ^{[注 2]}手かかる。

棒が4本以上の場合の最小手数は三角数を用いて計算できることが知られている。

2進数による解析

初期状態から n 回動かした状態は、n の2進数表記から、一意的に求めることができる。

すべて左端の棒にある状態からすべて右端の棒に移動させる場合、各円盤の位置は以下のように求められる。

• n を2進数で書き表す。
• 最上位が一番大きい円盤、以下順に対応し1の位が一番小さい円盤に対応する。
• 最上位が0のとき、一番大きい円盤がまだ動いておらず、1の時には移動済みである。
• 各桁の数字を一つ上の位と比べる。
  1. 同じ値の場合
     • その円盤は一回り大きい円盤の上に乗っている（同じ棒上にある）。
  2. 異なっている場合
     • その数字が0の場合
       • 下から奇数番目の場合、一回り大きい物の右隣にある。
       • 下から偶数番目の場合、一回り大きい物の左隣にある。
     • その数字が1の場合
       • 下から奇数番目の場合、一回り大きい物の左隣にある。
       • 下から偶数番目の場合、一回り大きい物の右隣にある。

ただし、左端の棒の左隣は右端、右端の棒の右隣は左端とする。

2進数の演算を利用すると、n 番目の移動を簡単に表記することができる。C言語の表記を用いると n 番目の移動は、「(n&(n-1))%3 番目の棒にある円盤を ((n|(n-1))+1)%3 番目の棒に移動する」となる。

なお、メルセンヌ数は二進数では全ての桁の位を占める数が1になるから、前述の二進数演算による解析は、全ての棒に与えられた枚数n分の二進メルセンヌ数桁との因果関係を明らかにしている。これは次項のパリティとグレイ・コード解法にも大きく関与しているといえる。

グレイコードによる解法

ハノイの塔の解答とグレイ・コードによる数字の表記は近い位置にある。

グレイコードによって表記された数字の一番下の桁に一番小さい円盤、次の数字に二番目の円盤というようにすべての桁と円盤を対応付けたとき、数字が変化することによって変わるビットに対応する円盤を動かすことで解答が求められる。

この方法では動かす円盤がわかるだけでどの棒に動かすべきかは求められないが、円盤同士のパリティを考えることにより移動先も定まる（偶数番目同士、奇数番目同士の円盤は重ならない）。

前述の通り、全ての桁と円盤を対応付ける事は、その桁に対応したメルセンヌ数に支配される事と等しい。

最小手数について

円盤${\displaystyle n}$枚に対してかか最小手数を${\displaystyle T(n)}$とする。

導出

①${\displaystyle T(1)=1}$は明らか成立(一番下の円盤の上に円盤がないため、円盤を右の杭に移動させれば完成)。
②${\displaystyle n(\geq 2)}$枚における完成までの手順は以下の通りである。
(ⅰ)「一番下の円盤」の上にある「残りの円盤群」を全て補助の杭(前述のルールによれば真ん中の杭にあたる)に移動させる。
(ⅱ)「一番下の円盤」を目的の杭(前述のルールによれば一番右の杭にあたる)に移動させる。
(ⅲ)(ⅰ)で移動させた円盤を全て目的の杭に移動させる。

②を精査する。
(ⅰ)にかかる手数は${\displaystyle T(n-1)}$
(ⅱ)にかかる手数は1((ⅰ)で上にある円盤群は移動済みであるから、目的の杭に移動させるだけである。)
(ⅲ)にかかる手数は(ⅰ)と同じ操作を繰り返していることから、${\displaystyle T(n-1)}$
よって、${\displaystyle T(n)=T(n-1)+1+T(n-1)=2T(n-1)+1}$が成り立つ。
${\displaystyle T(n)+1=2(T(n-1)+1)}$となり、 ①から、初項1,公比2である等比数列であることがわかる。 よって、 ${\displaystyle T(n)=2^{n}-1}$ が導かれる。

証明

数学的帰納法により証明する。 ${\displaystyle n=1}$のとき、${\displaystyle 2^{1}-1=1}$であり、${\displaystyle T(1)=1}$より、成立。 ${\displaystyle n=k(k\in \mathbb {N} )}$のとき成り立つことを仮定して${\displaystyle n=k+1}$のとき成り立つことを示す。 前項の性質を用いると、 ${\displaystyle T(k+1)=2T(k)+1=2(2^{k}-1)+1=2^{k+1}-1}$したがって、任意の${\displaystyle n}$に対して${\displaystyle T(n)=2^{n}-1}$

杭の本数を変えたハノイの塔

杭の本数を${\displaystyle m}$,円盤の枚数を${\displaystyle n}$とする。
杭が3本の場合(${\displaystyle n\geq 3}$)、「一番下の円盤」を一番右の杭に移すには、「残りの円盤群」を真ん中の杭にすべて整列させなくてはならないが、杭が4本以上であれば、「残りの円盤群」を分散できるため、より効率的に完成させられる。 ${\displaystyle m}$と${\displaystyle n}$の大小関係によっても挙動は変化する。 例えば、${\displaystyle m=4}$,${\displaystyle n=3}$とすると、最小手数は以下の通りである。
${\displaystyle \left|{\begin{matrix}1&{\phantom {1}}&{\phantom {1}}&{\phantom {1}}\\2&{\phantom {1}}&{\phantom {1}}&{\phantom {1}}\\3&{\phantom {1}}&{\phantom {1}}&{\phantom {1}}\end{matrix}}\right|\longrightarrow \left|{\begin{matrix}{\phantom {1}}&{\phantom {1}}&{\phantom {1}}&{\phantom {1}}\\2&{\phantom {1}}&{\phantom {1}}&{\phantom {1}}\\3&1&{\phantom {1}}&{\phantom {1}}\end{matrix}}\right|\longrightarrow }$ ${\displaystyle \left|{\begin{matrix}{\phantom {1}}&{\phantom {1}}&{\phantom {1}}&{\phantom {1}}\\{\phantom {1}}&{\phantom {1}}&{\phantom {1}}&{\phantom {1}}\\3&1&2&{\phantom {1}}\end{matrix}}\right|\longrightarrow \left|{\begin{matrix}{\phantom {1}}&{\phantom {1}}&{\phantom {1}}&{\phantom {1}}\\{\phantom {1}}&{\phantom {1}}&{\phantom {1}}&{\phantom {1}}\\{\phantom {1}}&1&2&3\end{matrix}}\right|\longrightarrow }$

${\displaystyle \left|{\begin{matrix}{\phantom {1}}&{\phantom {1}}&{\phantom {1}}&{\phantom {1}}\\{\phantom {1}}&{\phantom {1}}&{\phantom {1}}&2\\{\phantom {1}}&1&{\phantom {1}}&3\end{matrix}}\right|\longrightarrow \left|{\begin{matrix}{\phantom {1}}&{\phantom {1}}&{\phantom {1}}&1\\{\phantom {1}}&{\phantom {1}}&{\phantom {1}}&2\\{\phantom {1}}&{\phantom {1}}&{\phantom {1}}&3\end{matrix}}\right|}$
(円盤の数字は円盤の小さい順で割り当てている。一番上の円盤は1となる。また、列によって杭の位置を示す)
このように、${\displaystyle m>n}$のとき、残りの円盤群を補助の杭に移動させる最良の手段はできるだけ分散させることであるから、 ${\displaystyle n-1}$枚の残りの円盤群を一枚ずつ補助の杭に移動させていくことで最小手数で完成させられる。
つまり、${\displaystyle m>n}$の場合、「残りの円盤群」を補助の杭に移動させる最小手数は、${\displaystyle n-1}$手となる。
「一番下の円盤」を目的の杭に移動させるのに、1手。
「残りの円盤群」を目的の杭に移動させるのは最初と同じく${\displaystyle n-1}$手。
よって、${\displaystyle m>n}$のとき、
${\displaystyle T(n)=2n-1}$

${\displaystyle m<n}$の場合を考える。 前述したとおり、「残りの円盤群」はできるだけ分散して補助の杭に移したい。しかし、${\displaystyle m<n}$であるから、少なくとも一つの杭には2つ以上の円盤が入ることになる。すなわち、${\displaystyle m,n}$に対して、最小手数を
${\displaystyle T_{m}(n)}$などとおいて、${\displaystyle T_{m}(n-1)}$で繰り返し表していくことはあまり有効ではない。杭が3本の場合においては、「残りの円盤群」を補助の杭に整列させてから、目的の杭に整列させるため、その手数は一致するが、杭が4本以上かつ、円盤の枚数の方が多い場合においては、「残りの円盤群」は補助の杭に整列されないため、手数は一致しない。よって、杭が3本のときと同じ性質は持たない。同様な再帰的(対称的)な操作を行わないため、解は複雑さを増している。

由来

ハノイの塔は、フランスの数学者エドゥアール・リュカが1883年に発売したゲーム『ハノイの塔』がルーツである。パッケージには「Li-sou-stian大学勤務のシャム出身のN. Claus教授によりトンキンからもたらされたゲーム」と書かれているが、Li-Sou-Stian大学はリュカが働いていたリセ・サン＝ルイ (Saint-Louis) 校のアナグラム、シャム出身のN. Claus (N. Claus de Siam) はアミアン出身のリュカ (Lucas d'Amiens) のアナグラムであるため、すべてはリュカの創作だと思われている。

同梱のリーフレットには、次のような伝説があると書かれていた。

インドのガンジス河の畔のヴァラナシ（ベナレス）に、世界の中心を表すという巨大な寺院がある。そこには青銅の板の上に、長さ1キュビット、太さが蜂の体ほどの3本のダイヤモンドの針が立てられている。そのうちの1本には、天地創造のときに神が64枚の純金の円盤を大きい円盤から順に重ねて置いた。これが「ブラフマーの塔」である。司祭たちはそこで、昼夜を通して円盤を別の柱に移し替えている（移し変えのルールの説明は省略）。そして、全ての円盤の移し替えが終わったときに、世界は崩壊し終焉を迎える。

パッケージではハノイの塔となっていたが、リーフレットではブラフマーの塔となっていた。ハノイはトンキンの中心都市、ブラフマーはヒンドゥー教や仏教における創造神である。

この話には多くのヴァリエーションが生まれた。たとえば、ダイヤモンドの針のかわりに大理石の柱が立っているなどである。

64枚の円盤を移動させるには、最低でも

（2⁶⁴ − 1）回 = 18,446,744,073,709,551,615 回 = 1844京6744兆737億955万1615回

かかり、1枚移動させるのに1秒しかかからなかったにしても最低でも約5845億年かかる（なお、ビッグバンは今から約137億年前に発生したとされている）。

日本におけるハノイの塔

日本では1907年（明治40年）に書かれた書物『世界遊戯法大全』で紹介されている。その中では何回移動させればいいかなど数学的考察もしっかり書かれている。