ハノイの塔のソースを表示

{{出典の明記|date=2017年7月22日 (土) 02:34 (UTC)}}
[[画像:Tower of Hanoi.jpeg|thumb|250px|8つの円盤のハノイの塔]]
'''ハノイの塔'''（ハノイのとう、{{Lang-en-short|Tower of Hanoi}}）は、[[パズル]]の一種。 '''バラモンの塔'''または '''ルーカスタワー'''（{{Lang-en-short|Lucas' Tower}}）{{efn2|考案者の[[エドゥアール・リュカ|リュカ]]の英語音名}}とも呼ばれる。

== ルール ==
[[画像:Tower of Hanoi 4.gif|right]]
以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。
*3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
*最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
*円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

<math>n</math> 枚の円盤すべてを移動させるには最低 <math>2^n -1</math> {{efn2|name="Mersenne_num"|この公式は、[[メルセンヌ数]]の定義式そのものでもあり、つまり、与えられた円盤 <math>n</math> 枚数時における最小手数は[[メルセンヌ数]] {{mvar|M{{sub|n}}}} のn項目に等しいという事である。よって本パズルはメルセンヌ数に支配されたものといえる。}}回の手数がかかる<ref name="algo">{{cite book | 和書 | title=C言語による最新アルゴリズム事典 | publisher=[[技術評論社]] | author=奥村晴彦 | authorlink=奥村晴彦 | year=1991 | pages=216&ndash;217頁 | isbn=4-87408-414-1 }}</ref>。

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

解が再帰的な構造をしているということから、この解の手順を表示させるという問題は、再帰的な[[プログラム (コンピュータ)|コンピュータ・プログラム]]の単純な例題として多用されている。ただし支配数が[[メルセンヌ数]]{{efn2|メルセンヌとリュカとは[[素数]]研究者という共通点がある。}}なので、同じく再帰の例題として多用される[[フィボナッチ数]]{{efn2|リュカはフィボナッチ数の研究者の一人であり、その同伴数列（[[リュカ数]]）の一般項公式を与えた人物でもある。さらに、フィボナッチ数、メルセンヌ数、リュカ数、これらの数列は全て二階[[線形回帰数列]]という分野に属する（元から再帰的性質を持った）数列である。}}のように、<math>n</math> が大きくなると結果も膨大となる。

== 解き方 ==
3本の棒にA,B,Cの名前を付ける。最初Aに ''n'' 個の円盤があり、Cにすべての円盤を移動させるとすると、次のようにする。''n'' = 1のときは自明であるから、''n'' &gt; 1の場合、
#上から ''n'' &minus; 1 個目までの円盤を'''何らかの方法で'''AからBに移動する。
#残った1枚をAからCに移動する。
#Bにある円盤を'''何らかの方法で'''BからCに移動する。
ここで、1は最初Aに ''n'' &minus; 1 個の円盤があり、Bにすべての円盤を移動させるという問題ととらえることができる。そこで、次のようにする。
#上から ''n'' &minus; 2 個目までの円盤を'''何らかの方法で'''AからCに移動する。
#残った1枚をAからBに移動する。
#Cにある円盤を'''何らかの方法で'''CからBに移動する。
3も同様にして行うことができ、「何らかの方法」の部分を分解していくと解ける<ref name="algo" />。

=== 実用的な解法 ===
再帰的でない解き方として、以下のような手順がある<ref name="algo" />。人間が解く場合にも利用可能である。
*いちばん小さい円盤とそれ以外の円盤を交互に動かす。
*いちばん小さい円盤は常にB→C→A→B(''n''が偶数の場合)またはC→B→A→C(''n''が奇数の場合)の順に動かす。
*いちばん小さな円盤以外の円盤を動かす場面では、動かせる方法は1通りしかない。
このような単純なアルゴリズムで表記されるにもかかわらず、実際には 2<sup>''n''</sup> &minus; 1 {{efn2|name="Mersenne_num"}}手かかる。

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

=== 2進数による解析 ===
初期状態から ''n'' 回動かした状態は、''n'' の[[二進記数法|2進数表記]]から、一意的に求めることができる。

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

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

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

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

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

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

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

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

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

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

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

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

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

64枚の円盤を移動させるには、最低でも
:（2<sup>64</sup> &minus; 1）回 = 18,446,744,073,709,551,615 回 = 1844京6744兆737億955万1615回
かかり、1枚移動させるのに1秒しかかからなかったにしても最低でも約5845億年かかる（なお、[[ビッグバン]]は今から約137億年前に発生したとされている）。
<!--閏年を考えるだけで数億年の誤差が出るので、それより下の計算には意味がない-->

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

== 脚注 ==
{{脚注ヘルプ}}
'''注釈'''
{{Notelist2}}
'''出典'''
{{Reflist}}

== 外部リンク ==
*{{MathWorld|title=Tower of Hanoi|urlname=TowerofHanoi}}
*[http://puzzlemuseum.com/month/picm07/2007-03_hanoi.htm ハノイの塔 オリジナルパッケージの写真]

{{DEFAULTSORT:はのいのとう}}
[[Category:パズル]]
[[Category:エドゥアール・リュカ]]
[[Category:塔を題材とした作品]]