本題為三色河內塔，雙色河內塔請參閱97年雲嘉區第五題。 

下圖為河內塔問題(Towers of Hanoi)的一種，共有A、B、C三個柱子，一開始A柱子可以放個數為3倍數的套環，都是花白灰相間的三種不同顏色套環，每種大小的套環都有三個，花色在上，白色在中，灰色在下。套環依序由上到下的編號分別為1~N，假設每次的移動都只能從柱子的頂端移動一個套環，搬到其他柱子放，而且編號較大的套環永遠都不能放在較小套環的上方。最後要將所有花套環移動到A，白套環移動到B，以及所有灰套環移動到C。請寫出一個程式，輸入套環總數(為 3的倍數，包含花白灰三種套環)，計算並輸出所有套環的最佳移動順序(移動次數最少)及其移動次數。

輸入1：
3

輸入2：
6

輸出1：
ring 1 : A => C
ring 2 : A => B
ring 1 : C => B
ring 3 : A => C
ring 1 : B => A
共需5個移動

輸出2：
ring 1 : A => B
ring 2 : A => C
ring 1 : B => C
ring 3 : A => B
ring 1 : C => A
ring 2 : C => B
ring 1 : A => B
ring 4 : A => C
ring 1 : B => C
ring 2 : B => A
ring 1 : C => A
ring 3 : B => C
ring 1 : A => B
ring 2 : A => C
ring 1 : B => C
ring 5 : A => B
ring 1 : C => A
ring 2 : C => B
ring 1 : A => B
ring 3 : C => A
ring 1 : B => C
ring 2 : B => A
ring 1 : C => A
ring 4 : C => B
ring 1 : A => B
ring 2 : A => C
ring 1 : B => C
ring 3 : A => B
ring 1 : C => A
ring 2 : C => B
ring 1 : A => B
ring 6 : A => C
ring 1 : B => C
ring 2 : B => A
ring 1 : C => A
ring 3 : B => C
ring 1 : A => B
ring 2 : A => C
ring 1 : B => C
ring 4 : B => A
ring 1 : C => A
ring 2 : C => B
共需42個移動