Towers of Hanoi (3D)
About this app
The classic recursion puzzle in space: choose the number of disks, let the algorithm solve it optimally (2ⁿ−1 moves) or move them yourself — peg by peg the recursive idea T(n)=2·T(n−1)+1 becomes visible.
The puzzle and its recursive solution
A tower of n disks has to move from peg A to peg C. Only one disk may move at a time, and a larger disk may never lie on a smaller one. The recursive idea: to move n disks, first move the top n − 1 disks to the spare peg B, then move the largest disk to C in a single move, and finally move the n − 1 disks from B to C. This gives T(n) = 2 · T(n − 1) + 1, so exactly 2ⁿ − 1 moves. It cannot be done in fewer.
What the app shows
Three pegs and a tower of disks in 3D, viewable from several angles: default view, front, top view, or close to the start and target peg. A status field counts the moves and shows the minimum 2ⁿ − 1 and the last move. When solving automatically the optimal recursive solution plays out, and you can see that the smallest disk moves on every second move while the largest moves only once.
Try it yourself
Set 3 to 8 disks with the slider and try to move the tower yourself, or let the algorithm solve it, all at once or one move at a time, at an adjustable speed. Compare your move counter with the minimum. With 8 disks it already takes 255 moves, and every extra disk doubles the work.
Frequently asked questions
- How many moves does the Tower of Hanoi take?
- At least 2ⁿ − 1 moves for n disks: 7 for 3 disks, 15 for 4, 255 for 8. Every additional disk doubles the number of moves and adds one.
- How does the recursive Tower of Hanoi algorithm work?
- To move n disks from A to C, recursively move n − 1 disks from A to B, move the largest disk from A to C, then recursively move the n − 1 disks from B to C. The base case is a single disk, which is moved directly.
- Why is 2ⁿ − 1 the minimum number of moves?
- The largest disk has to move at least once, and for that all n − 1 smaller disks must sit on the third peg, both before and after. This forces T(n) ≥ 2 · T(n − 1) + 1 with T(1) = 1, and that recursion gives exactly 2ⁿ − 1.
- What can I do in the Hanoi app?
- You choose 3 to 8 disks, move them yourself or let the optimal solution run completely or move by move. The move counter, the minimum and the last move are shown live, and you can rotate the camera freely or pick views such as the top view.
Subject: Computer science
More from Computer science
- Ackermann function
- Elevator simulator
- Binary workshop
- Binary versus linear search
- The Collatz problem
- Inside a CPU
- Swap the inside
- One frame in 16 milliseconds — how a game engine renders an image (3D)
A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps