C# Program for Tower of Hanoi Puzzle Solution

A C# program for Tower of Hanoi uses a recursive method like void TowerOfHanoi(int n, char from, char to, char aux) to move disks between rods, printing each move until all disks are moved.

Examples

Inputn = 1

OutputMove disk 1 from rod A to rod C

Inputn = 3

OutputMove disk 1 from rod A to rod C Move disk 2 from rod A to rod B Move disk 1 from rod C to rod B Move disk 3 from rod A to rod C Move disk 1 from rod B to rod A Move disk 2 from rod B to rod C Move disk 1 from rod A to rod C

Inputn = 0

Output

How to Think About It

To solve Tower of Hanoi, think of moving n disks from one rod to another using a helper rod. Move the top n-1 disks to the helper rod first, then move the largest disk to the target rod, and finally move the n-1 disks from the helper rod to the target rod. This repeats until no disks remain.

Algorithm

1

If number of disks n is 1, move the disk directly from source to target rod.

2

Otherwise, move n-1 disks from source rod to auxiliary rod using target rod as helper.

3

Move the nth (largest) disk from source rod to target rod.

4

Move the n-1 disks from auxiliary rod to target rod using source rod as helper.

Code

csharp

using System;
class Program {
    static void TowerOfHanoi(int n, char from, char to, char aux) {
        if (n == 1) {
            Console.WriteLine($"Move disk 1 from rod {from} to rod {to}");
            return;
        }
        TowerOfHanoi(n - 1, from, aux, to);
        Console.WriteLine($"Move disk {n} from rod {from} to rod {to}");
        TowerOfHanoi(n - 1, aux, to, from);
    }
    static void Main() {
        int n = 3;
        TowerOfHanoi(n, 'A', 'C', 'B');
    }
}

Output

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

Dry Run

Let's trace moving 2 disks from rod A to rod C using rod B as helper.

1

Move top disk from A to B

Call TowerOfHanoi(1, 'A', 'B', 'C') prints: Move disk 1 from rod A to rod B

2

Move largest disk from A to C

Prints: Move disk 2 from rod A to rod C

3

Move disk from B to C

Call TowerOfHanoi(1, 'B', 'C', 'A') prints: Move disk 1 from rod B to rod C

Call	Action
TowerOfHanoi(1, A, B, C)	Move disk 1 from rod A to rod B
Print move disk 2 from rod A to rod C	Move disk 2 from rod A to rod C
TowerOfHanoi(1, B, C, A)	Move disk 1 from rod B to rod C

Why This Works

Step 1: Base case moves one disk

When n == 1, the program moves the disk directly from the source rod to the target rod and prints the move.

Step 2: Recursive calls break problem down

The program moves n-1 disks to the auxiliary rod first, then moves the largest disk, then moves the n-1 disks to the target rod.

Step 3: Print statements show moves

Each move is printed so you can see the exact steps to solve the puzzle.

Alternative Approaches

Iterative approach using stack

csharp

using System;
using System.Collections.Generic;
class Program {
    static void Main() {
        int n = 3;
        Stack<(int, char, char, char)> stack = new Stack<(int, char, char, char)>();
        stack.Push((n, 'A', 'C', 'B'));
        while (stack.Count > 0) {
            var (disks, from, to, aux) = stack.Pop();
            if (disks == 1) {
                Console.WriteLine($"Move disk 1 from rod {from} to rod {to}");
            } else {
                stack.Push((disks - 1, aux, to, from));
                stack.Push((1, from, to, aux));
                stack.Push((disks - 1, from, aux, to));
            }
        }
    }
}

Uses a stack to simulate recursion; more complex but avoids function call overhead.

Using bitwise operations for move calculation

csharp

using System;
class Program {
    static void Main() {
        int n = 3;
        int totalMoves = (1 << n) - 1;
        char[] rods = { 'A', 'B', 'C' };
        for (int i = 1; i <= totalMoves; i++) {
            int from = (i & (i - 1)) % 3;
            int to = ((i | (i - 1)) + 1) % 3;
            Console.WriteLine($"Move disk from rod {rods[from]} to rod {rods[to]}");
        }
    }
}

Calculates moves without recursion but harder to understand; good for optimization.

Complexity: O(2^n) time, O(n) space

Time Complexity

The algorithm makes 2^n - 1 moves, so time grows exponentially with the number of disks.

Space Complexity

The recursion stack grows up to n calls deep, so space is O(n).

Which Approach is Fastest?

Recursive approach is simplest and clear; iterative and bitwise methods can be faster but are more complex.

Approach	Time	Space	Best For
Recursive	O(2^n)	O(n)	Clarity and simplicity
Iterative with stack	O(2^n)	O(n)	Avoiding recursion overhead
Bitwise calculation	O(2^n)	O(1)	Optimized move calculation