Tower of Hanoi: Problem and Recursive Solution

Question

Explain the Tower of Hanoi problem and implement a recursive solution in Java. Include: - Problem description and rules - Recursive algorithm explanation - Implementation with step-by-step visualization - Analysis of time and space complexity - Testing and validation

Answer

Problem Description

The Tower of Hanoi is a mathematical puzzle that consists of three rods and a number of disks of different sizes that can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, making a conical shape.

Rules: 1. Only one disk can be moved at a time 2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack 3. No larger disk may be placed on top of a smaller disk 4. The goal is to move all disks from the source rod to the destination rod using the auxiliary rod

Visual Example

For n=3 disks:

Initial State:        Step 1:            Step 2:            Step 3:
    |                   |                   |                   |
   ███                  |                   |                   |
  █████                 |                   |                   |
 ███████                |                   |                   |
--------+--------    -----+--------    -----+--------    -----+--------
   A        B            A        B            A        B            A        B

Implementation

1. Basic Recursive Solution

   public class TowerOfHanoi {
       public static void solve(int n, char source, char auxiliary, char destination) {
           if (n == 1) {
               System.out.printf("Move disk 1 from %c to %c%n", source, destination);
               return;
           }
   
           // Move n-1 disks from source to auxiliary using destination
           solve(n - 1, source, destination, auxiliary);
   
           // Move the nth disk from source to destination
           System.out.printf("Move disk %d from %c to %c%n", n, source, destination);
   
           // Move n-1 disks from auxiliary to destination using source
           solve(n - 1, auxiliary, source, destination);
       }
   
       public static void main(String[] args) {
           int n = 3; // Number of disks
           solve(n, 'A', 'B', 'C');
       }
   }
   

2. Enhanced Solution with Visualization

   public class TowerOfHanoiVisual {
       private static class Tower {
           private Stack<Integer> disks;
           private char name;
   
           public Tower(char name) {
               this.name = name;
               this.disks = new Stack<>();
           }
   
           public void add(int disk) {
               if (!disks.isEmpty() && disks.peek() <= disk) {
                   throw new IllegalStateException("Cannot place larger disk on smaller one");
               }
               disks.push(disk);
           }
   
           public int remove() {
               return disks.pop();
           }
   
           public void display() {
               System.out.printf("Tower %c: ", name);
               for (int disk : disks) {
                   System.out.print(disk + " ");
               }
               System.out.println();
           }
       }
   
       private Tower source, auxiliary, destination;
   
       public TowerOfHanoiVisual(int n) {
           source = new Tower('A');
           auxiliary = new Tower('B');
           destination = new Tower('C');
   
           // Initialize source tower with disks
           for (int i = n; i > 0; i--) {
               source.add(i);
           }
       }
   
       public void solve() {
           System.out.println("Initial state:");
           displayTowers();
           moveDisks(source.disks.size(), source, auxiliary, destination);
       }
   
       private void moveDisks(int n, Tower source, Tower auxiliary, Tower destination) {
           if (n == 1) {
               int disk = source.remove();
               destination.add(disk);
               System.out.printf("Move disk %d from %c to %c%n", 
                   disk, source.name, destination.name);
               displayTowers();
               return;
           }
   
           moveDisks(n - 1, source, destination, auxiliary);
   
           int disk = source.remove();
           destination.add(disk);
           System.out.printf("Move disk %d from %c to %c%n", 
               disk, source.name, destination.name);
           displayTowers();
   
           moveDisks(n - 1, auxiliary, source, destination);
       }
   
       private void displayTowers() {
           source.display();
           auxiliary.display();
           destination.display();
           System.out.println();
       }
   
       public static void main(String[] args) {
           TowerOfHanoiVisual puzzle = new TowerOfHanoiVisual(3);
           puzzle.solve();
       }
   }
   

Algorithm Explanation

1. Recursive Strategy

2. For n disks, the solution can be broken down into three steps:

   1. Move n-1 disks from source to auxiliary using destination
   2. Move the nth disk from source to destination
   3. Move n-1 disks from auxiliary to destination using source

3. Base case: When n=1, simply move the disk from source to destination

4. Example Execution (n=3)

   Initial State:
   Tower A: 3 2 1
   Tower B: 
   Tower C: 
   
   Step 1: Move 2 disks from A to B using C
   Tower A: 3
   Tower B: 2 1
   Tower C: 
   
   Step 2: Move disk 3 from A to C
   Tower A: 
   Tower B: 2 1
   Tower C: 3
   
   Step 3: Move 2 disks from B to C using A
   Tower A: 
   Tower B: 
   Tower C: 3 2 1
   

Complexity Analysis

1. Time Complexity: O(2^n)
2. Each recursive call generates two more recursive calls
3. Total number of moves = 2^n - 1

4. Example: n=3 requires 7 moves, n=4 requires 15 moves

5. Space Complexity: O(n)

6. Stack space used by recursive calls
7. Maximum depth of recursion is n
8. Each call uses constant space

Testing

public class TowerOfHanoiTest {
    @Test
    public void testTowerOfHanoi() {
        // Test with 1 disk
        TowerOfHanoiVisual puzzle1 = new TowerOfHanoiVisual(1);
        puzzle1.solve();

        // Test with 2 disks
        TowerOfHanoiVisual puzzle2 = new TowerOfHanoiVisual(2);
        puzzle2.solve();

        // Test with 3 disks
        TowerOfHanoiVisual puzzle3 = new TowerOfHanoiVisual(3);
        puzzle3.solve();

        // Test invalid input
        assertThrows(IllegalArgumentException.class, () -> 
            new TowerOfHanoiVisual(0));
    }
}

Best Practices

1. Input Validation

   public TowerOfHanoiVisual(int n) {
       if (n <= 0) {
           throw new IllegalArgumentException("Number of disks must be positive");
       }
       // ... rest of the implementation
   }
   

2. Error Handling

   public void add(int disk) {
       if (!disks.isEmpty() && disks.peek() <= disk) {
           throw new IllegalStateException(
               String.format("Cannot place disk %d on disk %d", disk, disks.peek()));
       }
       disks.push(disk);
   }
   

Applications and Variations

1. Real-world Applications
2. Used in computer science education to teach recursion
3. Basis for some memory management algorithms

4. Used in some parallel processing algorithms

5. Variations

6. Multiple pegs (more than 3)
7. Different movement rules
8. Circular arrangement
9. Restricted moves

Conclusion

• The Tower of Hanoi problem is an excellent example of recursive problem-solving
• The recursive solution is elegant but not the most efficient for large n
• The problem demonstrates important concepts like:
• Recursive thinking
• State management
• Problem decomposition
• Base case identification
• The solution can be extended to handle variations and real-world applications