Tower Of Hanoi formula minimum moves proof recursion steps and solved examples
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 with Formula and Strategy
1. What is the Tower of Hanoi problem?
The Tower of Hanoi is a mathematical puzzle where you move a stack of disks from one rod to another following specific rules. It consists of three rods and n disks of different sizes arranged in increasing size from top to bottom. The rules are:
- Only one disk can be moved at a time.
- A disk can only be placed on top of a larger disk.
- All disks must be moved to another rod while following these rules.
2. What is the formula for the minimum number of moves in Tower of Hanoi?
The minimum number of moves required to solve the Tower of Hanoi with n disks is 2n − 1. This formula gives the optimal solution under the puzzle rules. For example:
- If n = 1: 2¹ − 1 = 1 move
- If n = 2: 2² − 1 = 3 moves
- If n = 3: 2³ − 1 = 7 moves
3. How do you solve the Tower of Hanoi step by step?
The Tower of Hanoi is solved using a recursive strategy that breaks the problem into smaller subproblems. The steps are:
- Move the top n − 1 disks to the auxiliary rod.
- Move the largest disk to the destination rod.
- Move the n − 1 disks from the auxiliary rod to the destination rod.
4. Why is Tower of Hanoi considered a recursive problem?
Tower of Hanoi is considered recursive because its solution depends on solving a smaller version of the same problem. To move n disks, you must first move n − 1 disks. This creates the recurrence relation T(n) = 2T(n − 1) + 1, with base case T(1) = 1. This self-repeating structure makes it a classic example of recursion in mathematics and programming.
5. How many moves are required for 3 disks in Tower of Hanoi?
The minimum number of moves required for 3 disks is 7 moves. Using the formula 2n − 1:
- 2³ − 1 = 8 − 1 = 7
6. What is the recurrence relation for Tower of Hanoi?
The recurrence relation for the Tower of Hanoi is T(n) = 2T(n − 1) + 1. Here:
- T(n) represents the minimum number of moves for n disks.
- T(1) = 1 (base case).
7. What is the time complexity of the Tower of Hanoi algorithm?
The time complexity of the Tower of Hanoi algorithm is O(2n). This is because the number of moves required is 2n − 1, which grows exponentially with the number of disks. As n increases, the running time doubles approximately for each additional disk.
8. Can you give an example of Tower of Hanoi with 2 disks?
Yes, the Tower of Hanoi with 2 disks requires 3 moves. The steps are:
- Move the smaller disk to the auxiliary rod.
- Move the larger disk to the destination rod.
- Move the smaller disk onto the larger disk.
9. What are the rules of the Tower of Hanoi puzzle?
The Tower of Hanoi puzzle follows three main rules:
- Only one disk can be moved at a time.
- A larger disk cannot be placed on top of a smaller disk.
- All disks must be moved from the source rod to the destination rod.
10. What are the real-life applications of Tower of Hanoi?
The Tower of Hanoi demonstrates concepts used in recursion, algorithm design, and problem decomposition. Applications include:
- Teaching recursive programming in computer science.
- Understanding exponential growth and recurrence relations.
- Modeling data movement between stacks in computing systems.
