Write a Java program for solving the Tower of Hanoi Problem.

To solve the Tower of Hanoi problem using recursion, we define a method that takes three parameters: the number of disks and the names of the source, destination, and auxiliary rods. The base case occurs when there is only one disk, which can be moved directly to the destination. For more than one disk, we follow these steps:

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

Here is the implementation in Java:

public class TowerOfHanoi {
    public static void solve(int n, String source, String destination, String auxiliary) {
        if (n == 1) {
            System.out.println("Move disk 1 from " + source + " to " + destination);
            return;
        }
        solve(n - 1, source, auxiliary, destination);
        System.out.println("Move disk " + n + " from " + source + " to " + destination);
        solve(n - 1, auxiliary, destination, source);
    }
}

This solution runs in O(2^n) time complexity, which is optimal for this problem due to the nature of recursive calls.

An alternative approach to solving the Tower of Hanoi problem is through an iterative method, which can be particularly useful for understanding the mechanics of the solution without deep recursion. The iterative solution uses a bit manipulation technique to determine the moves. Here's how it works:

1. Calculate the total number of moves required, 2^n - 1.
2. For each move, determine which rod to move from and to, based on whether the number of disks is odd or even.
3. Repeat the process for the total number of moves.

Here’s the Java code for the iterative approach:

public class TowerOfHanoiIterative {
    public static void solve(int n) {
        int totalMoves = (int) Math.pow(2, n) - 1;
        String source = "A", destination = "C", auxiliary = "B";

        for (int i = 1; i <= totalMoves; i++) {
            int from, to;
            if (i % 3 == 1) {
                from = source;
                to = destination;
            } else if (i % 3 == 2) {
                from = source;
                to = auxiliary;
            } else {
                from = auxiliary;
                to = destination;
            }
            System.out.println("Move disk from " + from + " to " + to);
        }
    }
}

This method is more space-efficient as it avoids the overhead of recursive calls, making it suitable for larger numbers of disks.

While the Tower of Hanoi problem is inherently recursive, we can use memoization to optimize our solution, particularly when dealing with larger input sizes. Although the classic problem does not exhibit overlapping subproblems, we can illustrate how memoization could be applied in a modified version where intermediate states are stored. Here’s a conceptual outline:

1. Use a map to store previously computed moves for a given number of disks.
2. Before executing the recursive calls, check if the result is already in the map.
3. If it is, retrieve the result instead of re-computing it.

Here’s a simplified version of how to implement this:

import java.util.HashMap;
import java.util.Map;

public class TowerOfHanoiMemoized {
    private static Map<Integer, String> memo = new HashMap<>();

    public static void solve(int n, String source, String destination, String auxiliary) {
        if (memo.containsKey(n)) {
            System.out.println(memo.get(n));
            return;
        }
        if (n == 1) {
            String move = "Move disk 1 from " + source + " to " + destination;
            memo.put(n, move);
            System.out.println(move);
            return;
        }
        solve(n - 1, source, auxiliary, destination);
        String move = "Move disk " + n + " from " + source + " to " + destination;
        memo.put(n, move);
        System.out.println(move);
        solve(n - 1, auxiliary, destination, source);
    }
}

This approach demonstrates a more advanced understanding of recursion and optimization techniques, allowing candidates to showcase their ability to think critically about algorithm performance.