**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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
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:**

1 2 3 4 5 6 7 8 9 |
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 n^{th }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 n^{th }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 n^{th }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.