Tower of Hanoi Problem in DSA C# - Build from Scratch

Tower of Hanoi Problem

📖 Scenario: Imagine you have three rods and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks neatly stacked in ascending order of size on one rod, the smallest at the top, making a conical shape.Your task is to move the entire stack to another rod, obeying the following simple rules:Only one disk can be moved at a time.Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.No disk may be placed on top of a smaller disk.

🎯 Goal: You will write a program in C# that prints the steps to solve the Tower of Hanoi problem for 3 disks. The program will show which disk moves from which rod to which rod, step by step.

📋 What You'll Learn

Create an integer variable numberOfDisks and set it to 3.

Create a method MoveDisks that takes four parameters: int n, char fromRod, char toRod, and char auxRod.

Implement the recursive logic inside MoveDisks to print the moves.

Call the MoveDisks method from Main with the correct arguments.

Print each move in the format: Move disk {diskNumber} from {fromRod} to {toRod}.

💡 Why This Matters

🌍 Real World

The Tower of Hanoi problem helps understand recursion, a key concept in programming and problem solving.

💼 Career

Recursion and problem decomposition are important skills for software developers, especially in algorithm design and optimization.

1

Create the number of disks variable

Create an integer variable called numberOfDisks and set it to 3.

DSA C#

# Create an integer variable called numberOfDisks and set it to 3
// Your code here

Hint

Use int numberOfDisks = 3; inside the Main method.

2

Define the MoveDisks method signature

Define a static method called MoveDisks that takes four parameters: int n, char fromRod, char toRod, and char auxRod. The method should return void.

DSA C#

using System;

class Program
{
    static void Main()
    {
        int numberOfDisks = 3;
    }

    // Define the MoveDisks method with parameters int n, char fromRod, char toRod, char auxRod
    // Your code here
}

Hint

Write the method header exactly as static void MoveDisks(int n, char fromRod, char toRod, char auxRod).

3

Implement the recursive logic inside MoveDisks

Inside the MoveDisks method, implement the recursive logic to solve the Tower of Hanoi problem for n disks. Use an if statement to check if n == 1. If yes, print Move disk 1 from {fromRod} to {toRod}. Otherwise, recursively call MoveDisks to move n-1 disks from fromRod to auxRod, then print the move of disk n from fromRod to toRod, and finally move n-1 disks from auxRod to toRod.

DSA C#

using System;

class Program
{
    static void Main()
    {
        int numberOfDisks = 3;
    }

    static void MoveDisks(int n, char fromRod, char toRod, char auxRod)
    {
        // Implement the recursive Tower of Hanoi logic here
        // Your code here
    }
}

Hint

Use recursion with base case if (n == 1) and recursive calls to move disks.

4

Call MoveDisks and print the solution

In the Main method, call the MoveDisks method with numberOfDisks, 'A' as the source rod, 'C' as the destination rod, and 'B' as the auxiliary rod. This will print the steps to solve the Tower of Hanoi problem.

DSA C#

using System;

class Program
{
    static void Main()
    {
        int numberOfDisks = 3;
        // Call MoveDisks with numberOfDisks, 'A', 'C', 'B'
        // Your code here
    }

    static void MoveDisks(int n, char fromRod, char toRod, char auxRod)
    {
        if (n == 1)
        {
            Console.WriteLine($"Move disk 1 from {fromRod} to {toRod}");
            return;
        }
        MoveDisks(n - 1, fromRod, auxRod, toRod);
        Console.WriteLine($"Move disk {n} from {fromRod} to {toRod}");
        MoveDisks(n - 1, auxRod, toRod, fromRod);
    }
}

Hint

Call MoveDisks(numberOfDisks, 'A', 'C', 'B'); inside Main.

Practice

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

easy

A. 6

B. 7

C. 8

D. 9

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 B

4. Quick Check:

   2^3 - 1 = 7 [OK]

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

Common Mistakes:

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

2. Which of the following is the correct C# method signature for a recursive Tower of Hanoi function?

easy

A. void TowerOfHanoi(int n, string fromRod, string toRod)

B. int TowerOfHanoi(int n, char fromRod, char toRod, char auxRod)

C. int TowerOfHanoi(int n, string fromRod, string toRod, string auxRod)

D. void TowerOfHanoi(int n, char fromRod, char toRod, char auxRod)

Solution

1. Step 1: Identify correct parameter types

   The Tower of Hanoi function typically uses integer for disk count and characters for rods.

2. Step 2: Check return type and parameters

   The function usually returns void and takes 3 rods as char parameters plus disk count as int.

3. Final Answer:

   void TowerOfHanoi(int n, char fromRod, char toRod, char auxRod) -> Option D

4. Quick Check:

   Correct signature uses void and char rods [OK]

Hint: Use void return and char for rods in signature [OK]

Common Mistakes:

• Using string instead of char for rods
• Returning int instead of void
• Missing auxiliary rod parameter

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

medium

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

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

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

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

Solution

1. Step 1: Understand the recursive move sequence for 2 disks

   Move smaller disk 1 to auxiliary rod B, then move disk 2 to target rod C, then move disk 1 from B to C.

2. Step 2: Verify the move order

   Sequence is: 1 from A to B, 2 from A to C, 1 from B to C.

3. Final Answer:

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

4. Quick Check:

   Correct move order for 2 disks [OK]

Hint: For 2 disks, move smaller disk first to aux rod [OK]

Common Mistakes:

• Swapping disk numbers in moves
• Confusing auxiliary and target rods
• Reversing move order

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

void Hanoi(int n, char from, char to, char aux) {
  if (n == 0) return;
  Hanoi(n - 1, from, aux, to);
  Console.WriteLine($"Move disk {n} from {from} to {to}");
  Hanoi(n - 1, aux, to, from);
}

medium

A. Base case should be if (n == 1) return;

B. Recursive calls have wrong rod order in parameters

C. No error, code is correct

D. Console.WriteLine should print disk n-1 instead of n

Solution

1. Step 1: Check base case correctness

   Base case n == 0 means no disks to move, which is correct to stop recursion.

2. Step 2: Verify recursive calls and print statement

   Recursive calls correctly move n-1 disks between rods, and print statement moves disk n from 'from' to 'to'.

3. Final Answer:

   No error, code is correct -> Option C

4. Quick Check:

   Base case and recursion are correctly implemented [OK]

Hint: Base case n==0 is correct to stop recursion [OK]

Common Mistakes:

• Changing base case to n==1 incorrectly
• Mixing up rod parameters in recursive calls
• Printing wrong disk number

5. You want to solve Tower of Hanoi for 4 disks but print only the moves where disk 1 is moved. How many such moves will be printed?

hard

A. 8

B. 15

C. 7

D. 4

Solution

1. Step 1: Calculate total moves for 4 disks

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

2. Step 2: Count moves involving disk 1

   Disk 1 moves every alternate move, so number of moves = (total moves + 1) / 2 = (15 + 1)/2 = 8.

3. Final Answer:

   8 -> Option A

4. Quick Check:

   Disk 1 moves half the times plus one [OK]

Hint: Disk 1 moves on every alternate move, count half plus one [OK]

Common Mistakes:

• Assuming disk 1 moves equal to total moves
• Using total moves minus one
• Confusing disk 1 moves with total disks