How to use the Tower of Hanoi solver
Pick the number of disks and the peg they should all end up on, then press Solve from here. With the usual starting tower on peg A the Tower of Hanoi solver shows the classic solution. If you are halfway through a game, copy your position first: tap a peg to lift its top disk, then tap another peg to drop it there. Only legal moves are allowed. Random position scatters the disks for a challenge. Press Play to watch the solution, or step through it; each move is listed as from-peg to to-peg.
The rules
- Move one disk at a time, always the top disk of a peg.
- Never put a larger disk on a smaller one.
- Get the whole stack onto the target peg.
How many moves does it take?
A tower of n disks needs exactly 2n − 1 moves: 7 for 3 disks, 31 for 5, 1,023 for 10. The reason: to move the largest disk you must first move the n − 1 smaller disks out of the way onto the spare peg, then move the largest disk, then move the n − 1 disks back on top of it. That is twice the moves for one disk fewer, plus one, which doubles at every size.
How the solver works from any position
The solver looks at the largest disk first. If it is already on the target peg, it can stay there forever, so the solver moves on to the next disk. Otherwise the largest disk has to move to the target peg once, and before that every smaller disk has to be on the third peg. So the job becomes: move the smaller disks to the third peg, move the large disk, then move the smaller disks onto the target. The same rule is applied to each smaller disk in turn.
This always gives the shortest possible solution. We checked it against a breadth-first search over every possible position with up to 7 disks (2,187 positions for 7 disks) for each of the three target pegs, and every solution was replayed under the rules.
Worked example: 3 disks
Disks 1 (small), 2 and 3 (large) start on A and go to C. The 7 moves are A to C, A to B, C to B (disks 1 and 2 are now parked on B), A to C (the large disk is home), B to A, B to C, A to C.
Tips for solving by hand
- The smallest disk moves on every other move, always around the pegs in the same direction: A, C, B, A, C, B for an odd number of disks going to C, and A, B, C for an even number.
- On the moves in between there is only ever one legal move that does not use the smallest disk; make it.
- Think of a tower of n disks as a tower of n − 1 disks plus the big one, and the solution becomes clear.
If you enjoy finding the shortest way, the 15 puzzle solver and the Lights Out solver also work from any position you enter.
Solver tested . Found a problem? Tell us.
Questions
What is the minimum number of moves for the Tower of Hanoi?
2n − 1 for n disks: 7 for 3 disks, 15 for 4, 31 for 5, 63 for 6, 127 for 7 and 1,023 for 10. From a mixed position it can be fewer; the solver gives the exact minimum.
Can I start from the middle of a game?
Yes. Set up your position by moving disks between pegs with taps, then press Solve from here. The solver finds the shortest way to finish from that position.
Does it matter which peg I move the tower to?
Not for the number of moves from the starting tower: B and C each take 2n − 1. Choose the target in the menu.
Is there a pattern to the moves?
Yes. The smallest disk moves every second move, cycling around the pegs in one direction, and every other move is the only legal move that does not involve it.