Python Program for Tower of Hanoi
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.
Python3
# Recursive Python function to solve the tower of hanoi 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) # Driver code n = 4 TowerOfHanoi(n, 'A' , 'B' , 'C' ) # A, C, B are the name of rods # Contributed By Dilip Jain |
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!
Contact Us