Tower of Hanoi

This puzzle teaches you how to solve a difficult problem by breaking it down into a simpler version of itself. You might wonder why this matters beyond a game. It shows that even the most elegant, logical instructions can become incredibly slow or require an enormous amount of memory when the numbers get large. For example, moving just 64 disks requires more than 18 quintillion moves—more time than the universe has existed. Understanding this helps you judge whether a simple idea will work in the real world or if it will grind to a halt as the task grows.

Imagine three pegs standing on a table and a stack of six disks, each smaller than the one below it, all starting on the left peg. Your goal is to move the entire stack to the right peg. You can only move one disk at a time, and you can never place a larger disk on top of a smaller one. The middle peg serves as a temporary resting spot.

The secret is to stop thinking about all six disks at once. Instead, focus on the bottom-most disk—the largest one. It cannot move until every other disk is out of its way. So, your first major task is simply to get the top five disks onto the middle peg. Once that is done, you move the large bottom disk from the left peg to the right peg. Now, your second major task is to move those five disks from the middle peg to the right peg, on top of the large one.

Notice the pattern? To move a stack of five disks, you first need to get the top four out of the way, move the fifth disk, and then bring the four back. You keep splitting the problem in half until you reach a stack of just one disk. Moving one single disk is trivial—it’s already solved. Because you know how to solve the one-disk case, and you know that moving n-1 disks is just a smaller version of the same task, the entire six-disk puzzle resolves itself automatically. Each step relies on the success of the smaller steps beneath it.

Think of clearing a messy desk with a stack of twelve books. You want to move the stack from the left side of the desk to the right side without dropping any books or placing a heavy book on top of a thin one. The only way to reach the bottom book is to clear everything above it first. So, you pick up the top eleven books and set them safely on your lap (the spare peg). Now you can slide the bottom book to the right side of the desk. Finally, you take the eleven books from your lap and place them back onto the bottom book. The act of moving the eleven books from the desk to your lap is exactly the same problem as moving the twelve books—it’s just smaller. You repeat this until you are holding just one book, which you can easily move.

The Tower of Hanoi is a puzzle where you move a stack of disks between three pegs one at a time, never placing a larger disk on a smaller one; its solution works by moving the top n-1 disks to a spare peg, moving the largest disk to the goal, and then moving the n-1 disks from the spare peg to the goal, with the minimum number of moves required being two raised to the power of n minus one.

This concept introduces Recursion (solving a problem by applying the same solution to smaller versions of itself) and Complexity (how the amount of work or memory grows as the input size increases). It also connects to Depth-First Search with Backtracking (exploring one path as far as possible before stepping back, similar to how you must return from smaller sub-problems) and Stack Memory Behaviour (the system’s way of keeping track of these nested steps).