Tower of Hanoi Problem in Java: Best Approaches with Details

 The Tower of Hanoi is a classic problem that has fascinated mathematicians and computer scientists for decades. It is often used to illustrate recursive problem-solving techniques, and it can also be a valuable tool for learning about algorithms and recursion.

In this blog, we will explore the Tower of Hanoi Problem, focusing on its best approaches. We will also provide a detailed breakdown of the recursive solution and an iterative approach.

What is the Tower of Hanoi Problem?

The Tower of Hanoi involves three pegs and a set of disks of different sizes. The objective is to move all the disks from one peg to another, following these rules:

1. Only one disk can be moved at a time.
2. A disk may only be placed on an empty peg or on top of a larger disk.
3. All disks start on one peg, and the goal is to move them to another peg while following the rules.

Problem Setup

We have:

• Three pegs: Source, Auxiliary, and Destination.
• Disks of different sizes are initially arranged on the source peg with the largest disk at the bottom.

The task is to move all disks from the source peg to the destination peg, following the rules.

Recursive Approach

The recursive approach is the most common way to solve the Tower of Hanoi problem. The general strategy is as follows:

1. Move the n-1 disks from the source peg to the auxiliary peg.
2. Move the nth disk (the largest disk) directly from the source peg to the destination peg.
3. Move the n-1 disks from the auxiliary peg to the destination peg.

This is a natural recursive process where each smaller sub-problem mirrors the original problem. The base case for the recursion is when only one disk is left to move.

Java Code for Recursive Solution

public class TowerOfHanoi {

    // Recursive function to solve the Tower of Hanoi problem
    public static void solveTowerOfHanoi(int n, char source, char auxiliary, char destination) {
        if (n == 1) {
            // Base case: if there's only one disk, move it to the destination
            System.out.println("Move disk 1 from " + source + " to " + destination);
            return;
        }
        
        // Move n-1 disks from source to auxiliary
        solveTowerOfHanoi(n - 1, source, destination, auxiliary);

        // Move the nth disk from source to destination
        System.out.println("Move disk " + n + " from " + source + " to " + destination);

        // Move n-1 disks from auxiliary to destination
        solveTowerOfHanoi(n - 1, auxiliary, source, destination);
    }

    public static void main(String[] args) {
        int n = 3; // Number of disks
        System.out.println("The sequence of moves to solve the Tower of Hanoi for " + n + " disks are:");
        solveTowerOfHanoi(n, 'A', 'B', 'C'); // A is source, B is auxiliary, C is destination
    }
}

Explanation of the Recursive Code

1. Base Case: If only one disk is left to move (n == 1), we simply move it directly to the destination peg.
2. Recursive Case: If n > 1, we:
   • Recursively move the n-1 disks from the source to the auxiliary peg.
   • Move the nth disk (the largest disk) from the source to the destination peg.
   • Recursively move the n-1 disks from the auxiliary peg to the destination peg.

This recursive solution works efficiently and directly follows the structure of the problem.

Iterative Approach

The iterative approach to the Tower of Hanoi problem is not as intuitive as the recursive approach, but it is still possible to solve it without recursion. This approach generally involves using a stack or keeping track of the states of the disks and pegs. For simplicity, we will discuss a strategy that uses binary operations to simulate the recursive steps iteratively.

Steps for the Iterative Approach

1. Number of Moves: The minimum number of moves required to solve the Tower of Hanoi problem is 2^n - 1, where n is the number of disks.
2. Binary Representation: The iterative approach simulates the sequence of moves using binary representation. Each move is encoded as a binary number, with each bit corresponding to a disk and the state representing the peg to which the disk should be moved.
3. Rules for Move: The sequence of moves follows the same logic as recursion but is derived iteratively, usually using an alternating move pattern and careful management of disk positions.

Pseudocode for Iterative Solution

public class TowerOfHanoiIterative {

    // Iterative function to solve the Tower of Hanoi problem
    public static void solveTowerOfHanoiIteratively(int n, char source, char auxiliary, char destination) {
        int totalMoves = (int) Math.pow(2, n) - 1; // Total number of moves
        char temp;
        
        // Determine the peg to move the disks
        if (n % 2 == 0) {
            temp = destination;
            destination = auxiliary;
            auxiliary = temp;
        }

        // Loop through each move
        for (int move = 1; move <= totalMoves; move++) {
            int disk = findDiskToMove(move, n);
            char from = getFromPeg(disk, source, auxiliary, destination);
            char to = getToPeg(disk, source, auxiliary, destination);

            System.out.println("Move disk " + disk + " from " + from + " to " + to);
        }
    }

    // Find which disk to move based on the binary representation of the move
    private static int findDiskToMove(int move, int n) {
        for (int i = 1; i <= n; i++) {
            if ((move & (1 << (i - 1))) != 0) {
                return i;
            }
        }
        return 0;
    }

    // Get the "from" peg based on the disk
    private static char getFromPeg(int disk, char source, char auxiliary, char destination) {
        if (disk % 3 == 1) return source;
        if (disk % 3 == 2) return auxiliary;
        return destination;
    }

    // Get the "to" peg based on the disk
    private static char getToPeg(int disk, char source, char auxiliary, char destination) {
        if (disk % 3 == 1) return destination;
        if (disk % 3 == 2) return source;
        return auxiliary;
    }

    public static void main(String[] args) {
        int n = 3; // Number of disks
        System.out.println("The sequence of moves to solve the Tower of Hanoi iteratively for " + n + " disks are:");
        solveTowerOfHanoiIteratively(n, 'A', 'B', 'C'); // A is source, B is auxiliary, C is destination
    }
}

Explanation of the Iterative Approach

• Binary Representation: The findDiskToMove function uses the binary representation of the current move to determine which disk to move. The moves alternate between the three pegs, mimicking recursive logic.
• Looping: Instead of recursive function calls, the program loops through each move, making the process iterative while ensuring the correct disk-to-peg moves.

Comparing the Approaches

1. Recursive Approach:
   • Simple and elegant.
   • Easy to understand and implement.
   • Has a time complexity of O(2^n), as each recursive call performs two subproblems.
2. Iterative Approach:
   • More complex and less intuitive.
   • Useful for understanding binary operations and simulating recursion.
   • Also has a time complexity of O(2^n), but with a different implementation method.

Summary

Both methods have the same time complexity, but understanding both is beneficial for developing a well-rounded understanding of algorithms in computer science.

Thanks for reading! 🎉 I'd love to know what you think about the article. Did it resonate with you? 💭 Any suggestions for improvement? I’m always open to hearing your feedback so that I can improve my posts! 👇🚀. Happy coding! 💻✨