Tower Of Hanoi

In this tutorial we will learn to solve Tower of Hanoi using recursion.

About Tower Of Hanoi

Tower of Hanoi is a very famous game. In this game there are 3 pegs and N number of disks placed one over the other in decreasing size.

The objective of this game is to move the disks one by one from the first peg to the last peg. And there is only ONE condition, we can not place a bigger disk on top of a smaller disk.

How to solve Tower Of Hanoi?

To solve this game we will follow 3 simple steps recursively.

We will use a general notation:

T(N, Beg, Aux, End)

Where,
T denotes our procedure
N denotes the number of disks
Beg is the initial peg
Aux is the auxiliary peg
End is the final peg

Steps

Following are the recursive steps to solve Tower of Hanoi.

1. T(N-1, Beg, End, Aux)
2. T(1, Beg, Aux, End)
3. T(N-1, Aux, Beg, End)

Step 1 says: Move top (N-1) disks from Beg to Aux peg.
Step 2 says: Move 1 disk from Beg to End peg.
Step 3 says: Move top (N-1) disks from Aux to End peg.

Pseudo code

/*
N = Number of disks
Beg, Aux, End are the pegs
*/
T(N, Beg, Aux, End)
Begin
    if N = 1 then
        Print: Beg --> End;
    else
        Call T(N-1, Beg, End, Aux);
        Call T(1, Beg, Aux, End);
        Call T(N-1, Aux, Beg, End);
    endif
End

Moves required

If there are N disks then we can solve the game in minimum 2^N – 1 moves.

Example: N = 3

Minimum moves required = 23 – 1 = 7

Tower of Hanoi code in C

#include <stdio.h>

void t(int n, char beg, char aux, char end);

int main(){
  printf("Moves\n");
  t(3, 'a', 'b', 'c');  //N = 3 (no. of disks)  a, b, c are the three pegs
  return 0;
}//main() ends here

void t(int n, char beg, char aux, char end){
  if(n == 1){
    printf("%c --> %c\n", beg, end);
  }else{
    t(n-1, beg, end, aux);
    t(1, beg, aux, end);
    t(n-1, aux, beg, end);
  }
}//t() ends here