Tower of Hanoi

The Tower of Hanoi looks simple, but it is a brilliant exercise in forward-thinking and strategy. The goal is to move the entire stack of discs from the starting peg to the destination peg, using a third peg as a temporary holding spot.

Rules

You can move the discs around as much as you want, but you must strictly follow these three rules on every single turn:

One Disc at a Time: You can only move the top disc of any stack. You cannot grab a handful of discs or pull one from the middle.
Top Disc Only: A move consists of taking the top disc from one peg and sliding it onto another peg.
No Big on Small: You can never place a larger disc on top of a smaller disc. A smaller disc must always rest on a larger one (or directly on the empty board).

Strategy

To successfully move the stack, you have to break the problem down into smaller chunks. The sequence below walks you through the logical mindset needed to solve the puzzle, whether you have 3 discs or 30.

Clear the path for the base: Before you can move the largest bottom disc to your goal peg, you must move every single disc above it out of the way. If you have a 3-disc tower, your immediate goal is to get the top 2 discs over to the temporary middle peg.
Move the anchor: Once the largest bottom disc is completely exposed and your goal peg is empty, move that largest disc directly to the destination peg. It will now act as the solid foundation for the rest of your tower.
Rebuild the pyramid: Now, treat the remaining smaller discs as a brand-new, slightly smaller tower. Move them from their temporary holding peg back onto the top of the largest disc on the destination peg, maintaining the strict "small-on-large" rule.

History

The Tower of Hanoi is a staple of computer science lectures and math textbooks, renowned for being the ultimate demonstration of mathematical induction and recursion. Yet, its journey began not in a research lab, but as a clever 19th-century marketing stunt wrapped in an exotic mythological legend.

The French Mathematician's Stunt (1883)

The puzzle was invented in 1883 by the very same French mathematician who popularized Dots and Boxes: Édouard Lucas.

To sell the puzzle to the Parisian public, Lucas published it under an anagrammatic pseudonym, N. Claus de Siam (supposedly a professor from the College of Li-Sou-Stian, which was itself an anagram for Lycée Saint-Louis where he taught).

He packaged the game with an elaborate, fabricated backstory to give it an air of ancient Eastern mysticism.

The Legend of the Doomsday Clock

According to Lucas's marketing lore, there was an ancient temple in India (often associated with Kashi Vishwanath or Varanasi) containing a large room with three time-worn needles. On one of these needles, God placed 64 golden discs of decreasing size at the creation of the world.

The priests of the temple worked night and day, moving the discs according to the strict immutable rules of Brahma:

Only one disc can be moved at a time.
Each move consists of taking the upper disc from one stack and placing it on top of another stack.
No larger disc may be placed on top of a smaller disc.

The legend claimed that when the priests successfully transferred all 64 discs from the first needle to the third, the temple would crumble into dust, and the world would end.

The Math: Why We Are Safe

Thankfully, the "Doomsday Clock" of Hanoi isn't ticking down anytime soon. Lucas designed the puzzle to elegantly express a geometric progression.

The minimum number of moves required to solve a tower with n discs is expressed by the formula: 2ⁿ-1

If the priests have 64 discs, the minimum number of moves required is 2⁶⁴−1, which equals exactly 18,446,744,073,709,551,615 moves.

Even if the priests were superhuman and moved one massive golden disc perfectly every single second without making a single mistake, it would take them 584.5 billion years to complete the task. Given that our current universe is only about 13.8 billion years old, we have plenty of time left.

The Computer Science Legacy

In the mid-20th century, as the field of computer science was born, the Tower of Hanoi found its true modern calling.

When programming languages began utilizing recursion—a programming technique where a function calls itself to break down a problem into smaller, identical sub-problems—the Tower of Hanoi became the perfect teaching tool. To solve a tower of n discs, a computer program simply needs to:

Move n−1 discs to an auxiliary peg.
Move the largest single disc to the destination peg.
Move the n−1 discs from the auxiliary peg to the destination peg.

Today, it remains one of the most widely implemented coding exercises in the world, proving that a toy invented to amuse 19th-century Parisians holds the fundamental DNA of modern computing.