DSA: Program for 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. 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(2 n )   where n is the number of rings Space complexity = O(n)

    Ps eudocode 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

    People are also reading: