11.4 – Towers of Hanoi – Recursion

by subbu on December 10, 2013

Towers of Hanoi:

It is a mathematical puzzle, is also called tower of Brahma or Lucas tower. It consists of three pegs or rods and number of disks of different sizes which can slide onto any peg.
At the beginning of the game, all the plates are arranged in ascending order on peg A that is smallest on top and biggest on bottom.
Towers of Honai - Wooden
The objective of this game is to move all disks from peg A to peg C using auxiliary peg B using some rules.

  1. Only one disk must be moved at a time
  2. Only top disk must be moved and placed only on top
  3. A disk can’t be placed on small disk
  4. Game must be completed within 2n-1 steps

Now let us play the game with two plates

Towers of Hanoi -2plates

Let us play the game with three plates now

Towers of Hanoi - 3plates

It is difficult to play the game as the number of plates grows. The recursive solution to towers of Hanoi is

tower(beg,end,aux,n-1)
beg->end
tower(aux,beg,end,n-1)

Equivalent implementation in C language is

void tower(char beg,char aux,char end,int n)
{
 if(n==0)
   return;
 tower(beg,end,aux,n-1);
 printf("\n%c -> %c",beg,end);
 tower(aux,beg,end,n-1);
}

Let us test it with 3 disks A, B and C

Towers of Hanoi - Recursion

#include<stdio.h>
void tower(char,char,char,int);
int main()
{
 int n;
 printf("nEnter number of plates:");
 scanf("%d",&n);
 tower('A','B','C',n);
 return 0;
}
void tower(char beg,char aux,char end,int n)
{
 if(n==0)
  return;
 tower(beg,end,aux,n-1);
 printf("\n%c -> %c",beg,end);
 tower(aux,beg,end,n-1);
}

Execution:
Enter number of plates:2
A -> B
A -> C
B -> C

Towers of Hanoi -2plates

Execution:
Enter number of plates:3
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

Towers of Hanoi - 3plates

Few words about origin:
Origin of this puzzle is an Indian temple called “Kashi Vishwanath” in India. The temple has a big room with three pegs and 64 golden plates. According to the rules of Brahma (God of creation), if any body completes the game then the last move of game would be the end of world.
Later a French mathematician “Edouard Lucas” in 1883 published the game in west. According to Lucas, it takes 264-1 seconds to complete the game if it takes 1 sec to move a plate, which is equal to 585 billion years.

Previous post:

Next post: