Recursive Tower of Hanoi using 4 pegs / rods
Tower of Hanoi is a mathematical puzzle. Traditionally, It consists of three poles and a number of disks of different sizes which can slide onto any poles. The puzzle starts with the disk in a neat stack in ascending order of size in one pole, the smallest at the top thus making a conical shape. The objective of the puzzle is to move all the disks from one pole (say ‘source pole’) to another pole (say ‘destination pole’) with the help of third pole (say auxiliary pole). The puzzle has the following two rules: 1. You can’t place a larger disk onto smaller disk 2. Only one disk can be moved at a time We’ve already discussed recursive solution for Tower of Hanoi with time complexity O(2^n). Using 4 rods, same approach shows significant decrease in time complexity.
Examples:
Input : 3 Output : Move disk 1 from rod A to rod B Move disk 2 from rod A to rod C Move disk 3 from rod A to rod D Move disk 2 from rod C to rod D Move disk 1 from rod B to rod D Input : 5 Output : Move disk 1 from rod A to rod C Move disk 2 from rod A to rod D Move disk 3 from rod A to rod B Move disk 2 from rod D to rod B Move disk 1 from rod C to rod B Move disk 4 from rod A to rod C Move disk 5 from rod A to rod D Move disk 4 from rod C to rod D Move disk 1 from rod B to rod A Move disk 2 from rod B to rod C Move disk 3 from rod B to rod D Move disk 2 from rod C to rod D Move disk 1 from rod A to rod D
C++
// C++ Recursive program for Tower of Hanoi #include <iostream> using namespace std; // Recursive function to solve Tower // of Hanoi puzzle void towerOfHanoi( int n, char from_rod, char to_rod, char aux_rod1, char aux_rod2) { if (n == 0) return ; if (n == 1) { cout << "\n Move disk" <<n << " from rod " << from_rod << " to rod " <<to_rod; return ; } towerOfHanoi(n - 2, from_rod, aux_rod1, aux_rod2, to_rod); cout << "\n Move disk" <<n-1 << " from rod " << from_rod << " to rod " <<aux_rod2; cout << "\n Move disk" <<n << " from rod " << from_rod << " to rod " <<to_rod; cout << "\n Move disk" <<n-1 << " from rod " << aux_rod2 << " to rod " <<to_rod; towerOfHanoi(n - 2, aux_rod1, to_rod, from_rod, aux_rod2); } // Driver program int main() { int n = 4; // Number of disks // A, B, C and D are names of rods towerOfHanoi(n, 'A' , 'D' , 'B' , 'C' ); return 0; } // This code is contributed by SHUBHAMSINGH10 |
C
// Recursive program for Tower of Hanoi #include <stdio.h> // Recursive function to solve Tower // of Hanoi puzzle void towerOfHanoi( int n, char from_rod, char to_rod, char aux_rod1, char aux_rod2) { if (n == 0) return ; if (n == 1) { printf ( "\n Move disk %d from rod %c to rod %c" , n, from_rod, to_rod); return ; } towerOfHanoi(n - 2, from_rod, aux_rod1, aux_rod2, to_rod); printf ( "\n Move disk %d from rod %c to rod %c " , n - 1, from_rod, aux_rod2); printf ( "\n Move disk %d from rod %c to rod %c " , n, from_rod, to_rod); printf ( "\n Move disk %d from rod %c to rod %c " , n - 1, aux_rod2, to_rod); towerOfHanoi(n - 2, aux_rod1, to_rod, from_rod, aux_rod2); } // driver program int main() { int n = 4; // Number of disks // A, B, C and D are names of rods towerOfHanoi(n, 'A' , 'D' , 'B' , 'C' ); return 0; } |
Java
// Recursive program for Tower of Hanoi public class GFG { // recursive function to solve // Tower of Hanoi puzzle static void towerOfHanoi( int n, char from_rod, char to_rod, char aux_rod1, char aux_rod2) { if (n == 0 ) return ; if (n == 1 ) { System.out.println( "Move disk " + n + " from rod " + from_rod + " to rod " + to_rod); return ; } towerOfHanoi(n - 2 , from_rod, aux_rod1, aux_rod2, to_rod); System.out.println( "Move disk " + (n - 1 ) + " from rod " + from_rod + " to rod " + aux_rod2); System.out.println( "Move disk " + n + " from rod " + from_rod + " to rod " + to_rod); System.out.println( "Move disk " + (n - 1 ) + " from rod " + aux_rod2 + " to rod " + to_rod); towerOfHanoi(n - 2 , aux_rod1, to_rod, from_rod, aux_rod2); } // Driver method public static void main(String args[]) { int n = 4 ; // Number of disks // A, B, C and D are names of rods towerOfHanoi(n, 'A' , 'D' , 'B' , 'C' ); } } |
Python 3
# Recursive program for Tower of Hanoi # Recursive function to solve Tower # of Hanoi puzzle def towerOfHanoi(n, from_rod, to_rod, aux_rod1, aux_rod2): if (n = = 0 ): return if (n = = 1 ): print ( "Move disk" , n, "from rod" , from_rod, "c to rod" , to_rod) return towerOfHanoi(n - 2 , from_rod, aux_rod1, aux_rod2, to_rod) print ( "Move disk" , n - 1 , "from rod" , from_rod, "c to rod" , aux_rod2) print ( "Move disk" , n, "from rod" , from_rod, "c to rod" , to_rod) print ( "Move disk" , n - 1 , "from rod" , aux_rod2, "c to rod" , to_rod) towerOfHanoi(n - 2 , aux_rod1, to_rod, from_rod, aux_rod2) # driver program n = 4 # Number of disks # A, B, C and D are names of rods towerOfHanoi(n, 'A' , 'D' , 'B' , 'C' ) # This code is contributed by Smitha. |
C#
// Recursive program for Tower of Hanoi using System; public class GFG { // recursive function to solve // Tower of Hanoi puzzle static void towerOfHanoi( int n, char from_rod, char to_rod, char aux_rod1, char aux_rod2) { if (n == 0) return ; if (n == 1) { Console.WriteLine( "Move disk " + n + " from rod " + from_rod + " to rod " + to_rod); return ; } towerOfHanoi(n - 2, from_rod, aux_rod1, aux_rod2, to_rod); Console.WriteLine( "Move disk " + (n - 1) + " from rod " + from_rod + " to rod " + aux_rod2); Console.WriteLine( "Move disk " + n + " from rod " + from_rod + " to rod " + to_rod); Console.WriteLine( "Move disk " + (n - 1) + " from rod " + aux_rod2 + " to rod " + to_rod); towerOfHanoi(n - 2, aux_rod1, to_rod, from_rod, aux_rod2); } // Driver method public static void Main() { int n = 4; // Number of disks // A, B, C and D are names of rods towerOfHanoi(n, 'A' , 'D' , 'B' , 'C' ); } } // This code is contributed by Anant Agarwal. |
PHP
<?php // Recursive PHP program - // Tower of Hanoi // Recursive function to solve // Tower of Hanoi puzzle function towerOfHanoi( $n , $from_rod , $to_rod , $aux_rod1 , $aux_rod2 ) { if ( $n == 0) return ; if ( $n == 1) { echo "\n" , "Move disk" , $n , " from rod " , $from_rod , " to rod" , $to_rod ; return ; } towerOfHanoi( $n - 2, $from_rod , $aux_rod1 , $aux_rod2 , $to_rod ); echo "\n Move disk " , $n - 1, " from rod " , $from_rod , " to rod " , $aux_rod2 ; echo "\n Move disk " , $n , " from rod " , $from_rod , " to rod " , $to_rod ; echo "\n Move disk " , $n -1, " from rod " , $aux_rod2 , " to rod " , $to_rod ; towerOfHanoi( $n - 2, $aux_rod1 , $to_rod , $from_rod , $aux_rod2 ); } // Driver Code // Number of disks $n = 4; // A, B, C and D are // names of rods towerOfHanoi( $n , 'A' , 'D' , 'B' , 'C' ); // This code is contributed by Ajit ?> |
Javascript
// Javascript Recursive program for Tower of Hanoi // Recursive function to solve Tower of Hanoi puzzle function towerOfHanoi(n,from_rod,to_rod,aux_rod1,aux_rod2) { if (n == 0) return ; if (n == 1) { console.log( "Move disk " +n+ " from rod " +from_rod+ " to rod " +to_rod); return ; } towerOfHanoi(n - 2, from_rod, aux_rod1, aux_rod2, to_rod); var a=n-1; console.log( "Move disk " +a+ " from rod " +from_rod+ " to rod " +aux_rod2); console.log( "Move disk " +n+ " from rod " +from_rod+ " to rod " +to_rod); console.log( "Move disk " +a+ " from rod " +aux_rod2+ " to rod " +to_rod); towerOfHanoi(n - 2, aux_rod1, to_rod, from_rod,aux_rod2); } var n = 4; // Number of disks // A, B, C and D are names of rods towerOfHanoi(n, 'A' , 'D' , 'B' , 'C' ); // This code is contributed by satwiksuman |
Move disk1 from rod A to rod D Move disk2 from rod A to rod B Move disk1 from rod D to rod B Move disk3 from rod A to rod C Move disk4 from rod A to rod D Move disk3 from rod C to rod D Move disk1 from rod B to rod C Move disk2 from rod B to rod D Move disk1 from rod C to rod D
Time Complexity: O(2^(N/2))
Auxiliary Space: O(1)
This article contributed by madHEYsia.