Tower of Hanoi in Java

Introduction

The Tower of Hanoi is a classic puzzle that has puzzled mathematicians and computer scientists for decades. It consists of three pegs and a stack of disks of different sizes, initially arranged on one peg in ascending order of size. The objective is to move the entire stack of disks to another peg, following a set of rules: only one disk can be moved at a time, and each move consists of taking the upper disk from one peg and placing it on top of another peg, and no disk may be placed on top of a smaller disk. This puzzle is significant because it teaches important concepts like recursive problem-solving & algorithmic thinking. 

In this article, we'll discuss the Tower of Hanoi puzzle using Java programming. We'll look into the problem statement and the rules of the puzzle, and see how to solve it using recursion. 

Java Program for Tower of Hanoi

Let's look into the Java program that solves it. We'll start by defining the problem statement more formally.

Given three pegs (let's call them source, auxiliary, & destination) & a stack of n disks of different sizes, we need to move the entire stack from the source peg to the destination peg. We must follow these rules:

1. Only one disk can be moved at a time.
 

2. Each move consists of taking the upper disk from one peg & placing it on top of another peg.
 

3. No disk may be placed on top of a smaller disk.
 

To solve this problem, we'll use a recursive approach. The basic idea is to break down the problem into smaller subproblems until we reach the base case. Let’s see how we can think about the recursive solution:
 

1. If there is only one disk, simply move it from the source peg to the destination peg.
 

2. If there are n disks, do the following:
 

   a. Recursively move the top n-1 disks from the source peg to the auxiliary peg, using the destination peg as the intermediate peg.
 

   b. Move the nth disk (the largest one) from the source peg to the destination peg.
 

   c. Recursively move the n-1 disks from the auxiliary peg to the destination peg, using the source peg as the intermediate peg.
 

Let's see how this can be implemented into Java code:

public class TowerOfHanoi {
    public static void towerOfHanoi(int n, char source, char auxiliary, char destination) {
        if (n == 1) {
            System.out.println("Move disk 1 from " + source + " to " + destination);
            return;
        }
        towerOfHanoi(n - 1, source, destination, auxiliary);
        System.out.println("Move disk " + n + " from " + source + " to " + destination);
        towerOfHanoi(n - 1, auxiliary, source, destination);
    }
    public static void main(String[] args) {
        int n = 3; // Number of disks
        towerOfHanoi(n, 'A', 'B', 'C'); // A, B, C are the names of the pegs
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

In this code, we define a recursive function `towerOfHanoi` that takes four parameters: the number of disks `n`, and the names of the source, auxiliary, & destination pegs. The base case is when there is only one disk (n == 1), in which case we simply print the move. For n disks, we recursively solve the problem by moving n-1 disks from source to auxiliary, then moving the nth disk from source to destination, & finally moving the n-1 disks from auxiliary to destination.

The main method demonstrates how to use this function by calling it with n = 3 disks and pegs named 'A', 'B', and 'C'.

Time and Space Complexity

When analyzing an algorithm, it's important to understand its time and space complexity. Time complexity measures how the running time of an algorithm grows as the input size increases, while space complexity measures how the memory usage grows.

For the Tower of Hanoi problem, let's analyze the time complexity first. Let's say we have n disks. In each recursive call, we make two recursive calls to move n-1 disks, & we perform one additional move to move the nth disk. This gives us the following recurrence relation for the time complexity T(n):

T(n) = 2T(n-1) + 1

The solution to this recurrence relation is O(2^n). This means that the time complexity of the Tower of Hanoi algorithm grows exponentially with the number of disks. For example, if we double the number of disks, the running time will increase by a factor of about 2^n.

Let’s look at a table showing the number of moves required for different numbers of disks:

Here is a table representing the given data:

As you can see, the number of moves grows quickly as n increases.

Now, let's consider the space complexity. In our recursive solution, the space complexity is determined by the maximum depth of the recursive call stack. Since we make recursive calls to move n-1 disks, the maximum depth of the call stack will be n. Therefore, the space complexity of the Tower of Hanoi algorithm is O(n).

It's important to remember that the iterative solution to the Tower of Hanoi problem has a space complexity of O(1) because it doesn't use any additional data structures that grow with the input size. However, the iterative solution is more complex to implement compared to the recursive solution.

In summary, the Tower of Hanoi problem has a time complexity of O(2^n) & a space complexity of O(n) when solved using recursion. While the time complexity is exponential, the space complexity is linear.