解く
ハノイの塔ソルバー
積み上がった状態だけでなく、正しい配置ならどれでも最短で解きます。いまの盤面のとおりに並べて、最適な手順が進むのを見てください。
最短の解
31手25 − 1 = 31
基本のパズル：すべての円盤が塔Aから始まり、塔Cで終わります。
再生の準備ができました31 手中 0 手目
←→1手ずつSpace再生HomeEnd端へ
すべての手を順番に
円盤1がいちばん小さく、A → C は「塔Aのいちばん上の円盤を取り、塔Cに置く」という意味です。行を選ぶと、盤面がその手まで進みます。
16手目は、円盤5がAからCへ渡る手です。その前後の15手はどちらも同じ解で、4枚の解をまず予備の塔へ、次に予備の塔から行っています。
| # | 円盤 | 移動元 | 移動先 |
|---|---|---|---|
| 1 | 1 | A | C |
| 2 | 2 | A | B |
| 3 | 1 | C | B |
| 4 | 3 | A | C |
| 5 | 1 | B | A |
| 6 | 2 | B | C |
| 7 | 1 | A | C |
| 8 | 4 | A | B |
| 9 | 1 | C | B |
| 10 | 2 | C | A |
| 11 | 1 | B | A |
| 12 | 3 | C | B |
| 13 | 1 | A | C |
| 14 | 2 | A | B |
| 15 | 1 | C | B |
| 16 | 5 | A | C |
| 17 | 1 | B | A |
| 18 | 2 | B | C |
| 19 | 1 | A | C |
| 20 | 3 | B | A |
| 21 | 1 | C | B |
| 22 | 2 | C | A |
| 23 | 1 | B | A |
| 24 | 4 | B | C |
| 25 | 1 | A | C |
| 26 | 2 | A | B |
| 27 | 1 | C | B |
| 28 | 3 | A | C |
| 29 | 1 | B | A |
| 30 | 2 | B | C |
| 31 | 1 | A | C |
ソルバーのしくみ
やり方はパズル自身の理屈を前から順にたどるだけです。いちばん大きい円盤を目標の塔に据えるには、それより小さい円盤がすべてよそに、つまり残る1本の塔に積まれていなければなりません。そこでソルバーは、まず小さい山をそこへ移すよう求め、大きい円盤を渡し、それから小さい山をその上へ運ぶよう求めます。この求めはどれも1枚少ないだけの同じ問題で、最後は1歩で動く1枚にたどり着きます。
積み上がった状態しか扱えないソルバーとの違いは、たった一行の考え方です。いちばん大きい円盤がすでに目標の塔にあるなら、その円盤にすることは何もなく、問題はその上にある円盤だけに縮みます。この一つの場合があるおかげで、最初からやり直させるのではなく、途中の盤面から解けます。自由配置から出る手数が 2ⁿ − 1 より少なく、途中まで進めた盤面ではずっと少なくなるのもこのためです。
上にあるn−1枚を予備の塔へ移します。それが済むまで、ほかには何もできません。
いちばん大きい円盤が自由になり、目標の塔も空いています。1手で渡ります。この段階に必要なのはその1手だけです。
その上にn−1枚を積み直します。1枚少ないだけの同じ問題で、最後は1手で動く円盤1枚にたどり着きます。
手順の読み方
各行が1手を表します。どの円盤が、どの塔を離れ、どの塔に着くか。円盤1がいちばん小さい円盤です。ルールに合うかどうかを確かめる必要はありません。一覧のすべての手は、作られ方からしてすでに正しい手です。
積み上がった状態から始めると、2つのパターンがすぐに見えてきます。
- いちばん小さい円盤は1手おきに動きます（1手目、3手目、5手目……）。しかも3本の塔をいつも同じ向きに回ります。
- その間の手は、いちばん小さい円盤に触らない唯一の正しい手です。
これが反復法のすべてで、積み上がった状態からの手順ならどれからでも読み取れます。自由配置からの一覧も最短であることは変わりませんが、小さな移動をつなぎ合わせたものなので、いちばん小さい円盤が途中で向きを変えることがあります。反復による解法がなぜこの方法で解けるのかを示し、攻略法がそれを実際に打つ手に変えます。再帰そのものを6つの言語で1行ずつ追うならハノイの塔のアルゴリズムへ。
よくある枚数にはそれぞれのページもあり、全手順とその枚数ならではの点が載っています：3枚から10枚までの解答と伝説の64枚。
手順を持ち帰る
アドレスバーはつねに画面の盤面を表しています。全体の移動なら ?disks=5&from=A&to=C、自由配置ならさらに pos=CBBAA のような符号が付きます。小さい円盤から順に1枚1文字です。そのリンクをコピーすれば、まったく同じパズルが開きます。行き詰まった配置を言葉で説明するかわりに、そのまま送れるということでもあります。
手順そのものはクリップボードにコピーできるほか、実物のパズルの横で読むためのテキストファイルとしても、表計算で開くためのCSVとしてもダウンロードできます。ダウンロードには表のような上限がありません。15枚でも、ファイルには32,767手すべてが入っています。
一覧が12枚で止まる理由
手数は円盤1枚ごとに倍になります。12枚は4,095手で、長いながらも使える表です。13枚は8,191手、20枚は1,048,575手になり、100万行の表を人が使える形にできるブラウザーはありません。12枚を超えると、このページは正確な手数を示して盤面の再生は残します。上のダウンロードには全手順が入っているので、解が手に入らなくなるわけではなく、表にしないだけです。手数だけを知りたいときは、計算機が64枚でもその先でも答えます。
よくある質問
ハノイの塔ソルバーは何をしますか？
すべての円盤を1本の塔に集める、いちばん短い手順を出します。枚数を指定すれば昔ながらの全体の移動を解き、途中の配置を与えればそこから解きます。後者はほとんどのソルバーにできないことです。
その手順は最短ですか？
はい。このソルバーは正しいだけでなく、最適であることが証明できます。積み上がった状態からはちょうど 2ⁿ − 1 手を出し、ほかのどんな正しい配置からも本当の最短経路を出します。これより短い手順は存在しません。
途中まで進めた配置から解けますか？
はい。そのための自由配置です。それぞれの円盤をいま置かれている塔に指定すれば、そこから最少の手数で仕上げます。多くの場合、最初からやり直すよりずっと少ない手数で済みます。
手順を共有したり保存したりできますか？
はい。アドレスバーにはいま見ている盤面がそのまま入っています。/ja/solver/?disks=5&from=A&to=C は5枚の全体移動で、自由配置には pos=CBBAA のような符号が付きます。小さい円盤から順に1枚1文字です。リンクをコピーすれば、まったく同じパズルが開きます。
手順をダウンロードできますか？
はい。コピーボタンの隣から、ふつうの .txt ファイルとしても、1手1行の .csv としてもダウンロードできます。表として表示しないほど長い手順でもダウンロードはできるので、15枚の答えも手元に残せます。
手順一覧はどう読みますか？
各行が1手を表します。円盤の番号、離れる塔、着く塔の順です。円盤1がいちばん小さい円盤です。順番どおりに動かせばパズルは解けます。どの円盤なら動かせるかを考える必要はありません。一覧にある手はすべて、すでに正しい手だからです。
なぜ手順一覧は12枚で止まるのですか？
12枚の解は4,095手です。20枚では1,048,575行になり、それを役に立つ形で描けるブラウザーはありません。そこで12枚を超えると、一覧のかわりに正確な手数と式を示し、盤面は変わらず解を再生します。