Towers of Hanoi

The Towers of Hanoi is one of the most famous puzzles in computer science. Three pegs stand in a row. On the first sits a stack of disks, largest at the bottom, shrinking to the top. Your goal: move the whole stack to the third peg. The rules are tiny — move one disk at a time, and never put a larger disk on a smaller one.

What makes it beloved is that a single idea solves it perfectly. To move n disks from A to C: first move the top n-1 disks out of the way to B, then move the biggest disk to C, then move those n-1 disks from B onto C. That's the whole algorithm — a three-line recursion that never makes a wrong move.

So the thinking is easy. The catch is hiding somewhere else entirely — not in how hard it is to figure out the moves, but in how many moves there are.

Pick how many disks you want, then let the optimal algorithm play it out move by move. The solver never makes a mistake — but watch the move counter.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label>{{disks_label}} <b id="ndisks">3</b></label>
  <input id="slider" type="range" min="1" max="8" value="3">
</div>
<div id="pegs" class="pegs"></div>
<div class="readout">
  <span>{{move_word}} <b id="cur">0</b> {{of_word}} <b id="tot">7</b></span>
  <span class="formula">2<sup id="exp">3</sup> - 1 = <b id="opt">7</b></span>
</div>
<div class="btns">
  <button id="solve" type="button">{{solve_btn}}</button>
  <button id="reset" type="button" class="ghost">{{reset_btn}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; align-items: center; gap: .8rem; margin: .3rem 0 .6rem; font-size: .95rem; }
.controls input { flex: 1; }
.pegs { display: grid; grid-template-columns: repeat(3, 1fr); gap: 8px; height: 150px;
        align-items: end; padding: 0 4px; }
.peg { position: relative; height: 100%; display: flex; flex-direction: column;
       justify-content: flex-end; align-items: center; }
.peg::before { content: ""; position: absolute; bottom: 0; width: 100%; height: 6px;
               background: #1d3557; border-radius: 3px; }
.peg::after { content: ""; position: absolute; bottom: 6px; width: 6px; height: 90%;
              background: #cdd9e3; border-radius: 3px; }
.disk { height: 16px; border-radius: 8px; margin-top: 3px; z-index: 1;
        background: #457b9d; box-shadow: inset 0 -2px 0 rgba(0,0,0,.15); }
.readout { display: flex; justify-content: space-between; align-items: center;
           margin: .7rem 0 .5rem; font-size: 1rem; font-weight: 600; }
.formula { color: #1d3557; font: 700 1rem ui-monospace, monospace; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button:disabled { opacity: .5; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Add a disk and the number of moves doesn't grow a little — it doubles. One disk needs 1 move, two need 3, three need 7, then 15, 31, 63... always exactly $2^{n}$ - 1. The algorithm that produces this is trivial and provably optimal; there is simply no shorter sequence. The difficulty was never in the reasoning — it lives entirely in the length of the answer.

Here is the surprise. The Towers of Hanoi is not a hard problem to solve in the usual sense — the recursion is short, deterministic, and provably optimal. You can prove by induction that $2^{n}$ - 1 moves are both necessary and sufficient: the big disk must move at least once, and to free it you must first clear the n-1 disks above it and then rebuild them, each of which already costs $2^{n-1}$ - 1 moves.

• The algorithm is trivial. A three-line recursion decides every move in constant time. There is no searching, no backtracking, no guessing.
• The answer is exponential. The shortest possible solution has $2^{n}$ - 1 moves. For 64 disks — the size in the original legend — that's over 18 quintillion moves. At one move per second it would take longer than the age of the universe.
• Status: solved, exactly. This isn't an open question or a conjecture. The optimal move count is a closed-form, proven fact: exactly $2^{n}$ - 1, a Mersenne number.

So where does the hardness live? In the size of the output. Any algorithm that prints the full solution must take at least exponential time, simply because the solution itself is exponentially long. This is output-sensitive difficulty — the opposite of problems like P vs NP, where the answer is short but finding it may be brutal. Hanoi flips that: finding is free, but the answer is gigantic.

The Towers of Hanoi earns its fame far beyond the toy:

• Teaching recursion. It is the canonical first example of a recursive algorithm: a problem defined in terms of smaller copies of itself. The elegance of "move n-1, move 1, move n-1" makes the idea click.
• The cost of the answer. It is the cleanest demonstration that an algorithm can be optimal and yet hopeless — because the output is too big. That lesson recurs whenever a task asks you to list, enumerate, or generate exponentially many things.
• Backup rotation. The "Tower of Hanoi" rotation scheme for backup tapes uses the same doubling structure to decide which tape to reuse, balancing how far back in time copies survive.
• Recognizing intractability by output. Knowing Hanoi trains the instinct to ask not just "is the algorithm clever?" but "how big is the thing it has to produce?" — a different axis of hardness from SAT and the rest of the NP world.

Learn Hanoi and you've met an idea that runs underneath all of algorithm analysis: sometimes you can solve a problem perfectly and still never finish, because the answer is simply too long to write down.

The Towers of Hanoi carries a quiet lesson: an algorithm can be trivial to write, instant to decide each step, and provably optimal — and still be doomed to run forever. Not because the thinking is hard, but because the answer is exponentially long: exactly $2^{n}$ - 1 moves, no shorter sequence possible.

That is a different face of difficulty from the one in P vs NP, where a short answer can be agonizing to find. Here the search is free and the answer is the wall. The next time a task seems easy "in principle," it's worth asking the Hanoi question first — not can I find the answer? but how big is the answer I'd have to produce?