Summary: In this programming example, we will learn to solve the Tower of Hanoi problem using recursion in Java.

What is the Tower of Hanoi?

Tower of Hanoi is a game of rods and discs that requires a certain number of discs of different sizes to be transferred from one rod to another.

The simple tower of Hanoi Puzzle includes 3 rods and 3 discs in ascending order, with the smallest one on top.

Our aim is to move all disks to the destination tower in the same order by following the following rules:

  • One disk should be moved at a time.
  • A large disk should not be placed on top of a smaller disk.

Initially, we have this stack:

Tower of Hanoi

We want to achieve this stack to solve the puzzle.

Tower of Hanoi Java

To solve the Tower of Hanoi problem, we will use recursion because every subset of the discs is itself a tower of Hanoi problem.

The Tower of Hanoi can have many problems depending on the number of discs, in our example we will solve Hanoi’s 3 disc tower for the demonstration purpose.

Tower of Hanoi Solution using Recursion

The trick is to assume that we are given only two disks (as stated in the picture).

C program to solve Tower of Hanoi

Now we need to shift the upper disc i.e. n-1 (2 discs in the current scenario) to B so that we can shift the last disk (n-th) to C.

The main point is we will not do this. The recursive function will take the responsibility to shift n-1 disks (2 disks in this case) to B.

where rodFrom = A , rodTo = B and rodMiddle = C.

Tower of Hanoi algorithm

Now we have to shift the last disk (nth or the largest disc) to rod C. So we will do this by printing the statement as follows:

where n=3, rodFrom = A and rodTo = C .

Tower of Hanoi recursion

Now again the n-1 discs (2 discs in rod B) need to be shifted to rod C with the help of rod A.

Since there are multiple risks involved in this turn, let the recursive function handle this task.

where rodFrom = B , rodTo = C and rodMiddle = A will be used as auxiliary rod by the recursive function.

Finally, we will get this i.e Tower of Hanoi solved.

Tower of Hanoi using Recursion

Here is the full source code in Java that solves the Tower of Hanoi problem as discussed above.

Output:

Tower of Hanoi Java Output

In this programming example, we have solved the tower of hanoi problem using the Java programming language.

Leave a Reply

1 × 1 =