Tower of Hanoi Program in C

What is the Tower of Hanoi?

Tower of Hanoi is one of the main applications of recursion.

It says if you can solve n-1 cases, then you can solve the nth case.

It is also called as the Tower of Brahma or Lucas Tower.

It is a mathematical puzzle having applications in computer algorithms and programs as well as being used in psychology and medicine field as well.

Applications of Tower of Hanoi:

It has been used to determine the extent of brain injuries and helps to build/rebuild neural pathways in the brain as attempting to solve, Tower of Hanoi uses parts of the brain that involve managing time, foresight of whether the next move will lead us closer to the solution or not.

Psychologists use this to identify problem-solving skills of the subjects, which gives them insight as to how their minds are functioning and making decisions etc.

After so many interesting applications, aren’t you curious to know what is this problem and why is it so widely prevalent?
Without much ado, let’s dive into the problem and how to implement the same using C!

Problem Statement:

Given 3 towers/pegs/poles and n disks of decreasing sizes, move all the disks from one pole to another one without ever putting a larger disk on the smaller one.

The initial state of the puzzle is, when all the disks in the ascending order that is the smallest disk being on top is stacked on the first pole.

Rules of the puzzle:

The following rules are to be followed while solving this problem which makes it more challenging and interesting.

Only one disk can be moved at a time.
A larger disk cannot be placed on a smaller disk.
Each move involves, taking the disk at the top and placing it over another stack or empty pole.

Note:

If you have n disks, the minimum number of moves required to solve it is 2n – 1. If n =3, you will require 7 moves minimum.

Understanding the problem and solution:

In our case, let us take n = 3. Let us name the poles serially as A, B, C with A being the source pole and C being the destination. B will be used as a spare pole.

As seen above, we have moved the 3 disks following all the rules in the minimum number of steps for n = 3 which is 7.
The recursive task is to keep moving the disks from one pole to another pole.
Let us see how we shall arrive at our base case and the recursive case for our program.
As stated initially, our objective is to move all the disks placed on pole A – source pole to pole C – destination pole.

To transfer all disks from A to C, we would have to move the two upper disks i.e n-1 disks, from A to B which is the spare pole.
Now, once n-1 disks are placed on spare peg we can now move the largest/last i.e nth disk onto the destination pole C.
The last set of the task would involve moving disks from spare peg B to destination peg C.

Thus, our cases have been derived and they are as given below:

Pseudocode

Base case:
  if n == 1:
    Move the disk from A to C using B as spare.

Recursive case:
  Move n - 1 disks from A to B using C as spare.
  Move the nth disk from A to C using B as spare.
  Move the n - 1 disks from B to C using A as spare.

Tower of Hanoi program in C:

#include <stdio.h>

void TOH(int n, char x, char y, char z) {
  if (n > 0) {
    TOH(n - 1, x, z, y);
    printf("Move from %c to %c\n", x, y);
    TOH(n - 1, z, y, x);
  }
}

int main() {
  int n = 3;
  TOH(n, 'A', 'B', 'C');
  return 0;
}

Output:

Move from A to B 
Move from A to C 
Move from B to C 
Move from A to B 
Move from C to A 
Move from C to B 
Move from A to B