Tower of Hanoi

The tower of Hanoi (commonly also known as the "towers of Hanoi") is a puzzle invented by E. Lucas in 1883 (Bousch 2014). It is also known as the Tower of Brahma puzzle and appeared as an intelligence test for apes in the film Rise of the Planet of the Apes (2011) under the name "Lucas Tower."

For a positive integer , begin with a stack of disks arranged from largest on the bottom to smallest on top on one rod, together with two empty rods. The tower of Hanoi puzzle asks for the minimum number of moves required to move the stack to another rod. Each move transfers the top disk of one rod to an empty rod or onto a larger disk. The puzzle with four pegs and disks is sometimes known as Reve's puzzle.

The sequence of disk labels in the standard optimal three-rod solution corresponds to the coordinates changed along the binary reflected Gray code, a Hamiltonian path on an -hypercube (Gardner 1957, 1959).

Given three rods and disks, the sequence gives the label of the disk ( to ) moved at the th step. Starting with , it is defined for by concatenating , the one-element list , and , written as

(1)

For the first few values of , this gives the sequences shown in the following table. A solution of the three-rod four-disk problem is illustrated above.

1	1
2	1, 2, 1
3	1, 2, 1, 3, 1, 2, 1
4	1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1

As the number of disks increases (again for three rods), an infinite sequence is obtained, the first few terms of which are illustrated in the table above (OEIS A001511). Amazingly, this is exactly the binary carry sequence plus one. The label of the disk moved at the th step is also the element added or deleted at the th transition of the binary reflected Gray code ordering of the subsets in the Ryser formula (Gardner 1988b, Vardi 1991). A simple method for hand-solving uses disks painted with alternating colors. No two disks of the same color are ever placed atop each other, and no disk is moved twice in a row (P. Tokarczuk, pers. comm., Jun. 23, 2004).

As a result of the above procedure, the number of moves required to solve the puzzle of disks on three rods is given by the recurrence relation

(2)

for , with . Solving gives

(3)

i.e., the Mersenne numbers.

For three rods, the proof that the above solution is minimal can be achieved using the Lucas correspondence which relates Pascal's triangle to the Hanoi graph. For four rods, Bousch (2014) proved that the algorithm of Frame (1941) and Stewart (1941) is minimal. Its optimality for five or more rods remains conjectural in general (Hinz and Parisse 2026).

A Hanoi graph can be constructed whose graph vertices correspond to legal configurations of disks on three rods, where the graph vertices are adjacent if the corresponding configurations can be obtained by a legal move. The puzzle itself can be solved using a binary Gray code.

Poole (1994) and Rangel-Mondragón give Wolfram Language routines for solving the Hanoi tower problem. Poole's algorithm works for an arbitrary disk configuration, and provides the solution in the fewest possible moves.

The minimal numbers of moves required to order , 2, ... disks on four rods are given by 1, 3, 5, 9, 13, 17, 25, 33, ... (OEIS A007664). For , this sequence satisfies the recurrence relation

(4)

with . For , the parameter is the nonnegative integer satisfying , where is the floor function. The explicit formula is

(5)

Wolfram (2022) analyzes the tower of Hanoi as a multicomputational process, including through the use of branchial graphs.