無料のハノイの塔 | 3本の棒のパズル

使い方

このページを開きます。最初の棒に円盤が4枚積んであります。最少は15手です。
いちばん上の円盤を別の棒にドラッグするか、棒をクリックしてから移したい棒をクリックします。大きな円盤を小さな円盤の上に置こうとすると拒否されます。
「解く」を押すと最短の解が再生されます。「ステップ」で1手ずつ進めることもできます。最後に PNG を保存します。

1枚ずつ、大きな円盤は小さな円盤の上に置かない

1手とは、ある棒のいちばん上の円盤を取り、別の棒か空いている棒に置くことです。手はこの1種類だけです。置く円盤は、その下になる円盤より小さくなければなりません。このルールにより、どの棒の円盤も常に大きい順に並び、いちばん大きいものが底になります。

2ⁿ − 1 手、それより少なくはできない

n 枚の円盤を移すには、まずいちばん大きな円盤の上にある n − 1 枚をよけ、いちばん大きな円盤を1回動かし、その上に n − 1 枚を移します。n − 1 枚に T 手かかるなら、n 枚には 2T + 1 手かかります。つまり 2ⁿ − 1 で、1、3、7、15、31 となります。ここで最も高い塔である8枚では 255 手かかります。

同じパズルを、円盤1枚少なく

上の n − 1 枚を補助の棒に移します。いちばん大きな円盤をゴールに移します。n − 1 枚を補助の棒からゴールに移します。この小さな作業の一つひとつが、また同じパズルです。「ステップ」と「解く」は最短の道筋を再生します。完全な塔からなら、それはこの再帰です。崩れた盤面からでも、合法な局面を探索して見つけた最短の道筋になります。