The Tower of Hanoi is a classic recursive problem in computer science. It involves moving a set of disks from one rod to another, following specific rules: only one disk can be moved at a time, and a larger disk cannot be placed on top of a smaller disk. This problem is widely used to teach recursion, problem-solving strategies, and algorithm design.
Understanding the Problem
The main challenge is moving all disks from the source rod to the destination rod using an auxiliary rod while following the rules. The problem can be broken down recursively: move the top n-1 disks to the auxiliary rod, move the largest disk to the destination, and finally move the n-1 disks from auxiliary to destination. Recursive thinking is essential to implement this efficiently.
Program 1: Tower of Hanoi (Recursive)
This program demonstrates a recursive solution to the Tower of Hanoi problem, showing all the moves required to transfer disks from the source rod to the destination rod.
#include <stdio.h>
void towerOfHanoi(int n, char source, char auxiliary, char destination) {
if (n == 1) {
printf("Move disk 1 from %c to %c\n", source, destination);
return;
}
towerOfHanoi(n - 1, source, destination, auxiliary);
printf("Move disk %d from %c to %c\n", n, source, destination);
towerOfHanoi(n - 1, auxiliary, source, destination);
}
int main() {
int n;
printf("Enter the number of disks: ");
scanf("%d", &n);
printf("The steps to solve Tower of Hanoi for %d disks are:\n", n);
towerOfHanoi(n, 'A', 'B', 'C');
return 0;
}The towerOfHanoi function solves the problem recursively. When there is only one disk, it moves it directly to the destination. For more than one disk, it first moves n-1 disks to the auxiliary rod, then moves the largest disk to the destination rod, and finally moves the n-1 disks from the auxiliary rod to the destination rod. This elegant recursive approach captures the essence of the Tower of Hanoi problem with minimal code while clearly showing each move.
Program 2: Tower of Hanoi (Iterative Using Stack)
This program solves the Tower of Hanoi problem iteratively. It simulates the recursive moves using stacks to represent the rods.
#include <stdio.h>
#include <stdlib.h>
typedef struct Stack {
int *arr;
int top;
int capacity;
} Stack;
// Create a stack
Stack* createStack(int capacity) {
Stack *stack = (Stack*) malloc(sizeof(Stack));
stack->capacity = capacity;
stack->top = -1;
stack->arr = (int*) malloc(capacity * sizeof(int));
return stack;
}
// Push a disk onto the stack
void push(Stack *stack, int disk) {
stack->arr[++stack->top] = disk;
}
// Pop a disk from the stack
int pop(Stack *stack) {
if (stack->top == -1) return -1;
return stack->arr[stack->top--];
}
// Move a disk between two rods
void moveDisk(Stack *fromRod, Stack *toRod, char from, char to) {
int fromTop = pop(fromRod);
int toTop = pop(toRod);
if (fromTop == -1) {
push(fromRod, toTop);
printf("Move disk %d from %c to %c\n", toTop, to, from);
} else if (toTop == -1) {
push(toRod, fromTop);
printf("Move disk %d from %c to %c\n", fromTop, from, to);
} else if (fromTop > toTop) {
push(fromRod, fromTop);
push(fromRod, toTop);
printf("Move disk %d from %c to %c\n", toTop, to, from);
} else {
push(toRod, toTop);
push(toRod, fromTop);
printf("Move disk %d from %c to %c\n", fromTop, from, to);
}
}
// Iterative Tower of Hanoi
void towerOfHanoiIterative(int n, char A, char B, char C) {
Stack *src = createStack(n);
Stack *aux = createStack(n);
Stack *dest = createStack(n);
for (int i = n; i >= 1; i--) push(src, i);
int totalMoves = (1 << n) - 1;
char s = A, d = C, a = B;
if (n % 2 == 0) {
char temp = d;
d = a;
a = temp;
}
for (int i = 1; i <= totalMoves; i++) {
if (i % 3 == 1) moveDisk(src, dest, s, d);
else if (i % 3 == 2) moveDisk(src, aux, s, a);
else if (i % 3 == 0) moveDisk(aux, dest, a, d);
}
free(src->arr); free(src);
free(aux->arr); free(aux);
free(dest->arr); free(dest);
}
int main() {
int n;
printf("Enter the number of disks: ");
scanf("%d", &n);
printf("The steps to solve Tower of Hanoi iteratively for %d disks are:\n", n);
towerOfHanoiIterative(n, 'A', 'B', 'C');
return 0;
}This iterative solution uses three stacks to represent the rods and calculates the total moves as 2^n - 1. Disks are moved according to a fixed sequence that simulates the recursive pattern. Even-numbered disks require swapping the auxiliary and destination rods to maintain the correct order. This approach avoids recursion entirely, making it suitable for situations where deep recursion could cause stack overflow.
FAQs
Q1: What is the minimum number of moves required for n disks?
The minimum number of moves is 2^n - 1.
Q2: Can Tower of Hanoi be solved iteratively?
Yes, there is an iterative solution using a stack, but recursion is more intuitive.
Q3: What is the time complexity?
O(2^n), exponential in the number of disks.
Q4: Why is Tower of Hanoi important in programming?
It teaches recursion, problem decomposition, and algorithmic thinking.
Conclusion
The Tower of Hanoi problem is a classic example demonstrating recursion in computer science. Understanding and implementing this algorithm helps develop problem-solving skills and recursive thinking.
References & Additional Resources
A curated list of books and online resources providing theoretical foundations and practical examples for understanding recursion and the Tower of Hanoi problem in C.
- Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language, 2nd Edition. Prentice Hall – Classic reference on C fundamentals, including recursion, pointers, and memory management.
- Thareja, R. (2011). Data Structures Using C. Oxford University Press – Covers recursive algorithms, problem-solving techniques, and C implementations.
- GeeksforGeeks: Tower of Hanoi – Step-by-step explanation and C code for solving the Tower of Hanoi problem.
- Programiz: Recursion in C – Detailed guide to recursion with examples in C.
- Tutorialspoint: Tower of Hanoi Animation and Explanation – Visual explanation and recursive solution walkthrough.
