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.
Approach :
Take an example for 2 disks : Let rod 1 = 'A', rod 2 = 'B', rod 3 = 'C'. Step 1 : Shift first disk from 'A' to 'B'. Step 2 : Shift second disk from 'A' to 'C'. Step 3 : Shift first disk from 'B' to 'C'. The pattern here is : Shift 'n-1' disks from 'A' to 'B'. Shift last disk from 'A' to 'C'. Shift 'n-1' disks from 'B' to 'C'. Image illustration for 3 disks :![]()
Examples:
Input : 2 Output : Disk 1 moved from A to B Disk 2 moved from A to C Disk 1 moved from B to C Input : 3 Output : Disk 1 moved from A to C Disk 2 moved from A to B Disk 1 moved from C to B Disk 3 moved from A to C Disk 1 moved from B to A Disk 2 moved from B to C Disk 1 moved from A to C
C++
// C++ recursive function to // solve tower of hanoi puzzle #include <bits/stdc++.h> using namespace std; void towerOfHanoi( int n, char from_rod, char to_rod, char aux_rod) { if (n == 1) { cout << "Move disk 1 from rod " << from_rod << " to rod " << to_rod<<endl; return ; } towerOfHanoi(n - 1, from_rod, aux_rod, to_rod); cout << "Move disk " << n << " from rod " << from_rod << " to rod " << to_rod << endl; towerOfHanoi(n - 1, aux_rod, to_rod, from_rod); } // Driver code int main() { int n = 4; // Number of disks towerOfHanoi(n, 'A' , 'C' , 'B' ); // A, B and C are names of rods return 0; } // This is code is contributed by rathbhupendra |
C
#include <stdio.h> // C recursive function to solve tower of hanoi puzzle void towerOfHanoi( int n, char from_rod, char to_rod, char aux_rod) { if (n == 1) { printf ( "
Move disk 1 from rod %c to rod %c" , from_rod, to_rod); return ; } towerOfHanoi(n-1, from_rod, aux_rod, to_rod); printf ( "
Move disk %d from rod %c to rod %c" , n, from_rod, to_rod); towerOfHanoi(n-1, aux_rod, to_rod, from_rod); } int main() { int n = 4; // Number of disks towerOfHanoi(n, 'A' , 'C' , 'B' ); // A, B and C are names of rods return 0; } |
Java
// Java recursive program to solve tower of hanoi puzzle class GFG { // Java recursive function to solve tower of hanoi puzzle static void towerOfHanoi( int n, char from_rod, char to_rod, char aux_rod) { if (n == 1 ) { System.out.println( "Move disk 1 from rod " + from_rod + " to rod " + to_rod); return ; } towerOfHanoi(n- 1 , from_rod, aux_rod, to_rod); System.out.println( "Move disk " + n + " from rod " + from_rod + " to rod " + to_rod); towerOfHanoi(n- 1 , aux_rod, to_rod, from_rod); } // Driver method public static void main(String args[]) { int n = 4 ; // Number of disks towerOfHanoi(n, 'A' , 'C' , 'B' ); // A, B and C are names of rods } } |
Python
# Recursive Python function to solve tower of hanoi def TowerOfHanoi(n , from_rod, to_rod, aux_rod): if n = = 1 : print "Move disk 1 from rod" ,from_rod, "to rod" ,to_rod return TowerOfHanoi(n - 1 , from_rod, aux_rod, to_rod) print "Move disk" ,n, "from rod" ,from_rod, "to rod" ,to_rod TowerOfHanoi(n - 1 , aux_rod, to_rod, from_rod) # Driver code n = 4 TowerOfHanoi(n, 'A' , 'C' , 'B' ) # A, C, B are the name of rods # Contributed By Harshit Agrawal |
C#
// C# recursive program to solve // tower of hanoi puzzle using System; class geek { // C# recursive function to solve // tower of hanoi puzzle static void towerOfHanoi( int n, char from_rod, char to_rod, char aux_rod) { if (n == 1) { Console.WriteLine( "Move disk 1 from rod " + from_rod + " to rod " + to_rod); return ; } towerOfHanoi(n-1, from_rod, aux_rod, to_rod); Console.WriteLine( "Move disk " + n + " from rod " + from_rod + " to rod " + to_rod); towerOfHanoi(n-1, aux_rod, to_rod, from_rod); } // Driver method public static void Main() { // Number of disks int n = 4; // A, B and C are names of rods towerOfHanoi(n, 'A' , 'C' , 'B' ); } } // This code is contributed by Sam007 |
PHP
<?php //PHP code to solve Tower of Hanoi problem. // Recursive Function to solve Tower of Hanoi function towerOfHanoi( $n , $from_rod , $to_rod , $aux_rod ) { if ( $n === 1) { echo ( "Move disk 1 from rod $from_rod to rod $to_rod
" ); return ; } towerOfHanoi( $n -1, $from_rod , $aux_rod , $to_rod ); echo ( "Move disk $n from rod $from_rod to rod $to_rod
" ); towerOfHanoi( $n -1, $aux_rod , $to_rod , $from_rod ); } // Driver code // number of disks $n = 4; // A, B and C are names of rods towerOfHanoi( $n , 'A' , 'C' , 'B' ); // This code is contributed by akash7981 ?> |
Output:
Move disk 1 from rod A to rod B Move disk 2 from rod A to rod C Move disk 1 from rod B to rod C Move disk 3 from rod A to rod B Move disk 1 from rod C to rod A Move disk 2 from rod C to rod B Move disk 1 from rod A to rod B Move disk 4 from rod A to rod C Move disk 1 from rod B to rod C Move disk 2 from rod B to rod A Move disk 1 from rod C to rod A Move disk 3 from rod B to rod C Move disk 1 from rod A to rod B Move disk 2 from rod A to rod C Move disk 1 from rod B to rod C
For n disks, total 2n – 1 moves are required.
eg: For 4 disks 24 – 1 = 15 moves are required.
For n disks, total 2n-1 function calls are made.
eg: For 4 disks 24-1 = 8 function calls are made.
Related Articles
References:
http://en.wikipedia.org/wiki/Tower_of_Hanoi
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments