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 = 4TowerOfHanoi(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