Tower of Hanoi Problem in DSA C#

Mental Model

Move disks one by one from one peg to another, never placing a bigger disk on a smaller one, until all disks reach the target peg.

Analogy: Imagine moving a stack of differently sized plates from one table to another using a third empty table, moving only one plate at a time and never putting a bigger plate on a smaller one.

Source: [3,2,1] ↑
Auxiliary: []
Target: []

Dry Run Walkthrough

Input: 3 disks on Source peg, move all to Target peg using Auxiliary peg

Goal: Move all disks from Source to Target following the rules

Step 1: Move disk 1 from Source to Target

Source: [3,2]
Auxiliary: []
Target: [1] ↑

Why: Smallest disk moves first to free bigger disks

Step 2: Move disk 2 from Source to Auxiliary

Source: [3]
Auxiliary: [2] ↑
Target: [1]

Why: Move next bigger disk to free the largest disk

Step 3: Move disk 1 from Target to Auxiliary

Source: [3]
Auxiliary: [2,1] ↑
Target: []

Why: Place smaller disk on Auxiliary to stack disks properly

Step 4: Move disk 3 from Source to Target

Source: []
Auxiliary: [2,1]
Target: [3] ↑

Why: Largest disk moves to Target as base

Step 5: Move disk 1 from Auxiliary to Source

Source: [1] ↑
Auxiliary: [2]
Target: [3]

Why: Free disk 2 by moving smaller disk back

Step 6: Move disk 2 from Auxiliary to Target

Source: [1]
Auxiliary: []
Target: [3,2] ↑

Why: Place disk 2 on top of largest disk

Step 7: Move disk 1 from Source to Target

Source: []
Auxiliary: []
Target: [3,2,1] ↑

Why: Place smallest disk on top to complete the stack

Result:

Source: []
Auxiliary: []
Target: [3,2,1] ↑

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class TowerOfHanoi
{
    static void MoveDisks(int n, string source, string target, string auxiliary, List<string> moves)
    {
        if (n == 1)
        {
            moves.Add($"Move disk 1 from {source} to {target}");
            return;
        }
        MoveDisks(n - 1, source, auxiliary, target, moves); // move n-1 disks to auxiliary
        moves.Add($"Move disk {n} from {source} to {target}"); // move nth disk to target
        MoveDisks(n - 1, auxiliary, target, source, moves); // move n-1 disks to target
    }

    static void Main()
    {
        int disks = 3;
        var moves = new List<string>();
        MoveDisks(disks, "Source", "Target", "Auxiliary", moves);
        foreach (var move in moves)
        {
            Console.WriteLine(move);
        }
    }
}

if (n == 1)

base case: move single disk directly

MoveDisks(n - 1, source, auxiliary, target, moves);

move top n-1 disks to auxiliary peg

moves.Add($"Move disk {n} from {source} to {target}");

move largest disk to target peg

MoveDisks(n - 1, auxiliary, target, source, moves);

move n-1 disks from auxiliary to target peg

Output

Move disk 1 from Source to Target

Move disk 2 from Source to Auxiliary

Move disk 1 from Target to Auxiliary

Move disk 3 from Source to Target

Move disk 1 from Auxiliary to Source

Move disk 2 from Auxiliary to Target

Move disk 1 from Source to Target

Complexity Analysis

Time: O(2^n) because each disk move doubles the number of moves needed

Space: O(n) due to recursion stack depth proportional to number of disks

vs Alternative: No simpler approach exists; this is the minimal number of moves required

Edge Cases

n = 1 (single disk)

Directly move the single disk from source to target

DSA C#

if (n == 1)

n = 0 (no disks)

No moves are made; function returns immediately

DSA C#

if (n == 0)

When to Use This Pattern

When you see a problem about moving stacked items with size rules and minimal moves, reach for the Tower of Hanoi pattern because it uses recursion to break down the problem.

Common Mistakes

Mistake: Trying to move more than one disk at once
Fix: Always move only one disk per step as per the rules

Mistake: Placing a bigger disk on a smaller disk
Fix: Check disk sizes before moving to ensure the bigger disk never goes on smaller

Summary

It solves moving disks between pegs following size and move rules.

Use it when you need to move stacked items with constraints on order and size.

The key insight is to move smaller stacks recursively to free the largest disk.

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