Table of Contents
History
The Tower of Hanoi was invented by a French mathematician named Édouard Lucas in the 19th century. Lucas introduced the puzzle in 1883 and named it after the Tower of Hanoi, a famous temple in Vietnam.
The Tower of Hanoi puzzle gained attention and popularity due to its intriguing mathematical properties. It is often used as an exercise or example in recursion and algorithm design. The puzzle demonstrates the concept of divide and conquer and is frequently used to explain recursion to computer science students.
Tower of Hanoi
Tower of Hanoi is a mathematical puzzle based on the pillars/towers (also called Peg) and disks. It consists of three pillars and one or more disks (i.e., n disks). At first, every disk is set to one tower in descending order.
The names of the first, second, and third pillars are Source, Auxiliary, and Destination, respectively.
Tower of Hanoi – Problem/Goal?
The problem with the Tower of Hanoi is transferring all disks from the source pillar to the destination pillar in the same pattern of descending order.
Rules of Tower of Hanoi – Problem
The goal of the Tower of Hanoi is to transfer all the disks from the source to the destination pillar without breaking the rule.
- Only one disk can be moved among the towers at any given time.
- Just the “top” disk can be taken out.
- No large disk can place over a small disk.
Note: The minimal number of moves required to solve a Tower of Hanoi puzzle is 2n − 1, where n is the number of disks.
Note: The minimal number of moves required to solve a Tower of Hanoi puzzle is 2n − 1, where n is the number of disks.
Algorithm – TOH
To write an algorithm for Tower of Hanoi, first, we need to learn how to solve this problem with fewer disks, say → 1 or 2. We mark three towers with name, source, destination, and aux (only to help move the disks). If we have only one disk, it can easily be moved from the source to the destination peg.
If we have two disks −
First, we move the smaller (top) disk to the auxiliary peg.
Then, we move the larger (bottom) disk to the destination peg.
And finally, we move the smaller disk from the auxiliary to the destination peg.
So now, we are in a position to design an algorithm for the Tower of Hanoi with more than two disks. We divide the disks into two parts. The largest disk (nth disk) is in one part, and all other (n-1) disks are in the second part.
We aim to move disk n from source to destination and then put all other disks onto it.
The steps to follow are as follows –
Step 1 − Move n-1 disks from source to auxiliary.
Step 2 − Move the nth disk from source to destination.
Step 3 − Move n-1 disks from auxiliary to destination.
Simpler statement of iterative solution
For an even number of disks:
- Make the legal move between pegs A and B (in either direction),
- Make the legal move between pegs A and C (in either direction),
- Make the legal move between pegs B and C (in either direction),
- Repeat until complete.
For an odd number of disks:
- Make the legal move between pegs A and C (in either direction),
- Make the legal move between pegs A and B (in either direction),
- Make the legal move between pegs B and C (in either direction),
- Repeat until complete.
After each move, check if the C peg is complete. In each case, a total of 2n − 1 moves are made.
Conclusion
It can be concluded that the puzzle is a fascinating example of recursive problem-solving and algorithmic thinking. The article likely explains the problem statement, the rules for moving the disks, and various strategies and algorithms to solve it efficiently.
The article may have highlighted different approaches to solving the Tower of Hanoi puzzle, such as the classic recursive solution, which breaks down the problem into smaller subproblems. It may have also discussed iterative or non-recursive solutions that utilize different data structures and algorithms to achieve the same goal.
