Introduction

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.

Solve It, Count the Moves

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">Pick the number of disks, then press <b>Solve</b>. The optimal algorithm plays it out one move at a time — it never makes a mistake. Watch the <b>move counter</b>: each extra disk <b>doubles</b> the total (always 2ⁿ - 1).</p>
<div class="controls">
  <label>Disks: <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 <b id="cur">0</b> of <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</button>
  <button id="reset" type="button" class="ghost">Reset</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Towers of Hanoi. The whole algorithm is the classic three-line recursion:
//   hanoi(n, from, to, via): hanoi(n-1, from, via, to); move(from,to); hanoi(n-1, via, to, from)
// It is provably optimal — the shortest solution has exactly 2^n - 1 moves.
// The "thinking" is trivial; the difficulty lives only in the LENGTH of the answer.
let N = 3;
let pegs = [[], [], []];   // pegs[i] = list of disk sizes, bottom..top
let moves = [];            // queued [from,to] moves
let step = 0, timer = null;

function buildMoves(n, from, to, via, out) {
  if (n === 0) return;
  buildMoves(n - 1, from, via, to, out);
  out.push([from, to]);
  buildMoves(n - 1, via, to, from, out);
}

function resetState() {
  if (timer) { clearTimeout(timer); timer = null; }
  pegs = [[], [], []];
  for (let s = N; s >= 1; s--) pegs[0].push(s); // largest at bottom
  moves = []; buildMoves(N, 0, 2, 1, moves);
  step = 0;
  document.getElementById('cur').textContent = '0';
  document.getElementById('tot').textContent = moves.length;
  document.getElementById('exp').textContent = N;
  document.getElementById('opt').textContent = moves.length;
  document.getElementById('solve').disabled = false;
  render();
}

function render() {
  const host = document.getElementById('pegs'); host.innerHTML = '';
  const maxW = 92, minW = 30;
  for (let p = 0; p < 3; p++) {
    const col = document.createElement('div'); col.className = 'peg';
    // render top-first so flex-end stacks bottom disk lowest
    for (let i = pegs[p].length - 1; i >= 0; i--) {
      const size = pegs[p][i];
      const d = document.createElement('div'); d.className = 'disk';
      const w = N === 1 ? maxW : minW + (size - 1) * (maxW - minW) / (N - 1);
      d.style.width = w + '%';
      col.appendChild(d);
    }
    host.appendChild(col);
  }
}

function play() {
  if (step >= moves.length) { document.getElementById('solve').disabled = false; return; }
  const [f, t] = moves[step];
  pegs[t].push(pegs[f].pop());
  step++;
  document.getElementById('cur').textContent = step;
  render();
  timer = setTimeout(play, Math.max(120, 700 / Math.sqrt(moves.length)));
}

document.getElementById('slider').addEventListener('input', e => {
  N = +e.target.value;
  document.getElementById('ndisks').textContent = N;
  resetState();
});
document.getElementById('solve').addEventListener('click', () => {
  if (step >= moves.length) resetState();
  document.getElementById('solve').disabled = true;
  console.log(fmt('Solving %N% disks: optimal = 2^%N% - 1 = %length% moves', { N: N, length: moves.length }));
  play();
});
document.getElementById('reset').addEventListener('click', resetState);
resetState();
Result
Console

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 2n2^{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.

The Real Complexity

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 2n2^{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 2n−12^{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 2n2^{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 2n2^{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.

Where It Matters

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.

Conclusion

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 2n2^{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?

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/towers-of-hanoi/Content licensed under CC BY-NC 4.0.