Tower of Hanoi, the dance of minimum movement

Image by BehindTheTmuna retrieved from Unsplash

The Tower of Hanoi is one of the most iconic mathematical and computational puzzles in history. It was invented in 1883 by the French mathematician Édouard Lucas, who accompanied it with a mythical lore: the Legend of the Temple of Benares.

According to the story, the priests of the temple guard three diamond needles with 64 golden disks of varying sizes. Their task is to transfer the entire tower from the first needle to the third following strict, unalterable sacred rules. It is said that when the last move is completed, the temple will crumble and the end of the world will arrive.

Behind this mystical narrative lies a fascinating mathematical structure based on recursion, state combinatorics, and exponential growth.

Formal problem description

The game consists of 3 vertical rods (labeled A, B, and C) and a set of $n$ disks of decreasing diameters initially stacked on rod A (source), ordered from largest at the base to smallest at the top.

The goal is to transfer the entire stack of disks from the source rod A to the destination rod C, abiding by the following rules:

1. Only one disk can be moved at a time.
2. A move consists of taking the top disk from one of the rods and placing it on top of another rod or on an empty rod.
3. No disk may ever be placed on top of a smaller disk.

To analyze the properties of this game, we will focus on the case of $n = 3$ disks:

Do you know what is the minimum number of moves required to complete the game with 3 disks and how to perform the perfect sequence?

---

Challenge solution

To solve a tower of $n$ disks from rod A to C, the optimal strategy requires breaking the problem down into three recursive sub-tasks:

1. Move the top $n-1$ disks from A to the auxiliary rod B.
2. Move the remaining largest disk ($n$) directly from A to C.
3. Move the $n-1$ disks from the auxiliary rod B to the destination rod C.

This yields the recurrence relation for the minimum number of moves $T(n)$, allowing us to obtain the exact formula for minimum moves:

\[T(n) = 2^n - 1\]

For our case of $n = 3$ disks, the minimum number of moves is $2^3 - 1 = 7$ moves.

Below is the step-by-step animated sequence of the solution process:

Breakdown of the 7 moves:

1. Move disk 1 (small) from A $\rightarrow$ C
2. Move disk 2 (medium) from A $\rightarrow$ B
3. Move disk 1 (small) from C $\rightarrow$ B
4. Move disk 3 (large) from A $\rightarrow$ C
5. Move disk 1 (small) from B $\rightarrow$ A
6. Move disk 2 (medium) from B $\rightarrow$ C
7. Move disk 1 (small) from A $\rightarrow$ C

Mathematical curiosity: For the 64 disks in the legend, the priests would require $2^{64} - 1 \approx 1.84 \times 10^{19}$ moves. Even at a rate of one move per second without mistakes, it would take them approximately 585 billion years to finish (several times the current age of the Universe!).

The Tower of Hanoi can also be modeled using a binary optimization formulation. Do you dare to try modeling it?

Want to keep exploring the world of Operations Research? Discover more posts on the topic here.