Tower of hanoi using recursion in python

View Discussion

Improve Article

Save Article

  • Read
  • Discuss
  • View Discussion

    Improve Article

    Save Article

    Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: 
    1) Only one disk can be moved at a time. 
    2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack. 
    3) No disk may be placed on top of a smaller disk.
    Note: Transferring the top n-1 disks from source rod to Auxiliary rod can again be thought of as a fresh problem and can be solved in the same manner.
     

    Tower of hanoi using recursion in python
     

    Python3

    def TowerOfHanoi(n , source, destination, auxiliary):

        if n==1:

            print ("Move disk 1 from source",source,"to destination",destination)

            return

        TowerOfHanoi(n-1, source, auxiliary, destination)

        print ("Move disk",n,"from source",source,"to destination",destination)

        TowerOfHanoi(n-1, auxiliary, destination, source)

    n = 4

    TowerOfHanoi(n,'A','B','C')

    Output

    Move disk 1 from source A to destination C
    Move disk 2 from source A to destination B
    Move disk 1 from source C to destination B
    Move disk 3 from source A to destination C
    Move disk 1 from source B to destination A
    Move disk 2 from source B to destination C
    Move disk 1 from source A to destination C
    Move disk 4 from source A to destination B
    Move disk 1 from source C to destination B
    Move disk 2 from source C to destination A
    Move disk 1 from source B to destination A
    Move disk 3 from source C to destination B
    Move disk 1 from source A to destination C
    Move disk 2 from source A to destination B
    Move disk 1 from source C to destination B

    Time Complexity: O(2n)

    Auxiliary Space: O(n)

    Please refer complete article on Program for Tower of Hanoi for more details!
     

    In this tutorial, we will implement the famous Tower of Hanoi puzzle using the Python program. We will solve this problem by using recursion function.

    If you aren't familiar with the Recursion function concepts, visit our Python recursive function tutorial (https://www.javatpoint.com/python-factorial-number-using-recursion).

    What is the Tower of Hanoi?

    In 1883, the Tower of Hanoi mathematical puzzle was invented by the French mathematician Edouard Lucas. The inspiration came from a legend that states - In Ancient Hindu temple, this puzzle was presented to the young priest. The puzzle is, there are three poles, and 64 disks, and each disk is smaller than the other. To solve this problem, move all 64 disks from one of the three poles to another pole without violating the essential constraints.

    The disks can be moved one disk at a time and they should place a smaller disk top of a larger one.

    Other folktale states, when they would solve this puzzle, the temple would smash into dust, and the world would end. But it would take a lot of time because to solve this problem 264 - 1 moves are necessary i.e., 18,446,744,073,709,551,615 per second that is equal to 5, 84,942,417,355 years according to the rules.

    Rules of the game

    The rules of "Tower of Hanoi" are quite simple, but the solution is slightly hard. There are three rods. The disks are stacked in the descending order; the largest disk stacked at the bottom and the smallest one on top.

    The task is to transfer the disks from one source rod to another target rod.

    The following rule must not be violated

    • Only one disk can be moved at a time.
    • The most upper disk from one of the rod can be stimulated in move.
    • The smaller disk cannot be placed at the lower of the largest disk.

    The number of moves can be calculated as 2n - 1.

    Solution:

    At the beginning of this tutorial, we have mentioned that we will use the recursive function to find the solution.

    Suppose we have three disks on the first rod; we need total 7 moves from the above formula. The most left rod is called SOURCE, and the rightmost rod is called TARGET. The middle rod is referred to as an AUX.

    The AUX is needed to deposit disks temporarily.

    Tower of hanoi using recursion in python

    Problem Approach

    1. Create a tower_of_hanoi recursive function and pass two arguments: the number of disks n and the name of the rods such as source, aux, and target.
    2. We can define the base case when the number of disks is 1. In this case, simply move the one disk from the source to target and return.
    3. Now, move remaining n-1 disks from source to auxiliary using the target as the auxiliary.
    4. Then, the remaining 1 disk move on the source to target.
    5. Move the n-1 disks on the auxiliary to the target using the source as the auxiliary.

    Python Program/ Source Code

    Output:

    Enter the number of disks: 3
    Move disk 1 from rod A to rod C.
    Move disk 2 from rod A to rod B.
    Move disk 1 from rod C to rod B.
    Move disk 3 from rod A to rod C.
    Move disk 1 from rod B to rod A.
    Move disk 2 from rod B to rod C.
    Move disk 1 from rod A to rod C.
    

    Case - 2:

    According to the formula, the moves can be happened 2n - 1, so n = 3 took 7 moves and, n = 2 took 3 moves.


    Can Tower of Hanoi be solved using recursion?

    So there you go now , the above program can help you solve the Tower of Hanoi puzzle for any number of disks in C++ and Python using a recursive approach.

    What is Tower of Hanoi problem in Python?

    Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: 1) Only one disk can be moved at a time.

    How do you make a Tower of Hanoi in Python?

    Python Program/ Source Code Enter the number of disks: 3 Move disk 1 from rod A to rod C. Move disk 2 from rod A to rod B. Move disk 1 from rod C to rod B. Move disk 3 from rod A to rod C.

    How does the Tower of Hanoi relate to recursion?

    In our Towers of Hanoi solution, we recurse on the largest disk to be moved. That is, we will write a recursive function that takes as a parameter the disk that is the largest disk in the tower we want to move.

    Tải thêm tài liệu liên quan đến bài viết Tower of hanoi using recursion in python