Tower of Hanoi

The Tower of Hanoi, also known as the problem of Benares Temple, Tower of Brahma, Lucas's Tower, or simply the pyramid puzzle, is a mathematical game. It uses three rods and several disks of different sizes that can slide onto any rod. At the start, the disks are stacked on one rod in order of decreasing size, with the smallest on top, forming a cone shape. The goal is to move the entire stack to another rod, following these 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 one. With three disks, the puzzle can be solved in seven moves. The minimum number of moves needed for n disks is 2ⁿ − 1. The puzzle was named after Hanoi, the capital of modern-day Vietnam.

French mathematician Édouard Lucas invented the puzzle, first presenting it in 1883 as a game discovered by "N. Claus (de Siam)"—an anagram of "Lucas d'Amiens." He later published it as a booklet in 1889 and in a posthumous volume of his *Récréations mathématiques*. The accompanying booklet described the game's supposed origins in Tonkin and a legend: Brahmins at a temple in Benares have been moving the "Sacred Tower of Brahma," made of 64 golden disks, under the same rules, and completing it would end the world. Many variations of this legend exist, often changing the setting to a monastery or different locations like Hanoi, and involving monks or priests. At one move per second, solving the 64-disk puzzle would take 2⁶⁴ − 1 seconds, or about 585 billion years—roughly 42 times the current estimated age of the universe.

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

An iterative solution alternates between moving the top piece and moving another piece. For the top piece, always move 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 on a circle so that moving left from the first rod goes to the third, and moving right from the third goes to the first. So moves 1, 3, 5, 7... shift the top piece from A to B to C to A (for an even number of disks) or A to C to B to A (for an odd number). When moving another piece, only one legal move exists, since no disk can go onto the smallest, and only one other move fits. Following steps 1, 2, 1, 2... correctly solves the puzzle in the fewest moves.

A simpler iterative approach repeats these steps until the goal is reached: move a disk between pegs A and B (whichever is legal); then between A and C; then between B and C. The stack ends on peg B if the number of disks is odd, and on peg C if even. Changing the order—moving between A and C first, then A and B, then B and 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; number them from 1 (smallest, top) to n (largest, bottom). To move m disks from a source peg to a target peg using a spare peg: move m − 1 disks from the source to the spare (using the same procedure); move disk m from the source to the target; then move the m − 1 disks from the spare to the target (again using the same procedure). The base case is moving 0 disks.