ハノイの塔をマスターする方法
まとめ: ハノイの塔は1つの再帰ルールで解ける。n枚のディスクをターゲットペグに移動するには、まずn-1枚を中間ペグに移動し、次に最大ディスクをターゲットに移動し、最後にn-1枚をその上に積み直す。このルールをすべてのレベルで適用すれば、常に最小手数に達する。最小手数は常に2の累乗より1少ない数だ。3枚は7手、4枚は15手、5枚は31手、6枚は63手、7枚は127手。
ゲームとは何か
ハノイの塔は、左端のペグにディスクを積み上げた状態で始まる。一番下が最大、一番上が最小。目標は全スタックを右端のペグに移動すること。2つのルールに従う。一度に1枚のみ移動する。大きなディスクを小さなディスクの上に置かない。
それだけだ。タイマーも、ランダム性も、隠れた情報もない。ただ論理と手数の予算だけ。
PlayMemorizeは3枚から7枚までスケールする。手数予算は最適最小値より上から始まり、初心者もパターンを学びながら勝てるようになっている。レベルが上がるにつれ、予算は数学的な最小値に近づいていく。
最小手数: 3枚=7手、4枚=15手、5枚=31手、6枚=63手、7枚=127手。各レベルは1つ下のレベルの約2倍の手数プラス1が必要だ。手数予算を超えるとラウンド終了で負けとなる。
再帰アルゴリズム
ハノイの塔のすべては、あらゆるスケールで繰り返し適用される1つのパターンから生まれる。
ペグBを一時保管として使い、n枚のディスクをペグAからペグCに移動するには:
- n-1枚をAからB（Cを一時的に使用）
- 最大ディスクをAからC
- n-1枚をBからC（Aを一時的に使用）
これが完全なアルゴリズムだ。パズルのあらゆるレベルで、この3ステップ構造を実行している。巧妙なのは、ステップ1と3がそれぞれ同じ問題の小さなインスタンスであり、同じルールで解けるという点だ。
3枚で具体的に追ってみよう。目標: すべてをペグ1からペグ3に移動。
- ステップ1（2枚をペグ1からペグ2へ）: ディスク1をペグ3へ、ディスク2をペグ2へ、ディスク1をペグ2へ。
- ステップ2（ディスク3をペグ1からペグ3へ）: 1手。
- ステップ3（2枚をペグ2からペグ3へ）: ディスク1をペグ1へ、ディスク2をペグ3へ、ディスク1をペグ3へ。
合計: 7手。最適。
3フェーズ思考: ディスクに触れる前に、3つのフェーズを声に出して言う。「n-1枚を中間に移す、最大をターゲットへ、n-1枚を上に積み直す。」再帰の各レベルで、1枚少ない同じ構造を繰り返している。手順の列を暗記するのではなく、フラクタルパターンを実行しているのだ。
ヒント: 動かす前に「今移動が必要な最大のディスクは何か?」と自問しよう。そのディスクを動かすまでのすべては準備だ。このフレームを維持することで、無目的な動きを防ぎ、最適パスを保てる。
手数が固定される理由
最小手数はアルゴリズムから直接導かれる。n枚を解くにはn-1枚を2回解く（ステップ1と3）プラス最大ディスクを1回移動（ステップ2）が必要だ。つまりT(n) = 2 x T(n-1) + 1。T(1)=1から展開すると: ディスク数1から7で1、3、7、15、31、63、127。
各数は2の累乗より1少ない。3枚: 8-1=7。4枚: 16-1=15。5枚: 32-1=31。6枚: 64-1=63。7枚: 128-1=127。
これは偶然ではない。n枚を解くたびにn-1枚を2回解く直接的な結果だ。これを理解すれば、ハノイを推測で解くパズルではなく実行するアルゴリズムとして見るようになる。
難易度別の戦術
3から4枚（学習）: このレベルでは手数予算に余裕がある。各ディスクを「小」「中」「大」と心の中で名付け、どのディスクを狙っているか混乱しないようにしよう。何かに触れる前に3フェーズを追跡する。各ゲーム後、フェーズを声に出して説明する: 「2枚を中間に移し、大きなものを動かし、上に積み直した。」
ヒント: 最大ディスクは完全な解答につき正確に1回移動するはずだ。もう一度移動したくなったら止まろう。アルゴリズム構造が崩れている。最大ディスクの1回の動きはマイルストーンだ。その前はすべて道を切り開くこと、その後はすべて上に積み重ねることだ。
5から6枚（中級）: 手数予算が締まってくる。無駄な動きはすべてコストになる。各レベルで再帰アルゴリズムを厳密に適用しよう。nからn-1枚に再帰するとき、精神的な焦点が移る。今は「始点」「目標」「補助」ペグが異なる小さなハノイパズルを解いている。各再帰レベルで各ペグが果たす役割を追跡しよう。
補助ペグのスワップ: 各再帰レベルで、1つのペグが始点、1つが目標、1つが補助だ。再帰するにつれてこれらの役割が入れ替わる。ペグ1からペグ2にn-1枚を移動するとき、ペグ3が補助だ。次にペグ1からペグ3にn-2枚を移動するとき、ペグ2が補助だ。このスワップを意識的に追跡しよう。5枚と6枚での混乱の最も一般的な原因だ。
7枚（チャレンジ）: 最低127手と厳しい予算で、手ごとに考えることはできない。フェーズごとに考えよう。始める前に、トップレベルの構造をマップする: 6枚を中間に移す（63手）、最大ディスクを右に移す（1手）、6枚を右に移す（63手）。次に各6枚フェーズを同様に細分する。このトップダウン計画により認知負荷が減り、どのフェーズにいるかを見失うエラーを防ぐ。
注意: 7枚では、手順を一手ずつ暗記しようとするのは信頼性が低く不要だ。アルゴリズムを信頼しよう。各分岐点で再帰ルールを適用すれば、正しい動きは常に決まっている。疑いと二の足は手数を無駄にし、予算を使い果たす原因になる。
よくあるミス
試行錯誤のパズルとして扱う。 ランダムな動きが偶に進歩しているように見えるが、行き詰まりに積み重なっていく。ハノイはアルゴリズムであり、実験で解くパズルではない。思考からランダム性を完全に除こう。
ペグの役割を見失う。 同一の3本のペグでは、「始点」「目標」「補助」が、特に上位のディスク数でぼやけることがある。始める前にペグを明示的に心の中でラベル付けしよう: 左=始点、中央=中間、右=目標。すべての再帰レベルでこれらのラベルを一貫して使おう。
最大ディスクを2回以上移動する。 再帰のトップレベルで最大ディスクは正確に1回移動する。もう一度移動したいと感じたら止まろう。アルゴリズム構造が崩れた。3フェーズのフレームに戻り、どこで外れたかを確認しよう。
最大ディスクのチェックポイント: 再帰の各レベルで、n番目のディスクは正確に1回移動するべきだ。最初のサブフェーズ（n-1枚を補助ペグに移動）が完了した後、n番目のディスクは自由で未移動のはずだ。ステップ2の後、ターゲットペグにあるはずだ。そうでなければ、アルゴリズムから外れている。
手数を使い果たす。 アルゴリズムに従っていないか、移動を精神的に「取り消した」（途中で考えを変え別のパスを試みた）ときにのみ起こる。アルゴリズムにコミットしよう。最適だ。より良いパスはない。
注意: 再帰アルゴリズムを使って動きを決めたら、コミットしよう。実行中に疑問を持つと手数が無駄になる。アルゴリズムは最適性を保証している。信頼して躊躇なく実行しよう。
練習プラン
第1週 - アルゴリズムの内面化（3枚）: 毎日3枚のゲームをプレイする。各ゲーム後、3つのフェーズを声に出して説明する。最初の手を打つ前に解答全体を語れるようになるまで繰り返す。
第2週 - スケールアップ（4から5枚）: 4枚のゲームに移行する。再帰が2段階になる。各ゲーム後、構造を追跡する。「3枚に再帰し、大きなディスクを動かし、再び再帰した。」4枚で3から4ゲームプレイしてから5枚に移る。
第3週 - プレッシャー（6枚）: 6枚では手数予算が制約になる。アルゴリズムだけを頼りにプレイしよう。最小値（63手）の5手以内で6枚ゲームを2回完了することを目指す。手数を追跡し、1週間で63手に近づいていくのを見よう。
第4週 - マスタリー（7枚）: 7枚のパズルに挑戦する。ディスクに触れる前にトップダウンのフェーズ計画を適用する。127手に近い手数で7枚を3連続で勝利することが本物のマスターのシグナルだ。
ヒント: ディスクレベルごとの手数のログをつけよう。セッションを通じて最小値に近づいていくのを見ることが、再帰パターンが内面化されている最も明確な外部シグナルだ。7枚で130手以上は無駄な動きがまだ現れている。135手以下で一貫性があれば、構造が固まっている。
ハノイの塔は、マスタリーが絶対的かつ測定可能な数少ないゲームの一つだ。再帰アルゴリズムを知って実行できるか、できないかのどちらかだ。できるようになれば、すべての難易度が同じ論理で解ける。ゆっくり進み、フェーズを名付け、アルゴリズムを信頼すれば、答えは常にそこにある。
