Tower of Hanoi

Problem Statement

Write a Java program that uses recursion to solve the Tower of Hanoi problem for n disks, printing the sequence of moves required to transfer all disks from a source rod to a destination rod using an auxiliary rod. The rules are: only one disk can be moved at a time, a larger disk cannot be placed on a smaller disk, and disks must be moved between the rods (source, auxiliary, destination). Test the program with different values of n, including edge cases like n = 1. You can visualize this as moving a stack of differently sized books from one table to another, using a third table as temporary storage, ensuring larger books are always below smaller ones.

Input: A non-negative integer n representing the number of disks, and three rod names (e.g., source = 'A', auxiliary = 'B', destination = 'C'). Output: A sequence of moves printed in the format "Move disk [number] from [source] to [destination]" (e.g., "Move disk 1 from A to C"), with each move on a new line. Constraints:

• 0 ≤ n ≤ 10 (to keep output manageable and avoid excessive recursion).
• Rod names are single characters (e.g., 'A', 'B', 'C'). Example:
• Input: n = 2, source = 'A', auxiliary = 'B', destination = 'C'
• Output:

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

• Explanation: The two disks are moved from rod A to rod C using rod B as auxiliary, following the rules of the Tower of Hanoi.

Pseudocode

FUNCTION towerOfHanoi(n, source, auxiliary, destination)
    IF n equals 0 THEN
        RETURN
    ENDIF
    IF n equals 1 THEN
        PRINT "Move disk 1 from source to destination"
        RETURN
    ENDIF
    CALL towerOfHanoi(n - 1, source, destination, auxiliary)
    PRINT "Move disk n from source to destination"
    CALL towerOfHanoi(n - 1, auxiliary, source, destination)
ENDFUNCTION

Algorithm Steps

1. Check if the number of disks n is 0. If so, return immediately, as no moves are needed.
2. Define a recursive function that takes the number of disks n and the names of the source, auxiliary, and destination rods as parameters.
3. In the recursive function, implement the base case: if n equals 1, print a move to transfer the single disk from the source to the destination rod and return.
4. For the recursive case, perform three steps: a. Recursively move n - 1 disks from the source rod to the auxiliary rod, using the destination rod as the auxiliary. b. Print a move to transfer the nth disk from the source rod to the destination rod. c. Recursively move n - 1 disks from the auxiliary rod to the destination rod, using the source rod as the auxiliary.
5. In the main function, call the recursive function with the input n and rod names (e.g., 'A', 'B', 'C').
6. The function prints the sequence of moves to solve the Tower of Hanoi problem.

Java Implementation

public class TowerOfHanoi {
    // Solves Tower of Hanoi for n disks and prints moves
    public void towerOfHanoi(int n, char source, char auxiliary, char destination) {
        // Base case: no disks to move
        if (n == 0) {
            return;
        }
        // Base case: single disk, move directly
        if (n == 1) {
            System.out.println("Move disk 1 from " + source + " to " + destination);
            return;
        }
        // Recursive case: move n-1 disks to auxiliary rod
        towerOfHanoi(n - 1, source, destination, auxiliary);
        // Move nth disk to destination rod
        System.out.println("Move disk " + n + " from " + source + " to " + destination);
        // Move n-1 disks from auxiliary to destination rod
        towerOfHanoi(n - 1, auxiliary, source, destination);
    }
}

Output

For the input n = 2, source = 'A', auxiliary = 'B', destination = 'C', the program outputs:

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

Explanation: The two disks are moved from rod A to rod C using rod B as auxiliary, following the Tower of Hanoi rules.

For the input n = 1, source = 'A', auxiliary = 'B', destination = 'C', the program outputs:

Move disk 1 from A to C

Explanation: A single disk is moved directly from rod A to rod C.

How It Works

• Step 1: The towerOfHanoi method checks if n is 0. For n = 2, it proceeds to the recursive case.
• Step 2: For n = 2:
  • First recursive call: towerOfHanoi(1, A, C, B):
    • Base case: n = 1, prints "Move disk 1 from A to B".
  • Print: "Move disk 2 from A to C".
  • Second recursive call: towerOfHanoi(1, B, A, C):
    • Base case: n = 1, prints "Move disk 1 from B to C".
• Step 3: The recursion generates the sequence of moves to transfer all disks from source to destination while respecting the rules.
• Example Trace: For n = 2:
  • Move disk 1 from A to B (move top disk to auxiliary).
  • Move disk 2 from A to C (move largest disk to destination).
  • Move disk 1 from B to C (move top disk to destination).
• Testing with Different n: For n = 1, it prints one move. For n = 3, it generates 7 moves (2^3 - 1), following the same recursive pattern.

Complexity Analysis Table

Note:

• n is the number of disks.
• Time complexity: O(2^n), as the algorithm makes 2^n - 1 moves, with each move involving a constant-time print operation.
• Space complexity: O(n) due to the recursive call stack, which grows linearly with the number of disks.
• Best, average, and worst cases are all O(2^n), as the number of moves is fixed for a given n.

✅ Tip: Use the Tower of Hanoi to understand recursive problem-solving, and test with small values of n (e.g., 1, 2, 3) to visualize the move sequence. Count the number of moves to confirm it matches 2^n - 1.

⚠ Warning: Avoid large values of n (e.g., >10), as the O(2^n) time complexity leads to an exponential number of moves, causing significant delays. Ensure rod names are distinct to avoid confusion in output.