The tower of Hanoi (commonly also known as the "towers of Hanoi"), is a puzzle invented by E. Lucas in 1883. 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."
Given a stack of 
disks arranged from largest on the bottom to smallest on top placed on a rod, together
with two empty rods, the tower of Hanoi puzzle asks for the minimum number of moves
required to move the stack from one rod to another, where moves are allowed only
if they place smaller disks on top of larger disks. The puzzle with 
pegs and 
disks is sometimes known as Reve's puzzle.
The problem is isomorphic to finding a Hamiltonian path on an 
-hypercube (Gardner 1957, 1959).
Given three rods and 
disks, the sequence 
giving the number of the disk (
to 
) to be moved at the 
th step is given by the remarkably simple recursive procedure
of starting with the list 
for a single disk, and recursively computing
 |
(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 is 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. Even more amazingly,
the number of disks moved after the 
th step is the same as the element which needs to be added
or deleted in the 
th
addend of the Ryser formula
(Gardner 1988, 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)
|
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. While algorithms are known for transferring disks on four rods, none has been proved minimal.
A Hanoi graph can be constructed whose graph vertices correspond to legal configurations of 
towers, 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, ... disk on four rods are given by 1, 3, 5, 9, 13, 17,
25, 33, ... (OEIS A007664). It is conjectured
that this sequence is given by the recurrence
 |
(4)
|
with 
and 
the positive floor integer solution to
 |
(5)
|
i.e.,
 |
(6)
|
This would then given the explicit formula
![s_n=1+[n-1/2x(x-1)-1]2^x.](/images/equations/TowerofHanoi/NumberedEquation7.svg) |
(7)
|
Wolfram (2022) analyzes the tower of Hanoi as a multicomputational process, including through the use of branchial graphs.
-Regular Sequences." Theoret. Comput. Sci. 98,
163-197, 1992.Allouche, J.-P. "Note on the Cyclic Towers of Hanoi."
Theor. Comput. Sci. 123, 3-7, 1994.Bogomolny, A. "Towers
of Hanoi." 
Poole, D. G. "Towers of Hanoi Package."