How to use the tower of hanoi move generator
- Enter the number of disks, from 1 to 200.
- Choose 3 pegs or 4 pegs, and your pace in moves per second.
- Read the fewest moves for both numbers of pegs and how long it takes at your pace.
- For 3 pegs and up to 8 disks, follow the full numbered move list.
Formula
Three pegs: T(n) = 2 T(n - 1) + 1, so T(n) = 2^n - 1
Four pegs (Frame-Stewart): T4(n) = min over k of 2 T4(k) + 2^(n - k) - 1
First move with 3 pegs: the smallest disk goes to the target peg if n is odd, to the spare peg if n is even
Time = moves / moves per second
Move k disks to a spare peg using all four pegs, move the other n - k disks with three pegs, then move the k disks again. The best split k is shown for four pegs.
Small and enormous towers
Three disks take 2^3 - 1 = 7 moves with three pegs, and 5 with four pegs. Eight disks take 255 moves, which is 4 minutes 15 seconds at one move per second, and 33 moves with four pegs. Ten disks need 1,023 moves with three pegs, 17 minutes 3 seconds, or 49 moves with four pegs (split at k = 6), which is 49 seconds.
The legendary 64 disk tower needs 2^64 - 1 = 18,446,744,073,709,551,615 moves with three pegs, about 584.5 billion years at one move per second. With four pegs the count falls to 18,433 moves, about 5 hours.
The recursion behind the puzzle
To move a tower of n disks you must move the top n - 1 out of the way, move the largest disk once, and then move the n - 1 back on top. That gives the doubling rule, and the count grows so fast that 64 disks outlast the age of the universe many times over. The recursion is a standard example of how a hard-looking problem splits into the same problem on a smaller size.
Related tools include the Nim game solver, Pascal's triangle, the Fibonacci calculator and the Collatz sequence calculator.
More pegs, fewer moves
An extra peg gives much more room to park disks, so the number of moves drops steeply, from 2^n - 1 to a count that grows far more slowly. The Frame-Stewart numbers 1, 3, 5, 9, 13, 17, 25, 33, 41, 49, 65 and so on count the fewest moves for four pegs, and this was proved to be optimal for four pegs in 2014. For more pegs the same rule is believed, but not proved, to be best.
Assumptions and limits
- Disks are moved one at a time, only the top disk of a peg moves, and no disk may sit on a smaller one.
- The move list is shown for three pegs and up to 8 disks. Counts are exact for up to 200 disks.
- A year is 365.25 days in the time estimate. Time is moves divided by the pace you enter.
- Four-peg move lists are not produced, only the counts and the best split.
Frequently asked questions
How many moves does the Tower of Hanoi take?
With three pegs, 2^n - 1 moves for n disks: 7 for three disks, 255 for eight and 1,023 for ten. This is the fewest possible.
How long would 64 disks take?
At one move per second the 64 disk puzzle would take about 584.5 billion years with three pegs, over 40 times the age of the universe.
What is the Frame-Stewart rule?
It is a recursive way to solve the puzzle with four or more pegs: move some of the top disks to a spare peg with all pegs available, move the rest with one peg fewer, then move the first group back. The best split gives the Frame-Stewart numbers.
Which peg does the smallest disk move to first?
With three pegs, if the number of disks is odd the first move goes to the target peg, and if it is even it goes to the spare peg. After that the smallest disk keeps moving in the same direction every other move.