//##############################################################
// This is a solution to the tower of hanoi problem.
//##############################################################
#include <stdio.h>

#define MAX_DISKS 9

int Towers[3][MAX_DISKS];
int Ndisks[3];  // number of disks in each tower
int Moves;

void print_towers();
void toh (int n, int a, int b, int c);

int main() {

    int n, i;

    do {
        printf("Enter number of disks (between 1 and %d): ", MAX_DISKS);
        scanf ("%d",&n);
    } while(n<1 || n > MAX_DISKS);

    for(i=0; i<n; i++) {
        Towers[0][i] = n-i;
        Towers[1][i] = 0;
        Towers[2][i] = 0;
    }

    Ndisks[0] = n;
    Ndisks[1] = 0;
    Ndisks[2] = 0;

    printf("Initial state of towers:\n");
    print_towers();

    Moves = 0;
    toh(n, 0, 1, 2);
    printf("\n\nTotal moves: %d\n", Moves);
    return 0;
}

//==============================================================
// move n disks from tower a to b, using c for intermediate storage
// This is achieved by:
// 1. move the top n-1 disks from a to c
// 2. move the last disk from a to b
// 3. move the n-1 disks from c to b
//==============================================================
void toh (int n, int a, int b, int c)
{
    if (n > 0) {
        //1. move the top n-1 disks from a to c
        // Here we recursively call toh to do it.
	      toh (n-1, a, c, b);

        //2. move the remaining disk from a to b
	      printf ("Move a disk from %d to %d\n", a+1, b+1);
        Towers[b][Ndisks[b]] = Towers[a][Ndisks[a]-1];
        Ndisks[a]--;
        Ndisks[b]++;
        print_towers();
        Moves++;

        //3. move the n-1 disks from c to b
	      toh (n-1, c, b, a);
    }
}

//==============================================================
//==============================================================
void print_towers()
{
    int i, j;
    for(i=0; i<3; i++){
        printf("[%d] ", i+1);
        for(j=0; j<Ndisks[i]; j++)
            printf("%d ", Towers[i][j]);
        printf("\n");
    }
}