For Teachers
Tower of Hanoi for Teachers
A 45-minute lesson with timings, a worksheet you can print from this page, an answer key that cannot be wrong, and instructions for building a set out of cardboard and pencils.
This puzzle earns its place in a classroom for a reason that is easy to miss: it is one of the very few problems where a six-year-old and an undergraduate can be given the same object and both be working at the edge of what they can do. The six-year-old is finding out that the big disk cannot move until the small ones are out of the way. The undergraduate is proving that no solution shorter than 2n − 1 exists. It is the same fact, met twice.
Why teach this puzzle
Four ideas come out of one object, and they come out in an order that works:
- Pattern recognition. The fewest moves for 1, 2, 3, 4 and 5 disks are 1, 3, 7, 15 and 31. Pupils find the rule themselves; nobody has to be told it.
- Exponential growth. Each disk added doubles the work. Ten disks is 1,023 moves and sixty-four is 585 billion years — a number that does the teaching on its own.
- Decomposition. The puzzle cannot be solved by planning every move. It can only be solved by solving a smaller copy of it first, which is the single most transferable idea in computing.
- Planning and self-monitoring. A move that looks right now can cost ten later. This is measurable enough that psychologists use the puzzle to assess exactly that, which is also a good answer to "when would we ever use this".
It maps onto the computing curriculum at recursion, algorithms and complexity, and onto the maths curriculum at sequences, powers of two and proof by induction. In a single lesson it is a maths lesson; across two it is a computing one.
A 45-minute lesson plan
Built around one decision: the rules first, the method last. A class told the recursive trick at minute five will execute it correctly and learn nothing, because the difficulty is what the lesson is made of. The pattern is collected from the pupils' own move counts, which means it has to be their move counts.
You will need: the worksheet printed one per pair, a physical set per pair if you have them (or make them), and a projector for the last fifteen minutes.
| Time | Stage | What the class is doing |
|---|---|---|
| 0–5 min | Hook | Show the 64-disk legend: priests moving a golden tower, the world ending when they finish. Ask the class to guess how long it takes at one move a second. Take guesses, write the wildest on the board, and do not answer yet. |
| 5–10 min | Rules | Three rules, demonstrated once on three disks — one disk at a time, only the top disk of a tower, never a larger disk onto a smaller one. Do not explain any method. Ask a pupil to come and make the first two moves. |
| 10–22 min | Play | Pairs work through one, two and three disks (a minute or two each), then four, recording every move on the worksheet. One pupil moves, the other records, then they swap. Do not give hints for the first five minutes — being stuck is the part that makes the pattern worth finding. |
| 22–30 min | Find the pattern | Collect the fewest-move counts for 1 to 4 disks on the board: 1, 3, 7, 15. Ask pupils to predict five before anyone plays it, then have one pair check it: 31. Ask what happens each time a disk is added. Push past "it doubles" to "it doubles and adds one", then to why — a five-disk game contains two four-disk games and one extra move. |
| 30–40 min | The big idea | Name it: to move n disks, move n − 1 out of the way, move the biggest one, bring n − 1 back. The same instruction solves every size, which is what recursion is. Play the animated solver on the projector while the class calls out what it is doing. |
| 40–45 min | Answer the hook | Back to the 64 disks: 2⁶⁴ − 1 moves, about 585 billion years. Let the calculator show the number growing as the slider moves. The lesson lands here — doubling is not "a bit more each time", it is the difference between a minute and the age of the universe. |
The one thing to say at minute thirty
When the class has the "double it and add one" rule, the move that turns a maths lesson into a computing one is this sentence: to move five disks, you have to move four disks twice. Once to get them out of the way, once to bring them back. That is why the count doubles, and it is also the whole algorithm — the recursive solution is that sentence written in three lines of code.
Answer key
Three disks, from tower A to tower C, in the fewest moves that exist — all 7 of them:
- Disk 1: A → C
- Disk 2: A → B
- Disk 1: C → B
- Disk 3: A → C
- Disk 1: B → A
- Disk 2: B → C
- Disk 1: A → C
A pupil who finishes on tower B in seven moves has solved the mirror-image puzzle — right method, wrong tower. Swap B and C in their list and it is the key above, move for move. The fewest-move counts for the prediction table are 1, 3, 7, 15, 31, 63 for 1 to 6 disks. Every number and every move above is generated by the same solver that runs the board on this site, so the key cannot drift away from what pupils see on screen.
The printable worksheet
One side of paper, sized to fit A4 and US Letter alike. Print it one per pair — one pupil moves the disks, the other records, and they swap for part two.
Or press Ctrl + P (⌘ + P on a Mac) to print this page's lesson plan instead.
Tower of Hanoi — Worksheet
Name: Class: Date:
The rules. Move one disk at a time. Only ever the top disk of a tower. A larger disk may never sit on a smaller one. Move the whole stack from tower A to tower C.
Part 1 — Three disks
Solve it once for practice. Then solve it again in as few moves as you can, and record that attempt below: which disk you moved, and from which tower to which.
| Move | Disk | From | To |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 |
| Move | Disk | From | To |
|---|---|---|---|
| 5 | |||
| 6 | |||
| 7 | |||
| 8 |
My best was moves.
Part 2 — Predict, then check
Fill in the moves you needed. Before you try the next size, write down what you think it will take. Then find out.
| Disks | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| My prediction | ||||||
| Fewest moves |
What happens to the number of moves each time you add one disk?
Part 3 — Why
Before the largest disk can move to tower C, where must every smaller disk be, and why?
Part 4 — Draw it
Set up five disks on tower A. Now move the four smallest onto tower B, and draw exactly what the three towers look like when you have. Number each disk you draw.
Play it, check your answer and watch the solution at towerofhanoionline.com
Build a physical tower
Hands beat screens for the first twenty minutes of this topic. A pupil who has picked a disk up and found there is nowhere legal to put it has learned something a click does not teach. A class set costs about an hour and a few pounds of cardboard.
You need: stiff cardboard, three pencils or wooden dowels per set, tape or glue, scissors, a hole punch or skewer, and a ruler.
- Cut the base. Cut one strip of stiff cardboard about 30 cm by 10 cm. This is the board that all three towers stand on, and one piece keeps them the same height and spacing.
- Fix three pegs. Push three pencils, wooden dowels or bamboo skewers through the base at 10 cm intervals, and tape or glue them underneath. Twelve centimetres of peg above the base is enough for five disks.
- Cut the disks. Cut five cardboard circles of clearly different sizes — 10, 8.5, 7, 5.5 and 4 cm across works well. Different colours help pupils talk about which disk is which.
- Punch the centres. Punch a hole in the centre of each disk, slightly wider than the pegs, so disks drop on and lift off without being forced.
- Label and stack. Number the disks 1 to 5 from smallest to largest, mark the bases A, B and C, and stack all five on A with the largest at the bottom. The set is now the puzzle on this site, in a pupil's hands.
Two shortcuts if the cutting is the problem. Stacking rings from an infant toy are already a Tower of Hanoi set — three upturned cups make the towers. So do coins of different sizes on three drawn circles, which reduces the whole build to a sheet of paper and whatever is in a pocket, and works at any class size.
Ages, levels and extensions
The same object, pitched five ways. Each row is a complete lesson's worth on its own.
| Age | Disks | What they are working on |
|---|---|---|
| 6–8 | 3 | Following the rules, and noticing that the big disk has to wait. Finishing at all is the achievement; move counts come later. |
| 8–11 | 3–5 | Counting moves, comparing with a partner, and finding the doubling pattern in 1, 3, 7, 15, 31. |
| 11–14 | 4–7 | Writing the rule as 2n − 1, predicting before testing, and meeting exponential growth as a number rather than as a word. |
| 14–16 | 5–8 | The recursive method stated properly, and proving by induction that no shorter solution exists. |
| 16+ | Any | Writing the algorithm in code, solving the recurrence T(n) = 2T(n − 1) + 1, and the binary correspondence — counting up in binary solves the puzzle. |
Four extensions that go somewhere
- Start it scrambled. Deal the disks across the three towers at random and ask for the shortest route home. The learned opening stops working and pupils have to reason from the position — the daily challenge is exactly this, one new position a day.
- Race the algorithm. One pupil plays by hand while another follows the written method on paper. The method wins, every time, and that is the point.
- Count in binary. Write the move number in binary and the position of the lowest 1 bit is the disk that moves. Pupils usually refuse to believe this until they check it.
- Add a fourth tower. The best-known method took seventy-three years to prove optimal — Thierry Bousch finished it in 2014 — and for five towers nobody knows. Pupils can play the four-peg board and see how much shorter the game gets. A question with no known answer, in a lesson, is rarer than it should be.
What to look for
The move count is the least interesting thing a pupil produces. Three things worth more:
- Do they clear the largest disk deliberately? A pupil who says "I have to get these two off first" before touching anything has understood the decomposition, whatever their move count says.
- Does the prediction improve? A guess of "about 20" for four disks followed by "31" for five is the doubling rule being formed. Guessing 16 then 17 is not.
- Can they explain the cost? "Every disk you add doubles it, because you have to move the smaller stack twice" is the whole lesson in one sentence — and it is a sentence, not a number, so it is the one worth asking for out loud.
A pupil who solves five disks in 40 moves and can say why it cannot be done in fewer than 31 has done better than one who solves it in 31 and cannot.
Using this site in class
Everything here is free, needs no account, and works on a school network without a sign-up. Four things are worth projecting:
- The board — play it with the class at three disks, then hand the mouse over. Auto Solve plays the perfect game at four speeds when you want to show the shape rather than grind it out.
- The calculator — for the last five minutes. Drag the slider from 5 to 64 and let the number and the timescale do the arguing.
- The solver — type in the position a stuck pair is actually in and step through the way out. It works from any legal position, not just a full stack, which is what makes it useful mid-lesson.
- The algorithm page — for the follow-up computing lesson. The code runs beside a board and highlights the line it is executing, in Python, Java, C++ and three more.
Linking to any of these from a course page or a handout is welcome, and so is printing the worksheet for your classes.
Put the board in your own page
If your course pages, VLE or wiki let you paste HTML, you can put a working board inside a lesson rather than sending pupils away to play it. Paste this where you want the board to appear:
Embed the board
<iframe
src="https://towerofhanoionline.com/embed/"
title="Tower of Hanoi"
width="100%"
height="820"
style="border:0;max-width:100%"
loading="lazy"
></iframe>That is the same board as the main page — drag or tap to move a disk, undo, a hint, the full move timeline, and the solver. It needs no account and sets no cookies, and nothing a pupil does in it is sent anywhere.
Start it at a particular puzzle. Two parameters set the board up before a pupil touches it. disks is the size, from 3 to 15; pos is a starting position, one letter per disk with the smallest disk first, so pos=CAB means disk 1 on tower C, disk 2 on A and disk 3 on B. A three-disk board to open a lesson with:
Embed a three-disk board
<iframe
src="https://towerofhanoionline.com/embed/?disks=3"
title="Tower of Hanoi — three disks"
width="100%"
height="820"
style="border:0;max-width:100%"
loading="lazy"
></iframe>The quickest way to get one of these is to set the board up by hand:
- Play the board to the position you want.
- Press Copy link under the statistics.
- Keep only the part from
?onwards, and paste it straight after/embed/in the snippet above.
The parameters are the same on both pages, but the address is not — pasting the whole link would embed the full page instead of the board.
Sizing.
- 680 pixels wide or more: the height above fits the board, the controls and the move timeline side by side.
- Narrower: everything stacks, and the board wants nearer 1,020 pixels of height.
- Never narrower than 420 pixels.
You are welcome to embed it in a school, college or university page, in course notes or in a handout, free and without asking. The one thing to leave alone is the credit line under the board — it is the link back, and it is what pays for the site being free.
Questions from teachers
What age group is the Tower of Hanoi suitable for?
Three disks works with children of about six upwards — the rules are simple enough to follow and seven moves is short enough to finish. Four and five disks suit ages eight to twelve. The pattern-finding and the 2ⁿ − 1 formula are usually a lower-secondary topic, around ages eleven to fourteen, and the recursion idea behind it is taught to sixteen-year-olds and to first-year undergraduates with the same puzzle.
How long does a Tower of Hanoi lesson take?
One 45-minute lesson covers the rules, hands-on play at three and four disks, the doubling pattern and the formula. The lesson plan on this page is built for that length. If you want the recursive method taught properly as well, plan a second lesson — trying to fit both into one leaves no time for pupils to be stuck, and being stuck is where the pattern gets found.
What does the Tower of Hanoi actually teach?
Four things, and they are unusually well connected. Pattern recognition, because the move counts 1, 3, 7, 15, 31 have an obvious rule. Exponential growth, because each added disk doubles the work and the numbers become absurd fast. Problem decomposition, because the only way to solve it is to solve a smaller copy of it first. And planning, because a move that looks right now can cost you the next ten — which is why clinical psychologists use the puzzle to measure exactly that.
Do I need computers for this lesson?
No. The worksheet and a physical set of disks are enough for the whole lesson, and the build instructions on this page make a five-disk set from cardboard and pencils. A projector is useful for the last fifteen minutes: watching the solver play a six-disk game and watching the calculator's number explode are both much stronger on a screen than described.
Can I use this site and worksheet in my classroom?
Yes. The site is free, has no account and no sign-up, and the worksheet is printable from this page. You are welcome to print it for your classes and to link to any page here from a lesson page, a course site or a handout.
Is there an answer key?
Yes — the seven-move three-disk solution and the fewest-move counts up to six disks are both on this page, above the worksheet. They are generated by the same solver that runs the board, so they cannot disagree with what pupils see on screen.