Towers of Hanoi
Move the whole tower from the left peg to the right peg. One disk at a time, and never a bigger disk on top of a smaller one. Click a peg to lift its top disk, then click where to drop it. Then try to do it in the fewest moves.
What's going on
To move a tower of 4 you must first move the top 3 out of the way, then move the big disk, then move the 3 back on top. So moves(4) = 2 × moves(3) + 1. The same sentence works for any size: each extra disk doubles the work and adds one. Starting from moves(1) = 1 you get 1, 3, 7, 15, 31, 63, 127, 255. That is 2n − 1, always one short of a power of two.
The Solve button follows exactly that plan, calling itself on smaller towers. A rule that refers to a smaller copy of itself is called recursion, and it is one of the main ideas in computer programming.
The legend says monks are moving a tower of 64 golden disks, and the world ends when they finish. At one move per second that takes 264 − 1 seconds, about 585 billion years. No hurry.
Sheet: The tower that takes forever.