DSA: Program for Tower of Hanoi

By | January 5, 2020
Tower of Hanoi

Tower of Hanoi is a popular math puzzle in which we have given 3 towers and one of those towers has n number of rings of a different shape. We need to move those rings from one tower to another and collect all rings in another tower in the exact same sequence.

All the rings are of different sizes and stacked in ascending order on one of the towers. The number of rings may be changed for various puzzles but the number of towers will remain the same 3.

Vamware

There are 3 simples rules we need to follow when we solve this problem:

  • We can move only one ring at a time
  • We can only move the upper ring from any tower and move it to another tower
  • No larger ring may be placed on the top of a smaller one.

Algorithm:

  • We have 3 towers so towers naming will be the source, destination, and auxiliary.
  • The source tower would be that tower which contains all the rings in ascending order from top to bottom in first place.
  • The destination would be that tower in which we will move all the rings and placed those in the same order as they are in source tower.
  • Auxiliary tower will help to move rings from one place to another.

Time Complexity = O(2n)   where n is the number of rings
Space complexity = O(n)

Pseudocode for Tower of Hanoi

tower(number_of_rings, source, auxiliary, destination)
IF numbe_of_rings == 1
      move disk from source to destination
ELSE
      tower(number_of_rings - 1, source, destination, auxiliary)  
      move disk from source to destination               
      tower(number_of_rings - 1, auxiliary, source, destination) 

Tower of Hanoi for 3 rings

Python:

def T_O_H(n , source, destination,auxiliary):
    if n == 1:
        print("Move ring 1 from ",source,"to",destination)
        return

    T_O_H(n-1, source, auxiliary, destination)
    print ("Move ring",n,"from",source,"to", destination)
    T_O_H(n-1, auxiliary, destination, source)       

n = int(input("Enter the number of Rings: "))
TowerOfHanoi(n, 'SOURCE', 'DESTINATION', 'AUXILIARY')

Output:

Enter the number of Rings: 3
Move ring 1 from SOURCE to DESTINATION
Move ring 2 from SOURCE to AUXILIARY
Move ring 1 from DESTINATION to AUXILIARY
Move ring 3 from SOURCE to DESTINATION
Move ring 1 from AUXILIARY to SOURCE
Move ring 2 from AUXILIARY to DESTINATION
Move ring 1 from SOURCE to DESTINATION

You may be also interested in:

Leave a Reply

Your email address will not be published. Required fields are marked *