Problem Description

The Tower of Hanoi is a classic mathematical puzzle. The setup consists of three pegs and a number of disks of different sizes. Initially, all disks are stacked on the first peg in order of size, with the largest at the bottom and smallest at the top. The objective is to move the entire stack to another peg, following these rules:

• Only one disk can be moved at a time
• Each move consists of taking the top disk from one peg and placing it on another
• No disk may be placed on top of a smaller disk

Recursive Approach

The solution becomes clear when we think recursively. To move n disks from source to destination:

1. Move n-1 disks from source to auxiliary peg
2. Move the largest disk from source to destination
3. Move n-1 disks from auxiliary to destination

The base case occurs when n equals 1, requiring only a single move.

Implementation

#include <stdio.h>

void moveDisk(char source, char target);
void solveHanoi(int diskCount, char source, char destination, char auxiliary);

int main()
{
    int diskCount = 4;
    solveHanoi(diskCount, 'A', 'C', 'B');
    return 0;
}

void solveHanoi(int n, char src, char dst, char aux)
{
    if (n == 1)
    {
        moveDisk(src, dst);
        return;
    }
    solveHanoi(n - 1, src, aux, dst);
    moveDisk(src, dst);
    solveHanoi(n - 1, aux, dst, src);
}

void moveDisk(char from, char to)
{
    printf("%c -> %c\n", from, to);
}

Alternative Implementation with Step Tracking

#include <stdio.h>

#define TOTAL_DISKS 4

void displayState(int src[], int aux[], int dst[]);
void hanoiRecursive(int count, int src[], int dst[], int aux[]);
void swap(int *x, int *y);

int main()
{
    int source[TOTAL_DISKS + 1] = {0};
    int auxiliary[TOTAL_DISKS + 1] = {0};
    int destination[TOTAL_DISKS + 1] = {0};
    
    for (int i = 1; i <= TOTAL_DISKS; i++)
    {
        source[i] = i;
    }
    
    printf("Initial state:\n");
    displayState(source, auxiliary, destination);
    
    hanoiRecursive(TOTAL_DISKS, source, destination, auxiliary);
    
    return 0;
}

void hanoiRecursive(int n, int src[], int dst[], int aux[])
{
    if (n == 1)
    {
        swap(&src[1], &dst[1]);
        displayState(src, aux, dst);
        return;
    }
    
    hanoiRecursive(n - 1, src, aux, dst);
    swap(&src[n], &dst[n]);
    displayState(src, aux, dst);
    hanoiRecursive(n - 1, aux, dst, src);
}

void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

void displayState(int s[], int a[], int d[])
{
    for (int i = 1; i <= TOTAL_DISKS; i++)
    {
        printf("%d ", s[i]);
    }
    printf(" | ");
    for (int i = 1; i <= TOTAL_DISKS; i++)
    {
        printf("%d ", a[i]);
    }
    printf(" | ");
    for (int i = 1; i <= TOTAL_DISKS; i++)
    {
        printf("%d ", d[i]);
    }
    printf("\n");
}

Analysis

The recursive solution has a time complexity of O(2^n), as the number of moves required equals 2^n - 1. For 64 disks, this equals approximately 18.4 quintillion moves, which explains why the legend suggests the world would end after completion.

The space complexity is O(n) due to the recursive call stack, where n represents the number of disks.

Output Format

Each line displays the three pegs separated by vertical bars, showing disk positions after every move. The value at each position indicates which disk occupies that slot (0 means empty).