雙色、三色河內塔

而三色河內塔則是將下圖左上的圓環經移動成為右上的圓環：

在移動的過程中，一樣遵守大盤必須在小盤之下的規則，而顏色順序則無限制。

解法

無論是雙色河內塔或是三色河內塔，其解法觀念與之前介紹過的河內塔是類似的，同樣也是使用遞迴來解，不過這次遞迴解法的目的不同，我們先來看只有兩個盤的情況，這很簡單，只要將第一柱的黃色移動至第二柱，而接下來第一柱的藍色移動至第三柱。

再來是四個盤的情況，首先必須用遞迴完成下圖左上至右下的移動：

接下來最底層的就不用管它們了，因為它們已經就定位，只要再處理第一柱的上面兩個盤子就可以了。

那麼六個盤的情況呢？一樣！首先必須用遞迴完成下圖左上至右下的移動：

接下來最底層的就不用管它們了，因為它們已經就定位，只要再處理第一柱上面的四個盤子就可以了，這又與之前只有四盤的情況相同，接下來您就知道該如何進行解題了，無論是八個盤、十個盤以上等，都是用這個觀念來解題。

那麼三色河內塔呢？一樣，直接來看九個盤的情況，首先必須完成下圖的移動結果：

接下來最底兩層的就不用管它們了，因為它們已經就定位，只要再處理第一柱上面的三個盤子就可以了。

您也可以看看 Towers of Hanoi Page 中有關於河內塔的討論。

實作

以下Java演算實例由 http://www.javaworld.com.tw 的 T5555 提供，感謝他的協助，我根據他的實例，轉換為C語言的實作部份，您可以參考這個討論串有關於河內塔的討論。

雙色河內塔 C 實作

#include <stdio.h>

void hanoi(int disks, char source, char temp, char target) {
    if (disks == 1) {
        printf("move disk from %c to %c\n", source, target);
        printf("move disk from %c to %c\n", source, target);
    } else {
        hanoi(disks-1, source, target, temp);
        hanoi(1, source, temp, target);
        hanoi(disks-1, temp, source, target);
    }
}

void hanoi2colors(int disks) {
    char source = 'A';
    char temp = 'B';
    char target = 'C';
    int i;
    for(i = disks / 2; i > 1; i--) {
        hanoi(i-1, source, temp, target);
        printf("move disk from %c to %c\n", source, temp);
        printf("move disk from %c to %c\n", source, temp);
        hanoi(i-1, target, temp, source);
        printf("move disk from %c to %c\n", temp, target);
    }
    printf("move disk from %c to %c\n", source, temp);
    printf("move disk from %c to %c\n", source, target);
}

int main() {
    int n;
    printf("請輸入盤數：");
    scanf("%d", &n);

    hanoi2colors(n);

    return 0;
}

三色河內塔 C 實作

#include <stdio.h>

void hanoi(int disks, char source, char temp, char target) {
    if (disks == 1) {
        printf("move disk from %c to %c\n", source, target);
        printf("move disk from %c to %c\n", source, target);
        printf("move disk from %c to %c\n", source, target);
    } else {
        hanoi(disks-1, source, target, temp);
        hanoi(1, source, temp, target);
        hanoi(disks-1, temp, source, target);
    }
}

void hanoi3colors(int disks) {
    char source = 'A';
    char temp = 'B';
    char target = 'C';
    int i;

    if(disks == 3) {
        printf("move disk from %c to %c\n", source, temp);
        printf("move disk from %c to %c\n", source, temp);
        printf("move disk from %c to %c\n", source, target);
        printf("move disk from %c to %c\n", temp, target);
        printf("move disk from %c to %c\n", temp, source);
        printf("move disk from %c to %c\n", target, temp);;
    }
    else {
        hanoi(disks/3-1, source, temp, target);
        printf("move disk from %c to %c\n", source, temp);
        printf("move disk from %c to %c\n", source, temp);
        printf("move disk from %c to %c\n", source, temp);

        hanoi(disks/3-1, target, temp, source);
        printf("move disk from %c to %c\n", temp, target);
        printf("move disk from %c to %c\n", temp, target);
        printf("move disk from %c to %c\n", temp, target);

        hanoi(disks/3-1, source, target, temp);
        printf("move disk from %c to %c\n", target, source);
        printf("move disk from %c to %c\n", target, source);

        hanoi(disks/3-1, temp, source, target);
        printf("move disk from %c to %c\n", source, temp);
        
        for (i = disks / 3 - 1; i > 0; i--) {
            if (i>1) {
                hanoi(i-1, target, source, temp);
            }

            printf("move disk from %c to %c\n",
                                 target, source);
            printf("move disk from %c to %c\n",
                                 target, source);

            if (i>1) {
                hanoi(i-1, temp, source, target);
            }
            printf("move disk from %c to %c\n", 
                                   source, temp);
        }
    }
}

int main() {
    int n;
    printf("請輸入盤數：");
    scanf("%d", &n);

    hanoi3colors(n);

    return 0;
}

雙色河內塔 Java 實作

public class Hanoi2Colors { 
    public static void help() {
        System.out.println(
              "Usage: java Hanoi2Colors number_of_disks");
        System.out.println(
              "\t number_of_disks: must be a even number.");
        System.exit(0);
    }
    
    public static void main(String[] args) {
        int disks = 0;        
        try {
            disks = Integer.parseInt(args[0]);
        } catch (Exception e) {
            help();
        }
        if ((disks <= 0) || (disks % 2 != 0)) { 
            help(); 
        }
        hanoi2colors(disks);
    }
     
    public static void hanoi(int disks, 
                      char source, char temp, char target) {
        if (disks == 1) {
            System.out.println("move disk from " 
                               + source + " to " + target);
            System.out.println("move disk from " 
                               + source + " to " + target);
        } else {        
            hanoi(disks-1, source, target, temp);
            hanoi(1, source, temp, target);
            hanoi(disks-1, temp, source, target);
        }
    }
 
    public static void hanoi2colors(int disks) {
        char source = 'A';
        char temp = 'B';
        char target = 'C';
        for (int i = disks / 2; i > 1; i--) {
            hanoi(i-1, source, temp, target);
            System.out.println("move disk from " 
                                   + source + " to " + temp);
            System.out.println("move disk from " 
                                   + source + " to " + temp); 
            hanoi(i-1, target, temp, source);
            System.out.println("move disk from " 
                                   + temp + " to " + target);
        }
        System.out.println("move disk from " 
                                   + source + " to " + temp);
        System.out.println("move disk from " 
                                 + source + " to " + target);
    }
}

三色河內塔 Java 實作

public class Hanoi3Colors {    
    public static void help() {
        System.out.println(
              "Usage: java Hanoi3Colors number_of_disks");
        System.out.println(
      "\tnumber_of_disks: must be a number divisible by 3.");
        System.exit(0);
    }
    
    public static void main(String[] args) {
        int disks = 0;        
        try {
            disks = Integer.parseInt(args[0]);
        } catch (Exception e) {
            help();
        }
        if ((disks <= 0) || (disks % 3 != 0)) { 
            help(); 
        }
        hanoi3colors(disks);
    }
    
    public static void hanoi(int disks, 
                       char source, char temp, char target) {
        if (disks == 1) {
            System.out.println("move disk from " 
                               + source + " to " + target);
            System.out.println("move disk from "
                               + source + " to " + target);
            System.out.println("move disk from "
                               + source + " to " + target);
        } else {        
            hanoi(disks-1, source, target, temp);
            hanoi(1, source, temp, target);
            hanoi(disks-1, temp, source, target);
        }
    }
    
    public static void hanoi3colors(int disks) {
        char source = 'A';
        char temp   = 'B';
        char target = 'C';
        if (disks == 3) {
            System.out.println("move disk from " 
                            + source + " to " + temp);
            System.out.println("move disk from " 
                            + source + " to " + temp);
            System.out.println("move disk from " 
                            + source + " to " + target);
            System.out.println("move disk from " 
                            + temp + " to " + target);
            System.out.println("move disk from " 
                            + temp + " to " + source);
            System.out.println("move disk from " 
                            + target + " to " + temp);
        } else {
            hanoi(disks/3-1, source, temp, target);
            System.out.println("move disk from " 
                            + source + " to " + temp);
            System.out.println("move disk from " 
                            + source + " to " + temp);
            System.out.println("move disk from " 
                            + source + " to " + temp);
            hanoi(disks/3-1, target, temp, source);
            System.out.println("move disk from " 
                            + temp + " to " + target);
            System.out.println("move disk from "
                            + temp + " to " + target);
            System.out.println("move disk from "
                            + temp + " to " + target);
            hanoi(disks/3-1, source, target, temp);
            System.out.println("move disk from " 
                            + target + " to " + source);
            System.out.println("move disk from " 
                            + target + " to " + source);
            hanoi(disks/3-1, temp, source, target);
            System.out.println("move disk from " 
                            + source + " to " + temp);
        
            for (int i = disks / 3 - 1; i > 0; i--) {
                if (i>1) { 
                    hanoi(i-1, target, source, temp); 
                }
                System.out.println("move disk from " 
                         + target + " to " + source);
                System.out.println("move disk from " 
                         + target + " to " + source);
                if (i>1) { 
                    hanoi(i-1, temp, source, target); 
                }
                System.out.println("move disk from " 
                         + source + " to " + temp);
            }
        }
    }
}

From Gossip@caterpillar

Algorithm Gossip: 雙色、三色河內塔

說明

解法

實作