Tower of Hanoi

The Tower of Hanoi—also called the Tower of Brahma, Lucas’s Tower, or simply the pyramid puzzle—is a mathematical game played with three rods and a set of disks of different sizes that can be slid onto any rod. At the start, all disks are stacked on one rod in order of decreasing diameter, with the smallest on top, forming a cone-like shape. The goal is to move the entire stack to another rod, following three rules: only one disk can be moved at a time; each move takes the top disk from one stack and places it on top of another stack or an empty rod; and no disk may be placed on a smaller disk. With three disks, the puzzle can be solved in seven moves. In general, the minimum number of moves needed for n disks is 2ⁿ − 1. The puzzle was named after Hanoi, the capital of modern-day Vietnam.

The puzzle was invented by French mathematician Édouard Lucas, first presented in 1883 under the pseudonym “N. Claus (de Siam)” (an anagram of “Lucas d’Amiens”). It later appeared as a booklet in 1889 and in a posthumous volume of Lucas’s *Récréations mathématiques*. The accompanying instruction booklet claimed the game originated in Tonkin and told a legend: Brahmins at a temple in Benares had been moving the “Sacred Tower of Brahma”—64 golden disks—according to the same rules, and completing the tower would end the world. Many variations of this legend exist, often placing the temple in different locations (including Hanoi) or replacing the Brahmins with monks, and sometimes stating the tower was created at the beginning of the world or that only one move is allowed per day. At one move per second, solving the 64-disk puzzle would take 2⁶⁴ − 1 seconds—about 585 billion years, or roughly 42 times the current estimated age of the universe.

The puzzle can be played with any number of disks, though toy versions typically have 7 to 9. The minimum number of moves for n disks is 2ⁿ − 1.

One simple iterative solution alternates between moving the top piece and moving another piece. When moving the top piece, always shift it to the next position in the same direction: to the right if the starting number of disks is even, or to the left if odd. Imagine the rods arranged in a circle (or wrapping horizontally), so moving left from the first rod goes to the third, and moving right from the third goes to the first. Thus, moves 1, 3, 5, 7… move the top piece from A to B to C to A (for an even number of disks) or from A to C to B to A (for an odd number). When moving another piece, only one legal move exists, since no disk may be placed on the smallest, and only one of the other disks will fit. Following steps 1, 2, 1, 2… correctly solves the puzzle in the fewest moves.

Another iterative approach repeats this sequence until the goal is reached: move a disk between A and B (whichever is legal); then between A and C (whichever is legal); then between B and C (whichever is legal). With this order, the stack ends on peg B if the number of disks is odd, and on peg C if even. Reversing the order—A–C, A–B, B–C—makes the stack end on peg B for an even number of disks and peg C for an odd number.

The recursive solution breaks the problem into smaller sub-problems. Label the pegs A, B, C; let n be the total number of disks, numbered from 1 (smallest, topmost) to n (largest, bottom-most). To move m top disks from a source peg to a target peg using a spare peg, without violating the rules: first move m − 1 disks from the source to the spare (using the same procedure); then move disk m from the source to the target; finally move the m − 1 disks from the spare to the target (again using the same procedure). The base case is moving 0 disks—doing nothing.