Tower of Hanoi is a mathematical problem (puzzle) that consists of 3 poles and ‘n’ number of discs, each disc having different diameters.
The Objective of the Tower of Hanoi Problem
The objective or goal of this problem is to transfer all the ‘n’ discs from source pole to the destination pole in such a way that we get the same arrangement of discs as before. But this goal must be achieved by sticking to the rules.
Rules and Constraints
The constraints that must be satisfied while solving the problem are –
- Only one disc can be moved at a time.
- Only the top-most disc can be removed
- The larger disc cannot be placed on top of the smaller disc.
Visual Representation of the Tower of Hanoi problem
The following picture shows the step-wise solution for a tower of Hanoi with 3 poles (source, intermediate, destination) and 3 discs. The goal is to move all the 3 discs from pole A to pole C.
As we can see from the above solution, the number of moves needed for 3 discs = 8. So, a generalized formula for a total number of moves we need is:
Total number of moves = n2 – 1
Where ‘n’ is the total no. of discs.
Solving the Tower of Hanoi Problem in Python
def TowerOfHanoi(n , s_pole, d_pole, i_pole): if n == 1: print("Move disc 1 from pole",s_pole,"to pole",d_pole) return TowerOfHanoi(n-1, s_pole, i_pole, d_pole) print("Move disc",n,"from pole",s_pole,"to pole",d_pole) TowerOfHanoi(n-1, i_pole, d_pole, s_pole) n = 3 TowerOfHanoi(n, 'A', 'C', 'B') # A, C, B are the name of poles
In the above code, we call our function TowerOfHanoi recursively for 3 discs.
- s_pole: source pole
- i_pole: intermediate pole
- d_pole: destination pole
The output of the above code is:
So , this is how we solve the problem of Tower of Hanoi.
This code can be generalized for any number of discs. So if you want the solution for 4 discs, just change the value of n from 3 to 4 as n = 4, and the output will be displayed for 4 discs and so on.