About Tower of Hanoi
Move the whole tower from the left needle to the right one. Only one disc moves at a time, always the top disc of a pile, and a disc may never sit on a smaller one. Pick 3 to 10 discs in the bar at the top.
PLAY: drag a disc to another needle, or click one needle and then another, or press 1, 2, 3 (and 4) for the same thing. A move that breaks the rules is refused and the page says why. UNDO (or Ctrl+Z) takes a move back; HINT names the best next move; tick Time it for a clock that starts with your first move.
SOLUTION plays the shortest solution. STEP (or the arrow keys) goes one move at a time, PLAY (or Space) runs it at the speed you set, and the Move slider or box jumps straight to any move. Under it are the calls the recursion is in the middle of, outermost first: each one moves a smaller tower, and the green step is the one under way.
ANY POSITION works from wherever the discs are now: how far you are from the finished tower, the next best move, FINISH IT to watch the rest, SCRAMBLE for a random position. With three needles every position is a dot on a map, your position lit; click a dot to go there.
Pegs gives a fourth needle; Clockwise only lets discs move one way round, A → B → C → A.
THE STORY
The puzzle was invented by the French mathematician Édouard Lucas and sold as a toy in 1883, under the name of "Professor N. Claus (de Siam)" of the college of "Li-Sou-Stian": anagrams of Lucas d'Amiens and of Saint-Louis, the lycée in Paris where he taught. The box called it a puzzle brought back from Tonkin, in what is now Vietnam, hence Hanoi. The famous legend, of a temple where priests move 64 golden discs and the world ends when they finish, was already in the leaflet that came with it; a newspaper piece by Henri de Parville at the end of 1883 gave the telling with three diamond needles. It was a story to sell the puzzle, not an old tradition.
The world is safe. 64 discs need 264 − 1 = 18,446,744,073,709,551,615 moves; at one move a second, with no mistakes, that is about 584.5 billion years, some 42 times the present age of the universe.
With four needles the puzzle was set by Henry Dudeney in 1907 as "The Reve's Puzzle", with cheeses on stools. In 1941 J. S. Frame and B. M. Stewart each gave the same method: put a smaller tower aside using all four needles, move the rest with three, bring the small tower back, choosing the split that gives fewest moves. Nobody could prove it was the best possible until Thierry Bousch did so in 2014; for five or more needles it is still unproved. The clockwise-only puzzle was solved by Michael Atkinson in 1981.
HOW IT WORKS
The solution is recursion. To move n discs from A to C: move the top n − 1 out of the way to B, move the biggest disc to C, then move the n − 1 from B onto it. Each "move n − 1" is the same job, one size smaller, until a single disc just moves. That takes 2n − 1 moves, and no solution is shorter: the biggest disc must move at least once, and before it can, everything else has to be stacked on the third needle.
The moves also follow a pattern you can read straight off a binary number. In move k, the disc that moves is one more than the number of 0s at the end of k written in binary (so disc 1 moves every other time); it is the same bit that changes in the k-th step of a Gray code, where neighbouring numbers differ in one bit. Where it goes is (k AND k − 1) mod 3 to ((k OR k − 1) + 1) mod 3, with the needles numbered A 0, B 1, C 2 for an odd number of discs and A 0, C 1, B 2 for an even one. So the page finds move k, and the position after it, without playing the moves before it.
From a muddled position, look at the discs from the biggest down. The biggest disc not yet on its target has to get there, so everything smaller must first gather on the third needle; then the smaller tower follows. That gives the shortest way for three needles. For four needles and clockwise-only, the page searches outwards from the finished tower through every position (up to a million of them) and follows the distances down.
The map: the biggest disc decides which of three big triangles a position is in, the next disc which smaller triangle inside that, and so on. Lines join positions one move apart. Moving the smallest disc goes round a tiny triangle; the big disc moves only along the few long links between the big triangles. As the number of discs grows the map becomes the Sierpiński triangle, and the solution is its bottom edge.
FURTHER WATCHING AND READING