Friday, November 25, 2011

Analysis of Tower of Hanoi Problem with Algorithm and Source code in C/C++

The Towers of Hanoi is well-known game, played with three poles and a number of different-sized disks. Each disk has a hole in the center, allowing it to be stacked around any of the poles. Initially, the disks are stacked on the leftmost pole in the order of decreasing size, i.e., the largest on the bottom and the smallest on the top, as shown in the figure below.TOH copy

The objective of the game is to transfer the disks from the leftmost pole to the rightmost pole, without ever placing a larger disk, on the top of a smaller disk. Only one disk may be moved at a time, and each disk must always be placed around one of the poles. The general strategy is to consider one of the poles to be the origin, and another to be the destination. The third pole will be used for intermediate storage, thus allowing the disks to be moved without placing a larger disk over a smaller disk. Assume there are n disks, numbered from smallest to largest, as above figure. If th disks are initially stacked on the left pole, the problem of moving all n disks to the right pole can be started using following Algorithm.


1. Declare necessary variables such as n, A, B, C etc.
2. Input number of disks
3. If n=1
move single disk from peg A to peg C and stop.
move the top (n-1) disks from peg A to peg B using peg C as auxiliary.
4. Move remaining disks from peg A to peg C.
5. Move (n-1) disks from peg B to peg C using peg A as auxiliary

Source Code

void transfer(int n, char from, char to, char temp);
int main(){
    int n;
    printf("How many disks? ");
    scanf("%d", &n);
    return 0;
void transfer(int n, char from, char to, char temp){
    /** n = number of disks
        from = orinin
        to = destination
        temp = temporary storage  **/
        /** move n-1 disks from origin to temporary **/
        transfer(n-1, from, temp, to);
        /** move nth disk from origin to destination **/
        printf("Move disk %d from %c to %c\n", n, from, to);
        /** move n-1 disks from temporary to destination **/
        transfer(n-1, temp, to, from);



How many disks? 3

Move disk 1 from L to R
Move disk 2 from L to C
Move disk 1 from R to C
Move disk 3 from L to R
Move disk 1 from C to L
Move disk 2 from C to R
Move disk 1 from L to R