From Gossip@Openhome

Algorithm Gossip: 雙色、三色河內塔

說明

雙色河內塔與三色河內塔是由之前所介紹過的河內塔規則衍生而來,雙色河內塔的目的是將下圖左上的圓環位置經移動成為右下的圓環位置:
多色河內塔

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

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

解法

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

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

多色河內塔

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

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

多色河內塔

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

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

多色河內塔

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

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

雙色河內塔實作:C    Java    Python    Scala    Ruby    JavaScript    Haskell

三色河內塔實作:C    Java    Python    Scala    Ruby    JavaScript    Haskell


  • 雙色河內塔 C
#include <stdio.h>

void print(char from, char to) {
printf("盤由 %c 移至 %c\n", from, to);
}

void hanoi(int n, char a, char b, char c) {
if (n == 1) {
print(a, c);
print(a, c);
} else {
hanoi(n - 1, a, c, b);
hanoi(1, a, b, c);
hanoi(n - 1, b, a, c);
}
}

void hanoi2colors(int n) {
char a = 'A';
char b = 'B';
char c = 'C';
int i;
for(i = n / 2; i > 1; i--) {
hanoi(i - 1, a, b, c);
print(a, b);
print(a, b);
hanoi(i - 1, c, b, a);
print(b, c);
}
print(a, b);
print(a, c);
}

int main() {
int n;
printf("盤數:");
scanf("%d", &n);

hanoi2colors(n);

return 0;
}

  • 雙色河內塔 Java
import java.util.*;
import static java.lang.System.out;

public class Hanoi2Colors {
static class Move {
char from, to;
Move(char from, char to) {
this.from = from;
this.to = to;
}
}

private List<Move> moves;

List<Move> solve(int n) {
moves = new ArrayList<Move>();
hanoi2Colors(n);
return moves;
}

public void hanoi(int n, char a, char b, char c) {
if (n == 1) {
moves.add(new Move(a, c));
} else {
hanoi(n - 1, a, c, b);
hanoi(1, a, b, c);
hanoi(n - 1, b, a, c);
}
}

public void hanoi2Colors(int n) {
char a = 'A';
char b = 'B';
char c = 'C';
for (int i = n / 2; i > 1; i--) {
hanoi(i - 1, a, b, c);
moves.add(new Move(a, b));
moves.add(new Move(a, b));
hanoi(i - 1, c, b, a);
moves.add(new Move(b, c));
}
moves.add(new Move(a, b));
moves.add(new Move(a, c));
}

public static void main(String[] args) {
out.print("盤數:");
Hanoi2Colors hanoi2Colors = new Hanoi2Colors();
int n = new Scanner(System.in).nextInt();
for(Move move : hanoi2Colors.solve(n)) {
out.printf("盤由 %c 移至 %c%n", move.from, move.to);
}
}
}

  • 雙色河內塔 Python
def hanoi(n, a, b, c):
if n == 1:
return [(a, c)]
else:
return hanoi(n - 1, a, c, b) + hanoi(1, a, b, c) + hanoi(n - 1, b, a, c)

def hanoi2Colors(n):
a, b, c= 'A', 'B', 'C'
l = [hanoi(i - 1, a, b, c) + [(a, b), (a, b)]
+ hanoi(i - 1, c, b, a) + [(b, c)] for i in range(n // 2, 1, -1)]
return [item for subList in l for item in subList] + [(a, b), (a, c)]

for move in hanoi2Colors(int(input('盤數:'))):
print("盤由 %c 移至 %c" % move)

  • 雙色河內塔 Scala
def hanoi(n: Int, a: Char, b: Char, c: Char): List[(Char, Char)] = {
if(n == 1) List((a, c))
else hanoi(n - 1, a, c, b) ++ hanoi(1, a, b, c) ++ hanoi(n - 1, b, a, c)
}

def hanoi2Colors(n: Int) = {
val (a, b, c) = ('A', 'B', 'C')
val list = for(i <- n / 2 until (1, -1)) yield (hanoi(i - 1, a, b, c)
++ List((a, b), (a, b)) ++ hanoi(i - 1, c, b, a) ++ List((b, c)))
list.flatten ++ List((a, b), (a, c))
}

print("盤數:")
hanoi2Colors(readInt).foreach(_ match {
case (from, to) => printf("盤由 %c 移到 %c%n", from, to)
})

  • 雙色河內塔 Ruby
#encoding: Big5

def step(f, t)
{from: f, to: t}
end

def hanoi(n, a, b, c)
if n == 1
[step(a, c)]
else
hanoi(n - 1, a, c, b) + hanoi(1, a, b, c) + hanoi(n - 1, b, a, c)
end
end

def hanoi2Colors(n)
a, b, c = "A", "B", "C"
(2..(n / 2)).to_a.reverse.map { |i|
hanoi(i - 1, a, b, c) + [step(a, b), step(a, b)] + hanoi(i - 1, c, b, a)
+ [step(b, c)]
}.flatten + [step(a, b), step(a, c)]
end

print "盤數:"
hanoi2Colors(gets.to_i).each do |move|
print "盤子從 #{move[:from]} 移動至 #{move[:to]}\n"
end

  • 雙色河內塔 JavaScript
Array.prototype.reduce = function(init, f) {
var value = init;
for(var i = 0; i < this.length; i++) {
value = f(value, this[i]);
}
return value;
};

function step(f, t) {
return {from: f, to: t};
}

function range(from, to) {
var r = [];
if(to > from) for(var c = 0, i = from; i < to; c++, i++) { r[c] = i; }
else for(var c = 0, i = from; i > to; c++, i--) { r[c] = i; }
return r;
}

function hanoi(n, a, b, c) {
if(n === 1) {
return [step(a, c)];
} else {
return hanoi(n - 1, a, c, b).concat(
hanoi(1, a, b, c), hanoi(n - 1, b, a, c));
}
}

function hanoi2Colors(n) {
var a = 'A'; var b = 'B'; var c = 'C';
return range(n / 2, 1).map(function(i) {
return hanoi(i - 1, a, b, c).concat([step(a, b), step(a, b)],
hanoi(i - 1, c, b, a), [step(b, c)]);
}).reduce([], function(ac, l) {
return ac.concat(l);
}).concat([step(a, b), step(a, c)]);
}

hanoi2Colors(6).forEach(function(step) {
print('盤從 ' + step.from + ' 移至 ' + step.to);
});

  • 雙色河內塔 Haskell
import Text.Printf

hanoi 1 a _ c = [(a, c)]
hanoi n a b c = hanoi (n - 1) a c b ++ hanoi 1 a b c ++ hanoi (n - 1) b a c

hanoi2Colors n = [item | subList <- list, item <- subList] ++ [(a, b), (a, c)]
where (a, b, c) = ('A', 'B', 'C')
begin = n `div` 2
list = [hanoi (i - 1) a b c ++ [(a, b), (a, b)] ++ hanoi (i - 1) c b a
++ [(b, c)] |i <- [begin, (begin - 1) .. 2]]

main = do
putStrLn "Please enter a number: "
n <- getLine
sequence [printf "Move from %c to %c\n" from to
| (from, to) <- hanoi2Colors (read n)]

------------------------------------------------------------------------------------------------------------------

  • 三色河內塔 C
#include <stdio.h>

void print(char from, char to) {
printf("盤由 %c 移至 %c\n", from, to);
}

void hanoi(int n, char a, char b, char c) {
if(n != 0) {
if (n == 1) {
print(a, c);
print(a, c);
print(a, c);
} else {
hanoi(n - 1, a, c, b);
hanoi(1, a, b, c);
hanoi(n - 1, b, a, c);
}
}
}

void hanoi3colors(int n) {
char a = 'A';
char b = 'B';
char c = 'C';

if(n == 3) {
print(a, b);
print(a, b);
print(a, c);
print(b, c);
print(b, a);
print(c, b);
}
else {
hanoi(n / 3 - 1, a, b, c);
print(a, b);
print(a, b);
print(a, b);

hanoi(n / 3 - 1, c, b, a);
print(b, c);
print(b, c);
print(b, c);

hanoi(n / 3 - 1, a, c, b);
print(c, a);
print(c, a);

hanoi(n / 3 - 1, b, a, c);
print(a, b);
int i;
for(i = n / 3 - 1; i > 0; i--) {
hanoi(i - 1, c, a, b);
print(c, a);
print(c, a);
hanoi(i - 1, b, a, c);
print(a, b);
}
}
}

int main() {
int n;
printf("盤數:");
scanf("%d", &n);

hanoi3colors(n);

return 0;
}

  • 三色河內塔 Java
import java.util.*;
import static java.lang.System.out;

public class Hanoi3Colors {
static class Move {
char from, to;
Move(char from, char to) {
this.from = from;
this.to = to;
}
}

private List<Move> moves;

List<Move> solve(int n) {
moves = new ArrayList<Move>();
hanoi3Colors(n);
return moves;
}

public void hanoi(int n, char a, char b, char c) {
if(n != 0) {
if (n == 1) {
moves.add(new Move(a, c));
moves.add(new Move(a, c));
moves.add(new Move(a, c));
} else {
hanoi(n - 1, a, c, b);
hanoi(1, a, b, c);
hanoi(n - 1, b, a, c);
}
}
}

public void hanoi3Colors(int n) {
char a = 'A';
char b = 'B';
char c = 'C';
if(n == 3) {
moves.add(new Move(a, b));
moves.add(new Move(a, b));
moves.add(new Move(a, c));
moves.add(new Move(b, c));
moves.add(new Move(b, a));
moves.add(new Move(c, b));
}
else {
hanoi(n / 3 - 1, a, b, c);
moves.add(new Move(a, b));
moves.add(new Move(a, b));
moves.add(new Move(a, b));

hanoi(n / 3 - 1, c, b, a);
moves.add(new Move(b, c));
moves.add(new Move(b, c));
moves.add(new Move(b, c));

hanoi(n / 3 - 1, a, c, b);
moves.add(new Move(c, a));
moves.add(new Move(c, a));

hanoi(n / 3 - 1, b, a, c);
moves.add(new Move(a, b));
for (int i = n / 3 - 1; i > 0; i--) {
hanoi(i - 1, c, a, b);
moves.add(new Move(c, a));
moves.add(new Move(c, a));
hanoi(i - 1, b, a, c);
moves.add(new Move(a, b));
}
}
}

public static void main(String[] args) {
out.print("盤數:");
Hanoi3Colors hanoi3Colors = new Hanoi3Colors();
int n = new Scanner(System.in).nextInt();
for(Move move : hanoi3Colors.solve(n)) {
out.printf("盤由 %c 移至 %c%n", move.from, move.to);
}
}
}

  • 三色河內塔 Python
def flatten(list):
return [item for sublist in list for item in sublist]

def hanoi(n, a, b, c):
if n == 0:
return []
else:
if n == 1:
return [(a, c), (a, c), (a, c)]
else:
return hanoi(n - 1, a, c, b) + hanoi(1, a, b, c) \
+ hanoi(n - 1, b, a, c)

def hanoi3Colors(n):
a, b, c= 'A', 'B', 'C'
if n == 3:
return [(a, b), (a, b), (a, c), (b, c), (b, a), (c, b)]
else:
return hanoi(n / 3 - 1, a, b, c) + [(a, b), (a, b), (a, b)] + \
hanoi(n / 3 - 1, c, b, a) + [(b, c), (b, c), (b, c)] + \
hanoi(n / 3 - 1, a, c, b) + [(c, a), (c, a)] + \
hanoi(n / 3 - 1, b, a, c) + [(a, b)] + \
flatten([hanoi(i - 1, c, a, b) + [(c, a), (c, a)] +
hanoi(i - 1, b, a, c) + [(a, b)]
for i in range(n // 3 - 1, 0, -1)])

for move in hanoi3Colors(int(input('盤數:'))):
print("盤由 %c 移至 %c" % move)

  • 三色河內塔 Scala
def hanoi(n: Int, a: Char, b: Char, c: Char): List[(Char, Char)] = {
if(n == 0) Nil
else {
if(n == 1) List((a, c), (a, c), (a, c))
else hanoi(n - 1, a, c, b) ++
hanoi(1, a, b, c) ++ hanoi(n - 1, b, a, c)
}
}

def hanoi3Colors(n: Int) = {
val (a, b, c) = ('A', 'B', 'C')
if(n == 3) List((a, b), (a, b), (a, c), (b, c), (b, a), (c, b))
else {
hanoi(n / 3 - 1, a, b, c) ++ List((a, b), (a, b), (a, b)) ++
hanoi(n / 3 - 1, c, b, a) ++ List((b, c), (b, c), (b, c)) ++
hanoi(n / 3 - 1, a, c, b) ++ List((c, a), (c, a)) ++
hanoi(n / 3 - 1, b, a, c) ++ List((a, b)) ++
(for(i <- n / 3 - 1 until (0, -1)) yield (hanoi(i - 1, c, a, b) ++
List((c, a), (c, a)) ++ hanoi(i - 1, b, a, c) ++ List((a, b)))).flatten
}
}

print("盤數:")
hanoi3Colors(readInt).foreach(_ match {
case (from, to) => printf("盤由 %c 移到 %c%n", from, to)
})

  • 三色河內塔 Ruby
#encoding: Big5

def step(f, t)
{from: f, to: t}
end

def hanoi(n, a, b, c)
if n == 0
[]
else
if n == 1
[step(a, c), step(a, c), step(a, c)]
else
hanoi(n - 1, a, c, b) + hanoi(1, a, b, c) + hanoi(n - 1, b, a, c)
end
end
end

def hanoi3Colors(n)
a, b, c = "A", "B", "C"
if n == 3
[step(a, b), step(a, b), step(a, c),
step(b, c), step(b, a), step(c, b)]
else
hanoi(n / 3 - 1, a, b, c) + [step(a, b), step(a, b), step(a, b)] +
hanoi(n / 3 - 1, c, b, a) + [step(b, c), step(b, c), step(b, c)] +
hanoi(n / 3 - 1, a, c, b) + [step(c, a), step(c, a)] +
hanoi(n / 3 - 1, b, a, c) + [step(a, b)] +
(1..(n / 3 - 1)).to_a.reverse.map { |i|
hanoi(i - 1, c, a, b) + [step(c, a), step(c, a)] +
hanoi(i - 1, b, a, c) + [step(a, b)]
}.flatten
end
end

print "整數:"
hanoi3Colors(gets.to_i).each do |move|
print "盤子從 #{move[:from]} 移動至 #{move[:to]}\n"
end

  • 三色河內塔 JavaScript
Array.prototype.reduce = function(init, f) {
var value = init;
for(var i = 0; i < this.length; i++) {
value = f(value, this[i]);
}
return value;
};

function step(f, t) {
return {from: f, to: t};
}

function range(from, to) {
var r = [];
if(to > from) for(var c = 0, i = from; i < to; c++, i++) { r[c] = i; }
else for(var c = 0, i = from; i > to; c++, i--) { r[c] = i; }
return r;
}

function hanoi(n, a, b, c) {
if(n === 0) {
return [];
} else {
if(n === 1) {
return [step(a, c), step(a, c), step(a, c)];
} else {
return hanoi(n - 1, a, c, b).concat(
hanoi(1, a, b, c), hanoi(n - 1, b, a, c));
}
}
}

function hanoi3Colors(n) {
var a = 'A'; var b = 'B'; var c = 'C';
if(n === 3) {
return [step(a, b), step(a, b), step(a, c),
step(b, c), step(b, a), step(c, b)];
}
else {
return hanoi(n / 3 - 1, a, b, c).concat(
[step(a, b), step(a, b), step(a, b)],
hanoi(n / 3 - 1, c, b, a),
[step(b, c), step(b, c), step(b, c)],
hanoi(n / 3 - 1, a, c, b),
[step(c, a), step(c, a)],
hanoi(n / 3 - 1, b, a, c),
[step(a, b)],
range(n / 3 - 1, 0).map(function(i) {
return hanoi(i - 1, c, a, b).concat(
[step(c, a), step(c, a)],
hanoi(i - 1, b, a, c), [step(a, b)]);
}).reduce([], function(ac, l) {
return ac.concat(l);
})
);
}
}

hanoi3Colors(6).forEach(function(step) {
print('盤從 ' + step.from + ' 移至 ' + step.to);
});

  • 三色河內塔 Haskell
import Text.Printf

hanoi 0 _ _ _ = []
hanoi 1 a _ c = [(a, c), (a, c), (a, c)]
hanoi n a b c = hanoi (n - 1) a c b ++ hanoi 1 a b c ++ hanoi (n - 1) b a c

hanoi3Colors n = case n of
3 -> [(a, b), (a, b), (a, c), (b, c), (b, a), (c, b)]
n -> hanoi begin a b c ++ [(a, b), (a, b), (a, b)] ++
hanoi begin c b a ++ [(b, c), (b, c), (b, c)] ++
hanoi begin a c b ++ [(c, a), (c, a)] ++
hanoi begin b a c ++ [(a, b)] ++
[item | subList <- list, item <- subList]
where (a, b, c) = ('A', 'B', 'C')
begin = n `div` 3 - 1
list = [hanoi (i - 1) c a b ++ [(c, a), (c, a)]
++ hanoi (i - 1) b a c ++
[(a, b)] |i <- [begin, (begin - 1) .. 1]]

main = do
putStrLn "Please enter a number: "
n <- getLine
sequence [printf "Move from %c to %c\n" from to
| (from, to) <- hanoi3Colors (read n)]