Pattern visualizer
Tower of Hanoi
To move n disks from A to C, first move the top n-1 disks from A to B (out of the way), then move the single biggest disk from A straight to C, then move those n-1 disks from B onto C. Each smaller sub-tower is solved the same recursive way, producing exactly 2^n - 1 moves. Animated on: n = 3 disks, peg A (source) → peg C (target), using peg B (auxiliary)..
Move n-1 out of the way, move the biggest, move n-1 back on top
time O(2^n)space O(n)step 1 / 9
321
[0][1]
[2]
line 1
3 disks stack on peg A (largest at bottom). 2^3 - 1 = 7 moves will move them all to peg C.
Pseudocode
1FUNCTION hanoi(n, from, aux, to):2 IF n is 0: RETURN3 hanoi(n-1, from, to, aux) (move the top n-1 disks out of the way)4 move disk n from the source peg to the target peg5 hanoi(n-1, aux, from, to) (move those n-1 disks onto the target)6 (total moves = 2^n - 1)
← / → step · space play · Home restart