Java Code Example: Tower of Hanoi (recursive)

The Tower of Hanoi is a classic mathematical puzzle that involves moving a set of disks from one rod to another, following specific rules:

1. Only one disk can be moved at a time.
2. A disk can only be placed on top of a larger disk (or on an empty rod).
3. The objective is to move all disks from the source rod to the destination rod, using an auxiliary rod as needed.

The problem can be solved using recursion, where we break the problem into smaller subproblems and solve them step by step.

Java Code Example

public class TowerOfHanoi {
    // Recursive function to solve Tower of Hanoi
    public static void solveHanoi(int n, char source, char auxiliary, char destination) {
        if (n == 1) {
            System.out.println("Move disk 1 from " + source + " to " + destination);
            return;
        }

        // Move (n-1) disks from source to auxiliary using destination
        solveHanoi(n - 1, source, destination, auxiliary);
        
        // Move the nth disk from source to destination
        System.out.println("Move disk " + n + " from " + source + " to " + destination);
        
        // Move the (n-1) disks from auxiliary to destination using source
        solveHanoi(n - 1, auxiliary, source, destination);
    }

    public static void main(String[] args) {
        int n = 3; // Number of disks
        System.out.println("Tower of Hanoi solution for " + n + " disks:");
        solveHanoi(n, 'A', 'B', 'C'); // A = Source, B = Auxiliary, C = Destination
    }
}

Output for 3 Disks

Tower of Hanoi solution for 3 disks:
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

Explanation

1. Base Case:
   • If there is only one disk (n == 1), we move it directly from the source to the destination.
2. Recursive Case:
   • First, we move the top (n-1) disks from the source rod to the auxiliary rod, using the destination rod.
   • Then, we move the largest disk directly from source to destination.
   • Finally, we move the (n-1) disks from the auxiliary rod to the destination rod, using the source rod.

Since each move follows the rules, the entire stack of disks is moved correctly to the destination rod in minimal steps (2ⁿ – 1 moves for n disks).

Conclusion

The Tower of Hanoi is an excellent example of a recursive problem where a larger problem is broken into smaller subproblems. The recursive solution efficiently finds the optimal sequence of moves. However, as n increases, the number of moves grows exponentially (O(2ⁿ) complexity), making it impractical for very large values of n.