The Tower of Hanoi is a classic problem in computer science and mathematics, often used to illustrate recursion. The problem involves three rods and a number of disks of different sizes which can slide onto any rod.
Implementation of Tower of Hanoi problem using a recursive approach
The main objective is to move the entire stack of disks from one rod to another, with the following rules:
- Only one disk can be moved at a time.
- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
- No disk may be placed on top of a smaller disk.
1.Define a method, ‘moveDisks’ that takes four parameters:
- The number of disks to be moved.
- The rod from which the disks need to be moved.
- The destination rod.
- An auxiliary rod that can be used for temporary storage.
2.Base Case:
- If there is only one disk to move, simply move it from the source rod to the destination rod.
3.Recursive Case:
- Move ‘n-1’ disks from the source rod to the auxiliary rod, using the destination rod as temporary storage.
- Move the remaining largest disk from the source rod to the destination rod.
- Move the ‘n-1’ disks from the auxiliary rod to the destination rod, using the source rod as temporary storage.
4.Repeat this process recursively until all disks are moved to the destination rod.
Java program for Towe of Hanoi problem
public class TowerOfHanoi { public static void main(String[] args) { int numDisks = 3 ; //change the umber of diska as needed char sourceRod = 'A'; char destinationRod = 'C'; char auxiliaryRod = 'B'; moveDisks(numDisks, sourceRod, destinationRod, auxiliaryRod); } public static void moveDisks(int numDisks, char source, char destination, char auxiliary) { if(numDisks == 1) { System.out.println("Move disk 1 from rod " + source + " to rod " + destination); return; } moveDisks(numDisks - 1, source, auxiliary, destination); System.out.println("Move disk " + numDisks + " from rod " + source + " to rod " + destination); moveDisks(numDisks - 1, auxiliary, destination, source); } }
Output:
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