ハノイの塔
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ハノイの塔（とう）はパズルのひとつ。
目次 |
[編集] ルール
- 3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
- 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
- 円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。
上のルールに従ってすべての円盤を右端の杭に移動させられれば完成。
すべての円盤を移動させるには2n − 1回の手数がかかる。
解法に再帰的アルゴリズムが使用可能な問題として有名であり、再帰的呼出しを記述可能なプログラミング言語の記述例としてもよく用いられる。
[編集] 解き方
3本の棒にA,B,Cの名前を付ける。最初Aにn個の円盤があり、Cにすべての円盤を移動させるとすると、次のようにする。
- 上からn-1個目までの円盤を何らかの方法でAからBに移動する。
- 残った1枚をAからCに移動する。
- Bにある円盤を何らかの方法でBからCに移動する。
ここで、1は最初Aにn-1個の円盤があり、Bにすべての円盤を移動させるという問題ととらえることができる。そこで、次のようにする。
- 上からn-2個目までの円盤を何らかの方法でAからCに移動する。
- 残った1枚をAからBに移動する。
- Cにある円盤を何らかの方法でCからBに移動する。
3も同様にして行うことができ、「何らかの方法」の部分を分解していくと解ける。
[編集] 実用的な解法
コンピュータに解答させる場合には再帰的方法が有効であるが、人間が手で解く場合には以下のような手順がある。
- 一番小さい円盤とそれ以外の円盤を交互に動かす。
- 一番小さい円盤は常に時計回りに動かす。
このような単純なアルゴリズムで表記されるにもかかわらず、実際には2n-1手かかる。
棒が4本以上の場合は、一般的な最小手数やアルゴリズムは知られていない。
[編集] 2進数による解析
初期状態からn回動かした状態は、nの2進数表記から、一意的に求めることができる。
すべて左端の棒にある状態からすべて右端の棒に移動させる場合、各円盤の位置は以下の様に求められる。
- nを2進数で書き表す。
- 最上位が一番大きい円盤、以下順に対応し1の位が一番小さい円盤に対応する。
- 最上位が0のとき、一番大きい円盤がまだ動いておらず、1の時には移動済みである。
- 各桁の数字を一つ上の位と比べる。
- 同じ値の場合
- その円盤は一回り大きい円盤の上に乗っている（同じ棒上にある）。
- 異なっている場合
- その数字が0の場合
- 下から奇数番目の場合、一回り大きい物の右隣にある。
- 下から偶数番目の場合、一回り大きい物の左隣にある。
- その数字が1の場合
- 下から奇数番目の場合、一回り大きい物の左隣にある。
- 下から偶数番目の場合、一回り大きい物の右隣にある。
- その数字が0の場合
- 同じ値の場合
ただし、左端の棒の左隣は右端、右端の棒の右隣は左端とする。
2進数の演算を利用すると、n番目の移動を簡単に表記することができる。C言語の表記を用いるとn番目の移動は、「(n&(n-1))%3番目の棒にある円盤を((n|(n-1))-1)%3番目の棒に移動する」となる。
[編集] グレイコードによる解法
ハノイの塔の解答とグレイ・コードによる数字の表記は近い位置にある。
グレイコードによって表記された数字の一番下の桁に一番小さい円盤、次の数字に二番目の円盤というようにすべての桁と円盤を対応付けたとき、数字が変化することによって変わるビットに対応する円盤を動かすことで解答が求められる。
この方法では動かす円盤が分かるだけでどの棒に動かすべきかは求められないが、円盤同士のパリティを考えることにより移動先も定まる。（偶数番目同士、奇数番目同士の円盤は重ならない）
[編集] 由来
ハノイの塔は、フランスの数学者E・リュカ(Edouard Lucas)が1883年に考えたものである。リュカは、インドに次のような伝説があると説明している。
[編集] ブラフマーの塔
- インドのガンジス河の畔のベナレス（ヴァラナシ）に世界の中心を表すという聖堂がある。そこには3本の大理石の柱（ダイヤモンドの針との説もあり）が立てられており、そのうちの1本には、当初64枚の黄金の円盤が大きい円盤から順に重ねられていたという。バラモン僧たちはそこで、一日中円盤を別の柱に移し替える作業を行っている。そして、全ての円盤の移し替えが終わったときに、この世は崩壊し終焉を迎えると言われている。
もちろんこれはリュカの作り話であるが、64枚の円盤を移動させるには、最低でも18,446,744,073,709,551,615回かかり、1枚移動させるのに1秒かかったとして、約5,845億年かかる（なお、ビッグバンは今から約137億年前の発生とされている）。
