ハノイの塔を最短で解くには？手数の公式と迷わない手順をやさしく解説

こんにちは。FreeLife Design、運営者の「ケイ」です。

ハノイの塔を最短で解きたいのに、途中で円盤の置き場所がわからなくなって手が止まる。そんな経験、パズル好きならけっこう多いかなと思います。

この記事では、ハノイの塔の最短手数を求める公式（2のn乗−1）と、その数になる理由を、なるべく式に頼らずに説明していきます。3枚なら7手、5枚なら31手、7枚なら127手。枚数ごとの最短手数を一覧にして、手数の計算方法もあわせて確認しますね。

後半では、ハノイの塔を最短で解くやり方と覚え方を、3枚の手順を1手ずつ追いながら整理します。一番小さい円盤をどちらへ動かせばいいのか、奇数枚と偶数枚で変わる最初の1手の決め方、7枚で途中に迷わないための目印、最短から外れたときの戻り方まで扱います。

あわせて、64枚の伝説で語られる世界滅亡の話を実際に計算したらどうなるか、棒の数を4本に増やすと最短手数がどう変わるか、といった少し寄り道の話題にも触れます。ふつうのルールのハノイの塔なら、決まりさえつかめばゲームアプリでも木のおもちゃでも同じように解けますよ。

• ハノイの塔の最短手数が2のn乗−1になる理由
• 3枚・5枚・7枚など枚数別の最短手数と所要時間の目安
• 一番小さい円盤の向きで決まる最短手順のやり方
• 途中で迷ったときの立て直し方と覚え方のコツ

ハノイの塔の最短手数は2のn乗−1で決まる

先に結論から言うと、ハノイの塔の最短手数は「2のn乗−1」で決まります。棒が3本で、全部の円盤を1本から別の1本へ移すふつうのルールの場合で、nは円盤の枚数です。3枚なら2×2×2−1で7手、4枚なら15手、5枚なら31手。円盤が1枚増えるごとに、最短手数はほぼ倍になっていきます。

この章では、まずルールのおさらいと公式の意味を確かめ、次に枚数別の最短手数を一覧表で見ていきます。そのうえで、なぜこれより少ない手数では解けないのかを、一番大きい円盤に注目して説明します。式が苦手な人でも、図をイメージしながら読めば納得できる内容にしています。

後半の2つの見出しは、少し視野を広げた話です。64枚の円盤を動かすと世界が滅びるという伝説の計算と、棒が4本あるときの最短手数。どちらもハノイの塔の「手数が爆発的に増える」性質をよく表していて、公式の意味がぐっと実感しやすくなるはずです。

最短手数の公式と3枚が7手になる理由

ハノイの塔の最短手数の公式は、円盤の枚数をnとしたとき「2のn乗−1」です。3枚なら7手、これが最短。どれだけ工夫しても6手以下にはなりません。

ハノイの塔の基本ルール

まずルールを確認しておきますね。ハノイの塔は、3本の棒と、大きさの違う穴あき円盤を使うパズルです。最初はすべての円盤が1本の棒に、下から大きい順に積まれています。これを別の1本へ、同じ順番のまま移し替えればゴールです。

動かし方には決まりが2つあります。1回に動かせるのは一番上の円盤1枚だけ。そして、小さい円盤の上に大きい円盤を置いてはいけません。たったこれだけのルールなのに、枚数が増えると一気に難しくなるのがおもしろいところです。

この記事では、円盤が最初に積まれている棒を「スタート」、移し替える先を「ゴール」、残りの1本を「作業用」と呼ぶことにします。手順を書くときは、スタート＝A、作業用＝B、ゴール＝Cという記号も使います。

3枚が7手になる流れ

3枚の場合を考えてみましょう。一番大きい円盤をゴールへ動かすには、その上に乗っている小さい2枚を、いったん作業用の棒へよけておく必要があります。2枚を移すには3手かかります。

2枚をよけたら、一番大きい円盤をゴールへ1手で動かします。最後に、作業用の棒によけておいた2枚を、ゴールの大きい円盤の上へ3手で戻す。合計すると3＋1＋3で7手です。

この「上の部分をよける→一番大きい円盤を動かす→上の部分を戻す」という3段の流れが、ハノイの塔の最短手順の骨組みになっています。2枚を移す3手も、中をのぞけば「1枚をよける→2枚目を動かす→1枚を戻す」と同じ形。入れ子になった構造なんです。

この入れ子の考え方は、プログラミングで「再帰」を教えるときの定番の例としてもよく使われています。ハノイの塔は数学パズルであると同時に、ものの考え方を学ぶ教材でもあるわけですね。

3枚・5枚・7枚の最短手数を枚数別に一覧で確認

枚数別の最短手数は、3枚が7手、5枚が31手、7枚が127手です。10枚になると1,023手まで増えます。下の表に、1枚から10枚までの最短手数と、1手にかかる時間ごとの所要時間の目安をまとめました。

→ 横にスクロールできます

所要時間は「1手を何秒で動かすか」を決めて掛け算しただけの、あくまで一般的な目安です。実際には考える時間や持ち替えの時間が入るので、慣れないうちはもっとかかると思っておくと気が楽かも。

最短手数の計算方法

計算方法はシンプルで、2をn回掛けてから1を引くだけ。5枚なら2×2×2×2×2＝32、そこから1を引いて31手です。7枚なら2を7回掛けて128、1を引いて127手になります。

もう1つの求め方もあります。「1枚少ないときの最短手数を2倍して1を足す」という方法です。3枚が7手なら、4枚は7×2＋1で15手、5枚は15×2＋1で31手。前の見出しで見た「よける→動かす→戻す」の流れを、そのまま数にしたものですね。

この2つのやり方は、どちらで計算しても同じ答えになります。暗算しやすいほうを使えばOKです。枚数が大きいときは2のn乗、すぐ前の枚数がわかっているときは「2倍して1を足す」が便利ですよ。

表の右端「並び方の総数」の意味

表の右端は、ルールを守ったまま作れる円盤の並び方が何通りあるかを示しています。円盤は1枚ずつ3本のどれかに置けて、同じ棒の中では大きい順に積むしかないので、並び方は3のn乗通り。3枚なら27通りです。

最短手数の7手で通るのは、そのうち8つの並び方（最初の形を含む）だけ。残りの多くは、遠回りをしたときにしか出てきません。最短手順がほとんど寄り道のない一本の道になっていることが、こうした数字からもイメージできるかなと思います。

海外の解説では、おもちゃのハノイの塔は7枚から9枚くらいの円盤がついたものが多いとされています。7枚なら最短127手、8枚なら255手。数字だけ見ると身構えてしまいますが、次の章のやり方を覚えれば、手順そのものは同じ動きのくり返しです。

最短であることの証明を一番大きい円盤から考える

2のn乗−1が最短だと言える理由は、一番大きい円盤に注目するとわかります。一番大きい円盤を動かすときには、その上の円盤がすべて別の1本にまとまっていなければならない。この一点から、これ以上は減らせない手数が決まってきます。

一番大きい円盤を動かす瞬間を考える

n枚のハノイの塔で、一番大きい円盤をゴールへ動かす場面を思い浮かべてください。このとき、大きい円盤の上には何も乗っていてはいけません。そしてゴールの棒も空でなければいけません。どの円盤も、一番大きい円盤より小さいからです。

となると、残りのn−1枚は全部、作業用の棒に正しい順で積まれているしかありません。つまり、一番大きい円盤を動かす前に、n−1枚のハノイの塔を1回解き終えている必要があるわけです。

そして一番大きい円盤をゴールへ動かしたあとも、作業用の棒にあるn−1枚を、ゴールの上へもう一度移さなければなりません。n−1枚のハノイの塔をもう1回解くことになります。

数学的帰納法でつなげる

ここまでをまとめると、n枚を解くには「n−1枚を2回」と「一番大きい円盤を1回」の手数が必ずかかる、ということになります。n−1枚の最短手数を2倍して1を足した数より少なくはできません。

1枚なら1手で、これは2の1乗−1と一致します。2枚は1×2＋1＝3手、3枚は3×2＋1＝7手。どの枚数でも、1枚少ない最短手数を2倍して1を足す関係が成り立つので、順番に積み上げていくと、すべての枚数で2のn乗−1になる。こうした証明の進め方を数学的帰納法と呼びます。

英国ケンブリッジ大学の数学普及サイトでも、上に乗っているn−1枚の塔を少なくとも2回、一番大きい円盤を少なくとも1回動かす必要があることから、この手数が最短だと説明しています。（出典：University of Cambridge・Millennium Mathematics Project『plus.maths.org』The optimal solution）

この性質は、あとで紹介する最短から外れたときの戻り方にも関係してきます。どこで迷っても、そこから最短で戻せば、合計の手数はそれほど大きく膨らまないんです。

64枚の伝説と世界滅亡の話を計算で確かめる

ハノイの塔には、64枚の円盤をすべて移し終えたとき世界が終わる、という伝説がついています。計算すると、64枚の最短手数は約1,845京手。1秒に1手で休まず動かしても、約5,845億年かかります。

伝説はパズルと一緒に生まれた物語

ハノイの塔は、フランスの数学者エドゥアール・リュカが1883年に発表したパズルです。発表のときは「N Claus de Siam」（シャムのN.クラウス）という名前が使われていて、これは「Lucas d’Amiens」（アミアンのリュカ）のつづりを並べ替えたものだったと伝えられています。

伝説は、このゲームに添えられていた物語です。インドのベナレスにある寺院で、司祭（バラモン）たちがダイヤモンドの針の間で64枚の金の円盤を動かしている。円盤は小さいものの上に大きいものを置けない決まりで、全部を移し終えたときに寺院は崩れ、世界も終わる、と語られていました。（出典：University of St Andrews『MacTutor History of Mathematics』The Towers of Hanoi）

なお、伝説の舞台が寺院ではなく修道院になっていたり、場所がハノイになっていたりと、伝わる話にはいくつもの変化形があります。パズルの名前に合わせて語り直されてきた物語、くらいに受け止めておくとよさそうです。

64枚の最短手数を計算すると

64枚の最短手数は、2の64乗−1。数字で書くと18,446,744,073,709,551,615手です。日本の数の単位で読むと、約1,845京手。ちょっと想像がつかない大きさですよね。

1秒に1手のペースで、一度も間違えず、休まず動かし続けたとします。1年を365.25日として割り算すると、約5,845億年。上で出典に挙げたページではこの年数が590兆年（英語で「590 trillion years」）と書かれていますが、2の64乗−1秒をそのまま年に直すと約5,845億年（約0.58兆年）です。原典の数字は桁が大きすぎるようです。伝説の語り方によっては1日に1手しか動かさないとする版もあり、その場合はさらに約8万6,400倍の時間がかかる計算です。

世界滅亡の話は、あくまでパズルを盛り上げるための物語です。ただ、この計算をしてみると、「1枚増えるごとに手数がほぼ倍になる」ことの迫力がよくわかります。7枚の127手と64枚の約1,845京手は、同じ公式から出てくる数なんです。

棒の数が3本と4本で最短手数はどう変わる

ふつうのハノイの塔は棒が3本です。棒を4本に増やすと最短手数は大きく減り、たとえば7枚なら3本で127手のところ、4本では25手で解けます。ただし4本の場合は、円盤をどう分けて動かすかという工夫が加わります。

4本の棒のハノイの塔

4本の棒で遊ぶハノイの塔は、海外では「Reve’s puzzle」（リーブのパズル）という名前でも知られています。3本のときのような単純な公式はなく、上の何枚かを別の棒へよけて、残りを3本の棒で動かす、という分け方を工夫して手数を減らします。

この分け方で手数を求める方法は、1941年ごろからフレーム＝スチュワートの方法として知られていました。ただ、それが本当に最短なのかは長く証明されず、4本の場合について証明されたのは2014年で、ベルギー数学会の論文誌に発表されたティエリ・ブーシュの論文とされています。単純そうに見えて、数学者を何十年も悩ませた問題なんですね。

→ 横にスクロールできます

表の4本の列は、フレーム＝スチュワートの方法の式に当てはめて計算した値です。棒が1本増えるだけで、10枚の手数が1,023手から49手まで減るのは驚きですよね。

ゲームやおもちゃでは棒の数を先に確かめる

ハノイの塔の棒は3本が標準です。ただ、問題集やアプリによっては棒の数や円盤の初期配置を変えたものもあるので、遊ぶ前に一度確かめておくと安心です。

この記事の公式とやり方は、棒が3本で、全部の円盤が1本に積まれた状態から始めるふつうのハノイの塔の話です。手元のパズルが違う形式なら、最短手数も違ってくる点だけ覚えておいてください。

ハノイの塔を最短で解くやり方と覚え方

ハノイの塔を最短で解くやり方は、2つの決まりと最初の1手の向きを覚えるだけです。奇数番目の手では一番小さい円盤を決まった向きへ1つ進め、偶数番目の手では一番小さい円盤以外で動かせる唯一の1枚を動かす。これを交互にくり返せば、何枚でも最短手数で解き終わります。最初の1手で一番小さい円盤をどちらへ置くかは、枚数が奇数か偶数かで決まります。

この章では、まずこの2つの決まりの中身を確かめ、3枚の手順を1手ずつ追っていきます。続いて、枚数が奇数か偶数かで変わる「最初の1手」の決め方、7枚のように手数が多いときに途中で迷わないための目印を紹介します。

最後に、うっかり最短から外れてしまったときの戻り方と、遊ぶときの注意点もまとめました。覚え方のコツをつかめば、紙に手順を書き出さなくても頭の中だけで進められるようになりますよ。

最短のやり方は小さい円盤を同じ向きへ回すこと

最短のやり方の中心は、一番小さい円盤をいつも同じ向きへ回し続けることです。3本の棒を輪のようにつながったものと考え、小さい円盤は1手おきに、決めた向きへ1本ずつ進めます。

奇数番目の手は一番小さい円盤

最短手順を1手目から数えていくと、1手目・3手目・5手目……と、奇数番目の手ではいつも一番小さい円盤が動いています。全体の手数に1を足して半分にした数が、一番小さい円盤の担当です。3枚なら7手のうち4手、5枚なら31手のうち16手になります。

理由は単純です。一番小さい円盤を2回続けて動かすのは、1回にまとめられる遠回り。逆に、小さい円盤以外を2回続けて動かそうとすると、2回目に残っているのは1回目を元に戻す動きだけです。だから最短手順では、一番小さい円盤とそれ以外が1手ずつ交互に動くことになります。

さらに、一番小さい円盤が進む向きは最後まで変わりません。スタート→ゴール→作業用→スタート……と回るか、スタート→作業用→ゴール→スタート……と回るか、どちらか一方をずっとくり返します。どちらの向きになるかは、円盤の枚数が奇数か偶数かで決まります（くわしくは少しあとの見出しで）。

偶数番目の手は動かせる1枚が決まっている

偶数番目の手では、一番小さい円盤以外を動かします。このとき迷う必要はありません。一番小さい円盤が乗っていない2本の棒を見比べると、ルールを守って動かせる組み合わせは必ず1つしかないからです。

たとえば、2本の棒の一番上がそれぞれ「2番目に小さい円盤」と「3番目に小さい円盤」なら、2番目を3番目の上へ動かすしかありません。片方の棒が空なら、もう片方の一番上の円盤を空の棒へ動かします。どちらを選んでも同じ、という場面は出てこないんです。

つまり、本当に考える必要があるのは奇数番目の手の「小さい円盤をどっちへ回すか」だけ。偶数番目の手は、盤面を見れば自動的に決まります。これがハノイの塔の最短手順を覚えやすくしている仕組みですね。

声に出して「小さいの、次は小さいの以外」と交互に唱えながら進めると、リズムができて迷いにくくなるかもしれません。

3枚の最短手順を1手ずつ解説

3枚の最短手順は7手です。円盤を小さい順に①②③、棒をスタートA・作業用B・ゴールCとすると、①をA→C、②をA→B、①をC→B、③をA→C、①をB→A、②をB→C、①をA→Cと動かせば完成します。

→ 横にスクロールできます

前半の3手は「上の2枚をよける」

1手目から3手目までは、一番大きい③を動かすための準備です。①と②の2枚を作業用のBへよけています。①をいったんゴールのCに置くのは遠回りに見えますが、こうしておくと②をBへ動かせて、その上に①を重ねられます。

よくある失敗は、1手目で①を作業用のBへ置いてしまうこと。こうすると②はCへしか行けず、上の2枚がゴール側にまとまってしまいます。③をゴールへ動かせなくなり、やり直しの手数がかかってしまいます。

後半の3手は「よけた2枚を戻す」

4手目で③をゴールへ動かしたら、あとはBにある2枚をCへ移すだけ。5手目から7手目は、前半と同じ「2枚を移す3手」を、場所を変えてもう一度やっています。①がB→A→Cと進むのも、ずっと同じ向きのままです。

表を見比べると、①の動きはA→C、C→B、B→A、A→Cと、輪の上を一方向に回り続けているのがわかります。この感覚がつかめたら、枚数が増えても同じ考え方で進められますよ。

手を動かしながら覚えたい人は、円盤の枚数を変えて遊べるおもちゃのハノイの塔があると便利です。対象年齢や円盤の枚数は商品ごとに違うので、購入前に各ショップの商品ページで確かめてくださいね。

4枚・5枚で最初の1手を間違えない判断

最初の1手は、円盤の枚数で決まります。奇数枚（3枚・5枚・7枚）なら一番小さい円盤をまずゴールへ、偶数枚（4枚・6枚・8枚）ならまず作業用の棒へ置きます。ここを逆にすると、最短手順には乗れません。

奇数枚と偶数枚で向きが逆になる

4枚の場合、一番小さい円盤はスタート→作業用→ゴール→スタート……の向きに回ります。3枚とはちょうど逆向きです。4枚の最短手順を書き出すと、1手目は①をA→B、2手目は②をA→C、3手目は①をB→Cとなり、①はA→B→C→Aの順に進んでいきます。

なぜ逆になるのかは、前の章の「よける→動かす→戻す」で考えるとわかります。4枚を解くには、上の3枚をまず作業用へよけなければいけません。3枚を作業用へ移すときは、その作業用が3枚にとっての「ゴール」になる。だから、3枚の解き方でゴールへ向かう1手目が、4枚全体で見ると作業用への1手目になるんです。

→ 横にスクロールできます

ゴールが決まっていないときの考え方

ゲームアプリによっては、「どちらの棒に移してもクリア」というものもあります。その場合は、最初に一番小さい円盤を置いた棒によって、最終的に塔が完成する棒が決まります。奇数枚なら1手目で置いた棒、偶数枚ならスタート以外で1手目に置かなかったほうの棒がゴールになる、と覚えておくと便利です。

スタートを左端の棒として例を挙げますね。5枚なら、1手目で①を右端の棒に置けば、31手目に右端で5枚の塔が完成します。4枚で右端に完成させたいときは、1手目の①を真ん中の棒へ置く。そうすると15手目に右端で塔がそろいます。慣れるまでは、始める前に「今日は何枚？奇数？偶数？」と一度確認する習慣をつけるのがおすすめ。

7枚の最短手順を途中で迷わず進めるコツ

7枚の最短手数は127手。途中で迷わないコツは、大きい円盤が動く手を「目印」として覚えておくことです。64手目に一番大きい円盤がゴールへ動き、その直前の63手目の時点では、上の6枚がすべて作業用の棒にまとまっています。

大きい円盤が動く手が区切りになる

最短手順では、何番目の手でどの円盤が動くかが決まっています。2番目に小さい円盤は2手目・6手目・10手目……と4手ごと、3番目は4手目・12手目……と8手ごと。大きい円盤ほど動く回数が少なく、一番大きい円盤は全体のちょうど真ん中で1回だけ動きます。

7枚なら、1枚の円盤が動く回数は、小さい順に64回・32回・16回・8回・4回・2回・1回。全部足すと127手です。大きい円盤が動く手は数が少ないぶん、進み具合を確かめる区切りとして使いやすいんですね。

→ 横にスクロールできます

手数を数えなくても進める覚え方

とはいえ、127手を1つずつ数えながら進めるのは大変です。手数を数えなくても進めるには、前の見出しの「奇数番目は一番小さい円盤、偶数番目は動かせる唯一の1枚」を守ることに集中するのがいちばん。数えるのは、区切りの盤面を確かめたいときだけで十分です。

もう1つの覚え方は、「小さい円盤を動かしたら、次は小さい円盤に触らない」と決めてしまうこと。小さい円盤を2回続けて動かすと、それだけで最短から外れます。手が迷ったら、直前に小さい円盤を動かしたかどうかを思い出すと、次の1手が決まりますよ。

7枚より多い枚数に挑戦したいなら、9段の木製タイプもあります。9枚の最短手数は511手なので、区切りの目印を使う練習にはちょうどいいかも。価格や在庫は変わるので、購入前に各ショップで確認してください。

最短から外れたときの戻り方と攻略の注意点

最短から外れたと気づいたら、いちばん大きい「まだゴールに来ていない円盤」に注目して立て直すのが近道です。その円盤をゴールへ動かせる形を目指して、上に乗っている円盤を先によけていきます。

外れたときの立て直し方

前の章で見たとおり、どんな並び方からでも、目標の形にするのに必要な手数は2のn乗−1以下です。途中で迷っても、一から積み直す必要はありません。今の盤面から考え直せば大丈夫です。

立て直しの手順は、こんなイメージです。まず、ゴールの棒にまだ来ていない円盤のうち、一番大きいものを探します。次に、その円盤より小さい円盤を全部、残りの1本へ集めることを目指します。集め終わったら、その大きい円盤をゴールへ動かす。これを大きい円盤から順にくり返せば、最終的に塔はそろいます。

よけたい小さい円盤が、すでに1本の棒に大きい順で積まれた塔になっているときは、そこは小さいハノイの塔を1つ解くのと同じです。その塔の枚数が奇数ならまず移したい先へ、偶数ならまずもう1本の棒へ、という判断がそのまま使えます。小さい円盤があちこちの棒に散らばっているときは、この判断はそのままでは当てはまりません。その場の盤面を見て、大きいほうの円盤から順に、動かせる形を作り直していくのが確実です。

遊ぶときに気をつけたいこと

ハノイの塔を攻略するうえで多い失敗は、同じ円盤を2回続けて動かしてしまうこと、一番小さい円盤の向きが途中で逆になること、そして枚数の奇数・偶数を取り違えることの3つです。どれも、最初の1手と「交互に動かす」決まりを意識するだけでかなり減らせます。

遊び方としては、円盤の枚数を減らして3枚から始め、慣れたら4枚、5枚と増やしていくと、つまずかずに楽しめるかなと思います。

ハノイの塔のように、手順の仕組みを理解すると一気に解けるパズルは、ほかにもたくさんあります。決まった動かし方を組み合わせて解く点では、ルービックキューブを7つの手順で揃える方法とも考え方が近いですね。板を滑らせて並べ替えるタイプが気になる人は、15パズルや箱入り娘の最短手数と世界記録の話も楽しめるはずです。

手で触って考えるパズルが好きなら、木製3Dやメタルなど立体パズルの種類別のコツや、知恵の輪・はずるの難易度別の選び方もあわせてどうぞ。

ハノイの塔の最短についてよくある質問

ハノイの塔の最短手数とやり方のまとめ

ハノイの塔の最短手数は、円盤の枚数nに対して2のn乗−1。3枚なら7手、5枚なら31手、7枚なら127手です。これは、一番大きい円盤を動かす前と後に、上の円盤をすべて移さなければならないことから決まる数で、これより少ない手数では解けません。

最短で解くやり方は、次の3点を押さえておけば大丈夫です。

• 奇数番目の手では一番小さい円盤を、決まった向きへ1本ずつ進める
• 偶数番目の手では、一番小さい円盤以外で動かせる唯一の1枚を動かす
• 奇数枚なら1手目はゴールへ、偶数枚なら1手目は作業用の棒へ置く

7枚のように手数が多いときは、全体の真ん中で一番大きい円盤がゴールへ動くことを目印にすると、進み具合を確かめやすくなります。迷ったときも一から積み直さず、まだゴールに来ていない一番大きい円盤から順に立て直せばOKです。

所要時間の表は、1手の秒数を決めて計算したあくまで一般的な目安です。まずは3枚と4枚で一番小さい円盤の向きの違いを手で確かめて、ハノイの塔の最短手順を自分のものにしてみてくださいね。