/*
    Name: hanoiTower.c

    Description: 利用函數遞迴法求河內塔問題之解

    Rules:
        河內塔問題目的乃在三根柱子中,將n個盤子從
        A 柱子搬到 C 柱中, 每次只移動一盤子, 而且必須遵守
        每個盤子都比其上面的盤子還要大的原則。

    Ans:
        河內塔問題的想法必須針對最底端的盤子。
        我們必須先把 A 柱子頂端 n-1 個盤子想辦法(借助 C 柱)移至 B 柱子
        然後才能將想最底端的盤子移至 C 柱。
        此時 C 有最大的盤子, B總共 n-1 個盤子, A 柱則無。
        只要再借助 A 柱子，將 B 柱 n-1 個盤子移往 C 柱即可 :
 
        HanoiTower(n-1, A, C, B);
        將 A 頂端 n-1 個盤子借助 C 移至 B
        HanoiTower(n-1, B, A, C);
        將 B 上的 n-1 個盤子借助 A 移至 C
*/

#include <stdio.h>
#include <stdlib.h>

/* 函數原型宣告 */
void HanoiTower(int, char, char, char);

int main()
{

    int n;
    char A = 'A', B = 'B', C = 'C';

    printf("-----Hanoi Tower Implementaion----\n");
    /*輸入共有幾個盤子在A柱子中*/
    printf("How many disks in A ? ");
    scanf("%d", &n);
    if (n == 0)
        printf("no disk to move\n");
    else
        HanoiTower(n, A, B, C);

    return 0;
}


/* 遞迴函數呼叫求河內塔之解 */
void HanoiTower(int n,char a,char b,char c)
{
    if ( n == 1 )
        printf("Move disk 1 from %c -> %c\n", a, c);
    else {
        /* 將A上n-1個盤子借助C移至B */
        HanoiTower(n-1,a,c,b);
        printf("Move disk %d from %c -> %c\n", n, a, c);
        /* 將B上n-1個盤子借助A移至C */
        HanoiTower(n-1, b, a, c);
    }
}