Tower of Hanoi
Generate the optimal move sequence for a Tower of Hanoi puzzle and watch it solve.
The Tower of Hanoi moves a stack of disks from one peg to another, one disk at a time, never placing a larger disk on a smaller one. Choose how many disks you have and how the pegs are labeled, then generate the shortest move sequence. The minimum number of moves is always 2 to the power of N, minus 1.
Case
Filter
Whitespace
Find & Replace
Group
How it works
To move a stack of N disks from the source peg to the target peg, first move the top N minus 1 disks out of the way onto the auxiliary peg, then move the single largest disk from the source to the target, then move those N minus 1 disks from the auxiliary peg onto the target. Each of those smaller transfers follows the same rule, so the whole solution builds up from the simplest case of moving one disk.
This pattern produces the shortest possible solution. For N disks it always takes exactly 2 to the power of N, minus 1 moves, and every move is the only sensible choice at that point. The move list below numbers each step and the animation applies them in order, lifting a disk off one peg and dropping it onto another.