About Tower of Hanoi
The Tower of Hanoi is a classic puzzle with three pegs and a stack of disks of different sizes. You must move the whole stack from the left peg to the right peg, one disk at a time, without ever putting a larger disk on a smaller one. You can choose from 3 to 7 disks.
How to play
- All disks start on the left peg, largest at the bottom. The puzzle is solved when they are all on the right peg; stacking them on the middle peg does not count.
- You can only move the top disk of a peg, and you can only place it on an empty peg or on a larger disk.
- An illegal move is refused: the board flashes and the disk is put back. It does not count as a move.
- The fewest possible moves for n disks is 2 to the power n, minus 1. That is 7 for 3 disks, 15 for 4 and 127 for 7. The score bar shows this as Best possible.
- Solving scores 100 points per disk, minus 5 points for each move above the minimum, with a minimum score of 1.
Controls
- Mouse or touch: tap a peg to lift its top disk, then tap the peg where you want to put it.
- Tap the same peg again to put the disk back down without moving it.
- The disk menu chooses 3, 4, 5, 6 or 7 disks and restarts. The game starts with 4.
Tips and strategy
- Think recursively. To move a tower of n disks to the right, first move the top n - 1 disks to the middle, then move the biggest disk to the right, then move the n - 1 disks on top of it.
- The smallest disk moves on every other turn, always around the pegs in the same direction. With an even number of disks, cycle it left, middle, right; with an odd number, cycle it left, right, middle.
- On the turns between, there is only ever one legal move that does not involve the smallest disk. Make it.
- If you lose track, find the largest disk that is not yet on the right peg. Your goal is to clear everything above it and the target spot, then move it.
- Practise with 3 disks until you can do it in 7 moves without thinking, then step up. Each extra disk doubles the work.
Background
The puzzle was invented by the French mathematician Edouard Lucas and sold as a toy in 1883. It came with a story about a temple where priests move 64 golden disks, and the world ends when they finish. With 64 disks the minimum is 2 to the power 64 minus 1 moves, which would take hundreds of billions of years at one move per second. The puzzle is a standard example for teaching recursion in computer science.
Questions
- What is the minimum number of moves?
- 2 to the power of the number of disks, minus 1. For example 31 moves with 5 disks. The game shows this number beside your move count.
- Do illegal moves count against me?
- No. A move that would put a larger disk on a smaller one is rejected and does not add to your move count.