Justin's Words

Tower of Hanoi Algorithm

Posted on | In |

What exactly is the Tower of Hanoi, here is the explanation from Tower of Hanoi:

The Tower of Hanoi is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

  1. Only one disk can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
  3. No disk may be placed on top of a smaller disk.

An animated solution shows it:

[caption id=”” align=”alignnone” width=”300”]Tower of Hanoi Tower of Hanoi animated solution[/caption]

We can solve the puzzle by programming. In fact, the puzzle of the Tower of Hanoi is usually used to illustrate recursion in programming. Below is a solution from yusufshakeel:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* tower of hanoi
 * author: yusuf shakeel
 * date: 20-12-2012
 */

#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