Tower of Hanoi Program in Java
Tower of Hanoi Program in Java
The Tower of Hanoi program in Java is written to solve a mathematical puzzle, called Tower of Hanoi, where we have three poles and n number of disks of different sizes. The task is to move all the n disks placed at one pole to another pole with the help of an intermediate pole. Follow the rules given below while moving the disks:
Rule 1: We can only move one disk at a time from one pole to another.
Rule 2: Only the topmost disk from any of the three given poles can be stacked to another pole.
Rule 3: The larger size disk can’t be placed on the top of a smaller disk.
The Tower of Hanoi puzzle is one of the prominent applications of recursion.
Let’s observe the Java program of the puzzle.
Filename: TowerOfHanoiExample.java
public class TowerOfHanoiExample { // A recursive method to find the solution of the puzzle, called Tower of Hanoi static void twrOfHanoi(int disk, char fromPole, char toPole, char auxPole) { // handling the base case if (disk == 1) { System.out.println("Moving disk 1 from pole " + fromPole + " to pole " + toPole); return; } // The first recursive call // recursively moving the n - 1 disk from the source pole to the auxiliary pole twrOfHanoi(disk - 1, fromPole, auxPole, toPole); // move the nth pole from the source pole to the destination pole System.out.println("Moving disk " + disk + " from pole " + fromPole + " to pole " + toPole); // The second recursive call // recursively moving the n - 1 disk from the auxiliary pole to the destination pole twrOfHanoi(disk - 1, auxPole, toPole, fromPole); } // The driver method public static void main(String argvs[]) { int disks = 3; // total number of disks char firstPole = 'A'; // first pole char secondPole = 'B'; // second pole char thirdPole = 'C'; // third pole // invoking the method twrOfHanoi twrOfHanoi( disks, firstPole, thirdPole, secondPole ); } }
Output:
Moving disk 1 from pole A to pole C Moving disk 2 from pole A to pole B Moving disk 1 from pole C to pole B Moving disk 3 from pole A to pole C Moving disk 1 from pole B to pole A Moving disk 2 from pole B to pole C Moving disk 1 from pole A to pole C
Explanation: In the above program, the three poles has been used to move the disks that are A, B, and C, respectively. Pole A is the source pole, where all the three disks are stacked by default. Pole C is the destination pole, and pole B is the auxiliary pole.
The task is to stack all the disks from the source pole, i.e., pole A to the destination pole, i.e., pole C, with the help of the auxiliary pole, i.e., pole B. The task is accomplished in the three following steps.
Step 1: Recursively move n – 1 disk from pole A to the pole B using pole C as the auxiliary pole.
Step 2: Move the nth disk or the last disk, which is of the largest size, from pole A to pole C.
Step 3: Recursively move n – 1 disk from pole B to the pole C using pole A as the auxiliary pole.


After the completion of the first step, pole A contains only one disk, the largest one. While the second and the third disk get stacked on pole B. Pole C is empty. Here, the pole C has acted as the auxiliary pole. The following diagrams illustrate the same.


Compare the disks positioning of figure-1 and figure-4. We see that pole A, B, and C contain 1, 2, and 0 disks, respectively. Figure-1 shows the initial positioning of the disks, and figure-4 demonstrates the final positioning of disks after the completion of step 1 (the first recursive call). Now, the nth disk is moved from pole A to pole C. After that, we move the remaining disks stacked on pole B to pole C. Consider the following diagrams.
The print statement sandwiched between the recursive calls is used to move the nth pole from the source to the destination pole (see figures 4 & 5). Now, we move to step 3 (figures 6 to 8). Here, pole A acts as the auxiliary pole and B as the source pole. All the disks eventually get stacked to the pole C.
Observe that the output contains 7 statements. Therefore, there are 7 recursive calls. The result of each recursive call is demonstrated in the above figures (figures 2 to 8). Note that, at any step we have not violated the rule to solve the puzzle.
Note: The Java program written above is a generic program and gives correct results even for a large number of disks (change the number of disks from 3 to any desired number and see yourself). For the sake of simplicity, we have chosen only 3 disks.