Tower of Hanoi Problem in DSA Java - Build from Scratch

Tower of Hanoi Problem

📖 Scenario: Imagine you have three pegs and a stack of disks of different sizes on the first peg. Your goal is to move all the disks to the third peg, following the rule that you can only move one disk at a time and never place a larger disk on top of a smaller one.

🎯 Goal: You will write a Java program that solves the Tower of Hanoi problem for 3 disks. The program will print the steps to move the disks from the first peg to the third peg.

📋 What You'll Learn

Create a method to print the moves

Use recursion to solve the problem

Print each move in the format: "Move disk X from peg Y to peg Z"

💡 Why This Matters

🌍 Real World

The Tower of Hanoi problem helps understand recursion, which is used in many real-world algorithms like file system traversal and puzzle solving.

💼 Career

Understanding recursion and problem-solving techniques like Tower of Hanoi is important for software development, algorithm design, and technical interviews.

1

Create the main class and method

Create a public class called TowerOfHanoi with a main method. Inside main, declare an integer variable numberOfDisks and set it to 3.

DSA Java

public class TowerOfHanoi {
    public static void main(String[] args) {
        // Your code here
    }
}

Hint

Start by creating the class and main method. Then declare numberOfDisks as 3.

2

Add the recursive method signature

Inside the TowerOfHanoi class but outside the main method, create a public static method called solveHanoi that takes four parameters: int n, char fromPeg, char toPeg, and char auxPeg. Leave the method body empty for now.

DSA Java

public class TowerOfHanoi {
    public static void main(String[] args) {
        int numberOfDisks = 3;
    }

    // Your code here
}

Hint

Define the method solveHanoi with the correct parameters and return type.

3

Implement the recursive logic

Inside the solveHanoi method, write the recursive logic: if n == 1, print "Move disk 1 from peg " + fromPeg + " to peg " + toPeg. Otherwise, call solveHanoi to move n-1 disks from fromPeg to auxPeg using toPeg as auxiliary, then print the move for disk n, then call solveHanoi to move n-1 disks from auxPeg to toPeg using fromPeg as auxiliary.

DSA Java

public class TowerOfHanoi {
    public static void main(String[] args) {
        int numberOfDisks = 3;
    }

    public static void solveHanoi(int n, char fromPeg, char toPeg, char auxPeg) {
        // Your code here
    }
}

Hint

Use the recursive pattern: move n-1 disks, move the nth disk, then move n-1 disks again.

4

Call the recursive method and print the moves

Inside the main method, call solveHanoi with numberOfDisks, 'A' as fromPeg, 'C' as toPeg, and 'B' as auxPeg. This will print the steps to move the disks.

DSA Java

public class TowerOfHanoi {
    public static void main(String[] args) {
        int numberOfDisks = 3;
        // Your code here
    }

    public static void solveHanoi(int n, char fromPeg, char toPeg, char auxPeg) {
        if (n == 1) {
            System.out.println("Move disk 1 from peg " + fromPeg + " to peg " + toPeg);
            return;
        }
        solveHanoi(n - 1, fromPeg, auxPeg, toPeg);
        System.out.println("Move disk " + n + " from peg " + fromPeg + " to peg " + toPeg);
        solveHanoi(n - 1, auxPeg, toPeg, fromPeg);
    }
}

Hint

Call solveHanoi with the correct arguments to start the process.

Practice

1. What is the minimum number of moves required to solve the Tower of Hanoi problem with 3 disks?

easy

A. 9

B. 6

C. 8

D. 7

Solution

1. Step 1: Understand the formula for minimum moves

   The minimum moves required for n disks is 2^n - 1.

2. Step 2: Calculate for 3 disks

   For 3 disks, minimum moves = 2^3 - 1 = 8 - 1 = 7.

3. Final Answer:

   7 -> Option D

4. Quick Check:

   2^3 - 1 = 7 [OK]

Hint: Use formula 2^n - 1 for minimum moves [OK]

Common Mistakes:

• Using n instead of 2^n - 1
• Calculating 2*n - 1 instead of 2^n - 1
• Confusing number of disks with moves

2. Which of the following is the correct base case condition in a recursive Tower of Hanoi function in Java?

easy

A. if (n < 0) return;

B. if (n == 1) return;

C. if (n == 0) return;

D. if (n > 1) return;

Solution

1. Step 1: Identify base case for recursion

   Base case stops recursion when no disks are left to move, i.e., n == 0.

2. Step 2: Check each option

   if (n == 0) return; correctly returns when n == 0, stopping recursion.

3. Final Answer:

   if (n == 0) return; -> Option C

4. Quick Check:

   Base case is n == 0 [OK]

Hint: Base case stops recursion at zero disks [OK]

Common Mistakes:

• Using n == 1 as base case which causes extra calls
• Using negative values as base case
• Returning when n > 1 which stops too early

3. What will be the output sequence of moves for Tower of Hanoi with 2 disks from source A to destination C using auxiliary B?

medium

A. Move disk 1 from A to B\nMove disk 2 from A to C\nMove disk 1 from B to C

B. Move disk 2 from A to B\nMove disk 1 from A to C\nMove disk 2 from B to C

C. Move disk 1 from A to C\nMove disk 2 from A to B\nMove disk 1 from C to B

D. Move disk 2 from A to C\nMove disk 1 from B to A\nMove disk 2 from C to B

Solution

1. Step 1: Understand move sequence for 2 disks

   Move smaller disk 1 from source A to auxiliary B.

2. Step 2: Move larger disk 2 from source A to destination C, then move disk 1 from B to C

   This completes the transfer following rules.

3. Final Answer:

   Move disk 1 from A to B\nMove disk 2 from A to C\nMove disk 1 from B to C -> Option A

4. Quick Check:

   Correct move order for 2 disks [OK]

Hint: Move smaller disk first to auxiliary, then largest to destination [OK]

Common Mistakes:

• Swapping disk numbers in moves
• Moving larger disk before smaller disk
• Incorrect order of moves

4. Identify the error in this Tower of Hanoi recursive function snippet:

void towerOfHanoi(int n, char from, char to, char aux) {
  if (n == 1) {
    System.out.println("Move disk 1 from " + from + " to " + to);
    return;
  }
  towerOfHanoi(n - 1, from, aux, to);
  System.out.println("Move disk " + n + " from " + from + " to " + to);
  towerOfHanoi(n - 1, aux, to, from);
}

medium

A. Base case should be if (n == 0) instead of if (n == 1)

B. There is no error; the function is correct

C. The print statement should be before the first recursive call

D. The order of parameters in recursive calls is incorrect

Solution

1. Step 1: Analyze base case correctness

   Base case n == 1 means move the single disk directly, which is correct.

2. Step 2: Check recursive calls and print order

   First move n-1 disks from source to auxiliary, then move nth disk, then move n-1 disks from auxiliary to destination. This matches the Tower of Hanoi logic.

3. Final Answer:

   There is no error; the function is correct -> Option B

4. Quick Check:

   Function matches Tower of Hanoi recursion [OK]

Hint: Check base case and recursive call order carefully [OK]

Common Mistakes:

• Changing base case to n == 0 causing infinite recursion
• Swapping parameters in recursive calls
• Moving print statement incorrectly

5. If the Tower of Hanoi problem has 4 disks, what is the total number of moves and what is the move sequence for the first two moves from source A to destination C using auxiliary B?

hard

A. Total moves: 15\nFirst move: Move disk 1 from A to B\nSecond move: Move disk 2 from A to C

B. Total moves: 14\nFirst move: Move disk 1 from A to B\nSecond move: Move disk 2 from B to C

C. Total moves: 16\nFirst move: Move disk 1 from A to B\nSecond move: Move disk 2 from A to C

D. Total moves: 15\nFirst move: Move disk 1 from A to C\nSecond move: Move disk 2 from A to B

Solution

1. Step 1: Calculate total moves for 4 disks

   Total moves = 2^4 - 1 = 16 - 1 = 15 moves.

2. Step 2: Determine first two moves in sequence

   First move: Move smallest disk 1 from A to B (auxiliary). Second move: Move disk 2 from A to C (destination).

3. Final Answer:

   Total moves: 15\nFirst move: Move disk 1 from A to B\nSecond move: Move disk 2 from A to C -> Option A

4. Quick Check:

   2^4 - 1 = 15 and correct first moves [OK]

Hint: Use formula for moves and remember smallest disk moves first [OK]

Common Mistakes:

• Incorrect total moves calculation
• Swapping first two moves
• Confusing auxiliary and destination rods