Step-by-Step Tower of Hanoi Algorithm for Students
The Tower of Hanoi (also known as the Tower of Brahma) is a mathematical game or puzzle invented by E. Lucas in 1883. The Tower of Hanoi games consists of pegs arranged in a stand, and 8 circular discs of wood or cardboard each of which has a hole in the middle, so that pegs can be easily put through it.
The discs placed on the pegs are of different sizes, and initially, all the discs are placed on one peg so that the biggest disc is at the bottom, and the smallest disc is at the top. This arrangement of discs in the Tower of Hanoi game is known as a tower.
Tower of Hanoi Problem
There are 3 pegs in the Tower of Hanoi problem and a disc of different size. Each disc has a hole in the middle so that any peg can be easily fit. At the beginning of the Tower of Hanoi game, all n discs are on the first peg, arranged such that the largest disc is at the top, and the smallest disc is at the bottom.
The goal of the Tower of Hanoi game is to move all the discs on the third peg, in a similar order, that is the smallest disc on the top, and in an increasing order towards the bottom.
But, there are some restrictions to how the discs are moved (which makes the Tower of Hanoi problem non-trivial).
The only type of move that is allowed is to grab one disc from the top of one peg and drop it into another peg. That implies that you cannot drop several pegs at one time.
The larger disc cannot lie above a smaller disc.
Tower of Hanoi Solution
The Tower of Hanoi game can be played with any number of discs, although many toy versions have around 7 to 9 discs. The minimum number of moves needed to solve a puzzle is 2ⁿ - 1, where n is the total number of discs. With the Tower of Hanoi 4 discs, the Tower of Hanoi puzzle can be solved with 15 moves (2⁴ - 1 = 15).
Tower of Hanoi Algorithm
To understand the Tower of Hanoi algorithm, we will first learn how to solve the Tower of Hanoi problem with a smaller number of discs, say 1 or 2, we will mark the three rods with source, destination, and auxiliary.
But if we have 2 discs,
First, we will move the smaller (top) disc from the peg source to the peg auxiliary.
Then we will move the larger (bottom) disc from the peg source to the peg destination.
Finally, we will move the smaller disc (top) from the peg auxiliary to the peg destination.
With this, we can easily design an algorithm for the Tower of Hanoi algorithm with more than two disks. We will divide the stack of disks into two different parts.
The larger (nth) disc in one part
And, all other (n-1) disks in the second part.
Our goal is to move disk n from peg source to peg destination and then place all other (n - 1) disks above it. Following are the steps to move 2 discs.
Step 1 − Move (n -1) disks from peg source to peg auxiliary.
Step 2 − Move larger (nth) disk from peg source to peg destination.
Step 3 − Move n -1 disks from the peg auxiliary to the peg destination.
Tower of Hanoi Recursion
Here, we will learn to solve the Tower of Hanoi puzzle using the Tower of Hanoi recursion method with an algorithm.
Let's take an example of the Tower of Hanoi with 2 discs:
In the diagram below, disc 1 is placed on top of disc 2 in peg 1. The aim is to move both the disc in the peg B recursively.
Here are the steps to move both the disc to peg B recursively
Here are the steps to move both the disc to peg B recursively.
The first step is to move Disc 1 from peg A to peg C.
The second step is to move Disc 2 from peg A to peg B
At last, move Disc 1 from peg C to peg B.
This Tower of Hanoi solutions with 2 discs takes 3 steps.
Tower of Hanoi Recursion Algorithm can be driven as follows:
START
Procedure Hanoi(disk, A, B, C)
If Disk = 1, Then,
Move Disk from peg A to peg B
ELSE
Hanoi(disk - 1, A, C, B) Step 1
Move disk from peg A to peg B Step 2
Hanoi(disk - 1, C, B, A) Step 3
END IF
END Procedure
STOP
Example of Tower of Hanoi With Solution
1. How Do You Solve the Tower of Hanoi With 3 Discs?
Solution:
With 3 discs, the Tower of Hanoi problem can be solved in 7 steps. The minimum number of moves required to solve a Tower of Hanoi puzzles is 2ⁿ - 1, where n is the total number of discs
If we have 3 discs - 1, 2, and 3 discs stacked in peg A, then the following are the steps to solve the Tower of Hanoi problem recursively with 3 discs.
Let,
Disc 1 = Red Color
Disc 2 = White Color
Disc 3 = Green Color
1. The first step is to move Disc 1 from peg A to peg C
2. The second step is to move Disc 2 from peg A to peg B.
3. The third step is to move Disc 1 from peg C to peg B
4. The fourth step is to move Disc 3 from peg A to peg C
5. The fifth step is to move Disc 1 from peg B to peg A
6. The sixth step is to move Disc 2 from peg B to peg C
7. The seventh step is to move Disc 1 from peg A to peg C
2. How Do You Solve the Tower of Hanoi With 4 Discs?
Solution:
With 4 discs, the Tower of Hanoi problem can be solved in 15 steps. The minimum number of moves required to solve a Tower of Hanoi puzzles is 2ⁿ - 1, where n is the total number of discs
If we have 4 discs - 1, 2, 3, and 4 discs stacked in Rod A, then the following are the steps to solve the Tower of Hanoi problem from source Rod A to a destination Rod C recursively with 4 discs.
Rod A: [1,2,3,4] Rod B: [ ] Rod C: [ ]
Steps:
Step 1: Move Disk 1 from Rod A to Rod B
Rod A: [4, 3, 2] Rod B: [1] Rod C: [ ]
Step 2: Move disk 2 from Rod A to Rod C
Rod A: [4, 3] Rod B: [1] Rod C: [2]
Step 3: Move disk 1 from Rod B to Rod C
Rod A: [4, 3] Rod B: [ ] Rod C: [2, 1]
Step 4: Move disk 3 from Rod A to Rod B
Rod A: [4] Rod B: [3] Rod C: [2, 1]
Step 5: Move disk 1 from RodC to Rod A
Rod A: [4, 1] Rod B: [3] Rod C: [2]
Step 6: Move disk 2 from RodC to Rod B
Rod A: [4, 1] Rod B: [3, 2] Rod C: [ ]
Step 7: Move disk 1 from Rod A to Peg B
Rod A: [4] Rod B: [3, 2, 1] Rod C: [ ]
Step 8: Move disk 4 from Rod A to Rod C
Rod A: [ ] Rod B: [3, 2, 1] Rod C: [4]
Step 9: Move disk 1 from Rod B to Rod C
Rod A: [ ] Rod B: [3, 2] Rod C: [4, 1]
Step 10: Move disk 2 from Rod B to Rod A
Rod A: [2] Rod B: [3] Rod C: [4, 1]
Step 11: Move disk 1 from RodC to Rod A
Rod A: [2, 1] Rod B: [3] Rod C: [4]
Step 12: Move disk 3 from Rod B to Rod C
Rod A: [2, 1] Rod B: [ ] Rod C: [4, 3]
Step 13: Move disk 1 from Rod A to Rod B
Rod A: [2] Rod B: [1] Rod C: [4, 3]
Step 14: Move disk 2 from Rod A to Rod C
Rod A: [ ] Rod B: [1] Rod C: [4, 3, 2]
Step 15: Move disk 1 from Rod B to Rod C
Rod A: [ ] Rod B: [ ] Rod C: [4, 3, 2, 1]
FAQs on Tower of Hanoi Explained: Rules, Algorithm & Solutions
1. What are the three fundamental rules for solving the Tower of Hanoi puzzle?
The Tower of Hanoi puzzle is governed by three simple rules that must be followed to reach the solution:
Only one disk can be moved at a time.
Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
No larger disk may be placed on top of a smaller disk.
2. What is the Tower of Hanoi problem, and what type of algorithm is typically used to solve it?
The Tower of Hanoi is a mathematical puzzle that involves moving a stack of disks of different sizes from a source peg to a destination peg using an auxiliary peg, adhering to specific rules. It is a classic problem in computer science, and its most elegant solution is achieved using a recursive algorithm. This approach works by breaking the problem down into smaller, self-similar sub-problems until a simple base case is reached.
3. How do you solve the Tower of Hanoi puzzle for 3 disks as an example?
To solve the Tower of Hanoi for 3 disks, a minimum of 23 - 1 = 7 moves are required. Assuming the pegs are A (source), B (auxiliary), and C (destination), the steps are:
Move disk 1 from A to C.
Move disk 2 from A to B.
Move disk 1 from C to B.
Move disk 3 from A to C.
Move disk 1 from B to A.
Move disk 2 from B to C.
Move disk 1 from A to C.
4. Why is the Tower of Hanoi considered a classic example of recursion?
The Tower of Hanoi is a perfect illustration of recursion because the solution to moving 'n' disks inherently depends on the solution to moving 'n-1' disks. The process is: 1. Recursively move n-1 disks from the source to the auxiliary peg. 2. Move the largest disk (n) from the source to the destination. 3. Recursively move the n-1 disks from the auxiliary to the destination peg. This principle of breaking a problem into smaller, identical instances of itself is the core concept of recursion.
5. What is the formula to calculate the minimum number of moves in the Tower of Hanoi?
The formula to determine the minimum number of moves required to solve the Tower of Hanoi puzzle is 2n - 1, where 'n' is the number of disks. For example, for 3 disks, it takes 23 - 1 = 7 moves, and for 4 disks, it would take 24 - 1 = 15 moves. The number of moves grows exponentially with each added disk.
6. Can the Tower of Hanoi be solved without using recursion?
Yes, the Tower of Hanoi can be solved using an iterative approach, which does not involve recursive function calls. The iterative solution is often implemented using stacks to keep track of the disks and moves. While recursion provides a more intuitive and simpler-to-code solution, an iterative method can be more memory-efficient for a very large number of disks, as it avoids the overhead of a deep function call stack.
7. What are some important real-world applications or analogies for the Tower of Hanoi algorithm?
While a direct one-to-one application is rare, the principles of the Tower of Hanoi algorithm have several important applications and uses in computer science and beyond:
Teaching Recursion: It is a primary tool for teaching students the concept of recursive programming.
Psychological Research: It is used by neuropsychologists to evaluate and test problem-solving and procedural memory skills in patients.
Data Backup Schemes: The logic is analogous to sophisticated data backup rotation schemes (like the Grandfather-father-son backup method) to manage and cycle through backup media efficiently.
