Past exam question: 2079 Ashwin (Back), Q5(a)
Open in the Padhaiko appQuestion
Write an algorithm for Tower of Hanoi (TOH) with 'n' disks.
Solution
Problem Formulation and Rules: The Tower of Hanoi (TOH) puzzle consists of three pegs: Source (), Destination (), and Auxiliary (), with disks of differing diameters initially stacked on in descending order of size.
The objective is to transfer all disks from peg to peg subject to three inviolable rules:
- Only one disk can be moved at any time.
- Only the uppermost disk from a peg may be picked up.
- No larger disk may ever be placed atop a smaller disk.
Recursive Strategy (Divide and Conquer): To transfer disks from to using as an auxiliary peg:
- Subproblem 1: Recursively move the top disks from to using as the auxiliary peg.
- Base Action: Move the remaining -th (largest) disk directly from to .
- Subproblem 2: Recursively move the disks from to using as the auxiliary peg.
Base Case: If , move the single disk directly from to and terminate.
Formal Recursive Algorithm:
Algorithm TOH(n, Source, Destination, Auxiliary):
1. [Base Case: Single Disk]
If n == 1:
Print "Move disk 1 from " + Source + " to " + Destination
Return
2. [Recurse: Move n-1 disks from Source to Auxiliary]
Call TOH(n - 1, Source, Auxiliary, Destination)
3. [Direct Move: Move the largest n-th disk to Destination]
Print "Move disk " + n + " from " + Source + " to " + Destination
4. [Recurse: Move n-1 disks from Auxiliary to Destination]
Call TOH(n - 1, Auxiliary, Destination, Source)
5. ReturnComplexity Analysis:
- Recurrence Relation:
- Number of Moves:
- Time Complexity: (exponential).
- Space Complexity: auxiliary space on the call stack due to recursion depth of .
Answer:
The recursive Tower of Hanoi algorithm:
void TOH(int n, char S, char D, char A) {
if (n == 1) {
printf("Move disk 1 from %c to %c\n", S, D);
return;
}
TOH(n - 1, S, A, D);
printf("Move disk %d from %c to %c\n", n, S, D);
TOH(n - 1, A, D, S);
}
Requires exactly moves, running in time and stack space.