Tower of Hanoi
Three pegs, and a cone of disks with the largest at the bottom. Move the whole tower to the right peg. You may move only one disk at a time, and a larger disk may never sit on a smaller one. The shortest solution takes 2ⁿ − 1 moves: 1, 3, 7, 15, 31, and so on. Move one disk at a time onto a larger disk or an empty peg. The whole tower should end on the right peg. The shortest solution takes 2ⁿ − 1 moves. Drag a disk, or click one peg and then another.
How it works
- Open this page. Four disks are stacked on the start peg. Fifteen moves is the minimum.
- Drag the top disk to another peg, or click a peg and then the peg you want. A larger disk on a smaller one is refused.
- Press Solve to watch a shortest solution, or Step through it. Then save a PNG.
One disk, and never a larger one on a smaller one
A move takes the top disk of one peg and sets it on another peg, or on an empty peg. That is the only kind of move. The disk you place must be smaller than the disk it lands on. With those rules the disks on every peg stay sorted, largest at the bottom.
2ⁿ − 1 moves, and no fewer
To shift n disks you first shift the n − 1 disks above the largest one out of the way, move the largest disk once, then shift the n − 1 disks on top of it. If n − 1 disks take T moves, n disks take 2T + 1. That is 2ⁿ − 1: 1, 3, 7, 15, 31. Eight disks, the largest tower here, take 255 moves.
The same puzzle, one disk smaller
Move the top n − 1 disks to the spare peg. Move the largest disk to the goal. Move the n − 1 disks from the spare peg onto the goal. Each of those smaller jobs is the same puzzle again. Step and Solve play a shortest path. From a perfect tower it is this recursion. From a scrambled board it is still a shortest path, found by searching the legal positions.
Frequently asked questions
What are the rules of the Tower of Hanoi?
Move one disk at a time. Take the top disk of a peg and place it on another peg. Never put a larger disk on a smaller one.
How many moves does the shortest solution take?
2ⁿ − 1. One disk is 1 move, two disks are 3, three are 7, four are 15, and five are 31.
Who invented the Tower of Hanoi?
Édouard Lucas introduced the puzzle in 1883. The story of priests moving 64 golden disks is the legend he told with it.
Can I watch the solution?
Yes. Step plays one move of a shortest solution. Solve plays the rest. Watch 3 disks runs the classic recursive strategy from the start.
Related tools
Tower of Hanoi
The Tower of Hanoi: three pegs, one disk at a time, and never a larger disk on a smaller one. The shortest solution is 2ⁿ−1 moves. Édouard Lucas introduced the puzzle in 1883.
Knight's Tour
Jump a chess knight to every square of the board exactly once. Play it yourself with Warnsdorff hints, or watch Solve finish an open or closed tour. Save the path as a PNG.
Eight Queens
Place eight queens on a chessboard so that none attacks another. Try it yourself, watch the backtracking search find a solution step by step, and go through all 92 solutions.
15 Puzzle
Play the classic 15 sliding puzzle in your browser on 3×3, 4×4, or 5×5 wooden tiles. Shuffle, slide whole rows at once, try Sam Loyd's impossible 14-15, or watch Solve finish it.
Buffon's Needle
Drop needles on a lined floor in your browser. Count the crossings and watch Buffon's 1777 experiment estimate π.
Multiplication Circles
Join each number on a circle to its multiple. Draw a times table, a cardioid, or a string figure on paper, chalk, or wood.
The Collatz Conjecture
Explore the Collatz 3n+1 problem in your browser. Walk hailstone sequences, grow a geometric Collatz tree, and zoom the continuous Collatz fractal.
Langton's Ant
Run Langton's Ant in your browser. Watch symmetry, chaos and the 104-step highway, then try multi-colour rules, several ants, a hex grid and turmites.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor