Tower of Hanoi Solver
Show the optimal Tower-of-Hanoi move sequence for N disks.
Overview
The Tower of Hanoi Solver displays the optimal move sequence for moving N disks from one peg to another, following the classic rules: move one disk at a time, never place a larger disk on a smaller one, and use the spare peg as needed. The solution is animated step by step so you can watch the recursive structure unfold.
Tower of Hanoi is a foundational example in computer science: it demonstrates recursion, exponential running time, and the surprising fact that the optimal solution has a closed-form length. For N disks the minimum number of moves is exactly 2^N - 1, so 3 disks take 7 moves, 10 disks take 1023, and 20 disks take just over a million.
How it works
The recursive solver follows a three-step structure. To move N disks from source to target using a spare peg: first move the top N-1 disks from source to spare, then move the largest disk from source to target, then move the N-1 disks from spare to target. The recursion bottoms out at N = 1 (move the single disk directly) and the move list builds up as the recursion unwinds.
The total move count satisfies T(N) = 2*T(N-1) + 1, which solves to T(N) = 2^N - 1. There's also an elegant iterative formulation based on binary numerals: at step k, the disk moved is the lowest set bit of k, and the direction follows a parity rule. The solver implements the recursive version because its move list reads more naturally for teaching purposes.
Examples
- 1 disk: 1 move (A -> C).
- 2 disks: 3 moves (A -> B, A -> C, B -> C).
- 3 disks: 7 moves following the classic recursive pattern.
- 64 disks: 18.4 quintillion moves — the legendary "end of the world" myth referenced in the puzzle's origin story.
FAQ
What's the minimum number of moves for N disks?
Exactly 2^N - 1. Three disks need 7 moves, four disks need 15, and so on.
Is there a faster algorithm?
No — 2^N - 1 is provably the lower bound. Every disk must move at least once, and the largest disk moves exactly once.
Does the solver visualise the moves?
Yes — the solution plays back step by step with the current peg state shown.
Can I solve from any starting configuration?
This implementation solves the classic problem with all disks on the source peg. Arbitrary starts would need a different algorithm.
Why is the solution recursive?
Because the problem has a natural recursive substructure — moving N disks reduces to two sub-problems of moving N-1 disks each.