說明
雙色河內塔與三色河內塔是由之前所介紹過的河內塔規則衍生而來，雙色河內塔的目的是將下圖左上的圓環位置經移動成為右下的圓環位置：
而三色河內塔則是將下圖左上的圓環經移動成為右上的圓環：
在移動的過程中，一樣遵守大盤必須在小盤之下的規則，而顏色順序則無限制。
解法
無論是雙色河內塔或是三色河內塔，其解法觀念與之前介紹過的河內塔是類似的，同樣也是使用遞迴來解，不過這次遞迴解法的目的不同，我們先來看只有兩個 盤的情況，這很簡單，只要將第一柱的黃色移動至第二柱，而接下來第一柱的藍色移動至第三柱。再來是四個盤的情況，首先必須用遞迴完成下圖左上至右下的移動：
接下來最底層的就不用管它們了，因為它們已經就定位，只要再處理第一柱的上面兩個盤子就可以了。
那麼六個盤的情況呢？一樣！首先必須用遞迴完成下圖左上至右下的移動：
接下來最底層的就不用管它們了，因為它們已經就定位，只要再處理第一柱上面的四個盤子就可以了，這又與之前只有四盤的情況相同，接下來您就知道該如何進行解題了，無論是八個盤、十個盤以上等，都是用這個觀念來解題。
那麼三色河內塔呢？一樣，直接來看九個盤的情況，首先必須完成下圖的移動結果：
接下來最底兩層的就不用管它們了，因為它們已經就定位，只要再處理第一柱上面的三個盤子就可以了。
您也可以看看 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);
}
}
}
}