Tower of Hanoi Problem:- In this post, we discuss the Tower of Hanoi Problem. The Tower of Hanoi problem has a historical basis in the ritual of ancient Vietnam.
Tower of Hanoi Problem
The problem can be described as follows: Suppose there are three pillars A, B and C. There are N discs of decreasing size so that no two discs are of the same size. Initially, all the discs are stacked on one pillar in their decreasing order of size. Let this pillar be A. The other two pillars are empty. The problem is to move all the discs from one pillar to another using the third pillar as an auxiliary so that
- Only one disc may be moved at a time.
- A disc may be moved from any pillar to another pillar.
- At no time can a larger disc be placed on a smaller disc.
The figure represents the initial and final stages of the tower of Hanoi problem for N=5 discs.
Tower of Hanoi problem with 5 discs Figure
The solution of this problem can be stated recursively as follows:
Move N discs from pillar A to C via the pillar B means
- Moving the first (N-1) discs from pillar A to B.
- Moving the disc from pillar A to C.
- Moving all (N-1) discs from pillar B to C.
The above solution can be described by writing a function, say Move(N, ORG, INT. DES). where N is the number of discs, ORG, INT and DES are origin (from pillar), intermediate (via pillar) and destination (to pillar), respectively. Thus, with this notation, Move(5. X. Z. 1) means moving 5 discs from pillar X to pillar Y taking the intermediate pillar as Z. With this definition in mind, the problem can be solved with recursion as follows:
Input: Number of discs in the tower of Hanoi N, specification of ORG as from the pillar and DES as to the pillar, and INT as the intermediate pillar.
Output: Steps of moves of N discs from pillar ORG to DES pillar.
1. If N> 0 then
2. Move (N-1, ORG, DES, INT)
3. ORG –> DES (Move from ORG to DES)
4. Move (N-1, INT, ORG, DES)
Feel free to share this post if it has been helpful in any way to solve your problem. Finally, in case you’re finding it difficult, You can leave a comment and we will get the issue fixed in hours.