gamesblog

Tower of Hanoi

How many moves does a Tower of Hanoi of n disks take? Derive 2ⁿ − 1, then count from a position part-way through, and with neighbouring pegs only.

  • Logic
  • Untimed
  • Endless levels

How it plays

Disks of different sizes sit on pegs. A move takes the top disk of one peg to another, never onto a smaller disk. The questions are counts: the fewest moves for the whole tower, how often one disk moves, the fewest from a position part-way through, and the fewest when disks may only move to a neighbouring peg.

Every answer comes from one idea: the largest disk can only move when everything smaller is out of its way, on one other peg. So moving n disks means moving n − 1 disks, then one, then n − 1 again — which is why each extra disk doubles the count, plus one.

Levels add kinds of question, then disks, without end. Answer by choosing or by typing.

Keys

Space starts and skips ahead · 1–9 pick · Enter submits · Esc stops. On a phone, tap.

What it trains

This practises turning a recursive procedure into a recurrence and solving it, on the Tower of Hanoi. It claims nothing wider.

Learn

How to get better at tower of hanoi: the method, the techniques, what each new level asks of you, and the traps the wrong answers are made of.

Your approach to each question

  1. Read which kind of count is asked: the whole tower, how often one disk moves, the fewest from a position part-way, or the tower with neighbouring pegs only. Each has its own formula.
  2. Find n, the number of disks, and for a one-disk question, which disk k. Disk 1 is the smallest, disk n the largest.
  3. Apply the formula as a power: 2ⁿ − 1 for the tower, 2^(n−k) for one disk, 3ⁿ − 1 for neighbouring pegs. For a position, work from the largest disk down, as below.
  4. Before you pick, check the answer against a small case you know: 3 disks take 7 moves, disk 1 of 3 moves 4 times, 3 disks on neighbouring pegs take 26.

Techniques and tricks

  • Move the tower above it

    The largest disk can move only when every smaller disk sits on the one other peg. So n disks = n − 1 disks, then the largest, then n − 1 again: T(n) = 2·T(n − 1) + 1.

    e.g. T(3) = 2 × 3 + 1 = 7; T(4) = 2 × 7 + 1 = 15

  • One less than a power of two

    Add 1 to every tower count and it doubles each time: 2, 4, 8, 16. So the fewest moves for n disks is 2ⁿ − 1. Know the powers of two to 2²⁰ = 1,048,576.

    e.g. 10 disks: 2¹⁰ − 1 = 1,023

  • Each disk up doubles

    The largest disk moves once. Each disk above it moves twice as often as the one beneath, so disk k of n moves 2^(n−k) times. Count up from the bottom, not the top.

    e.g. Disk 7 of 10: 10 − 7 = 3, so 2³ = 8 moves

  • Largest first, switch the target

    For a position part-way, start with the largest disk and a target of C. If the disk is on its target, it costs 0 and the target stays. If not, it costs 2^(k−1), and the target for the smaller disks becomes the third peg — neither where it is nor where it is going.

    e.g. Disk 3 on A, disks 2 and 1 on C. Disk 3 costs 4, so 2 and 1 must gather on B: disk 2 costs 2, then disk 1 must clear to A, costing 1. Total 7

  • Neighbouring pegs triple

    When a disk may only step A↔B or B↔C, the largest moves twice, and the rest must move all the way across three times: T(n) = 3·T(n − 1) + 2. Add 1 and it triples, so T(n) = 3ⁿ − 1.

    e.g. 3 disks: 3³ − 1 = 26; 4 disks: 3⁴ − 1 = 80

As the levels climb

  • The ladder opens with whole-tower questions on 3 disks, then adds how often one disk moves. Then the disks go up to 4.
  • Next come positions part-way through, then 5 disks, then the neighbouring-pegs variant, then 6 disks. After that only the disks grow, one a level, without end.
  • Counts pass the millions around 20 disks and keep doubling. Do not multiply out; know the power and subtract one, and read the options by their leading digits and length.
  • If Time pressure is on, each question gets 20 seconds plus 2 per disk; a position question gets 4 more per disk, up to 10 disks, because you must work through each.

Traps to avoid

  • Forgetting the minus one. 2ⁿ is always offered beside 2ⁿ − 1 for the whole tower. Check with one disk: it takes one move, which is 2¹ − 1, not 2¹.
  • Counting the one-disk power from the wrong end. Disk k moves 2^(n−k) times, so the smallest disk moves most. 2^(k−1) — counting from the top — is the lure.
  • Ignoring disks that look settled. In a position, a small disk already on C may still have to leave so a larger one can pass. Adding up only the disks not on C gives one of the wrong options; the whole-tower count 2ⁿ − 1 is another.
  • Using the two-way formula on neighbouring pegs. With A↔C banned, the count is 3ⁿ − 1, far more than 2ⁿ − 1; 3ⁿ without the minus one is offered too.
  • One out on the recurrence. For the whole tower, T(n − 1) — the count for one disk fewer — is the next lure after 2ⁿ, and with more options shown T(n + 1) joins it. Check n before you pick.

How to practise

  • Use “Kinds of question” to drill “From a position part-way” on its own — it is the one that needs working, not a formula — until the target switch is automatic.
  • Switch “Answer by” to “Typing the number” once you choose right every time. Typing 2ⁿ − 1 for large n makes you know the powers of two, not recognise them.
  • Say the recurrence out loud before you compute — “n − 1 off, the big one across, n − 1 back” — so the formula comes from the picture, not from memory alone.
  • When you miss a position question, read the working’s disk-by-disk lines and redo them yourself on paper, switching the target at each disk that moves.

Levels

It is untimed unless you turn the clock on. There is no last level: at least one dial turns without end. Your level is judged on your last ten answers, every ten: 90% moves you up, below 80% moves you down, which holds most people near four in five right.

All of it is in the settings beside Start — how many answers a judgement looks at and how often it recalibrates, the thresholds, the time, which questions, how many options, and whether you see each verdict at once or review them together at the judgement. You can also jump to any level.

More logic

All games →