雙色、三色河內塔


說明

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


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


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

解法

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

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

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

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

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

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


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

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

雙色河內塔實作:Python    Prolog

三色河內塔實作:Python    Prolog


  • 雙色河內塔 Python
def hanoi(n, a, b, c):
    if n == 1:
        print('{} to {}'.format(a, b))
        print('{} to {}'.format(a, c))
        print('{} to {}'.format(b, c))
    else:
        hanoi(n - 1, a, b, c)
        print('{} to {}'.format(a, b))
        hanoi(n - 1, c, a, b)
        print('{} to {}'.format(a, c))
        hanoi(n - 1, b, c, a)
        print('{} to {}'.format(b, c))
        hanoi(n - 1, a, b, c)
        
def two_colors_hanoi(n, a, b, c):
    if n == 1:
        print('{} to {}'.format(a, b))
        print('{} to {}'.format(a, c))
    else:
        hanoi(n - 1, a, b, c)
        print('{} to {}'.format(a, b))
        hanoi(n - 1, c, a, b)
        print('{} to {}'.format(a, c))
        hanoi(n - 1, b, c, a)

        two_colors_hanoi(n - 1, a, b, c)
        
two_colors_hanoi(3, 'A', 'B', 'C')

move(A, B) :- writef("%p to %p\n", [A, B]).

hanoi(1, A, B, C) :- 
    move(A, B), move(A, C), move(B, C), !.
hanoi(N, A, B, C) :-
    M is N - 1,
    hanoi(M, A, B, C),
    move(A, B),
    hanoi(M, C, A, B),
    move(A, C),
    hanoi(M, B, C, A),
    move(B, C),
    hanoi(M, A, B, C).
    
two_colors_hanoi(1, A, B, C) :-
    move(A, B), move(A, C), !.

two_colors_hanoi(N, A, B, C) :-
    M is N - 1,
    hanoi(M, A, B, C),
    move(A, B),
    hanoi(M, C, A, B),
    move(A, C),
    hanoi(M, B, C, A).
    
main(_) :-
    two_colors_hanoi(2, a, b, c).

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

  • 三色河內塔 Python
def hanoi(n, a, b, c):
    if n == 1:
        print('{} to {}'.format(a, b))
        print('{} to {}'.format(a, b))
        print('{} to {}'.format(a, c))
        print('{} to {}'.format(b, c))
        print('{} to {}'.format(b, c))
    else:
        hanoi(n - 1, a, b, c)
        print('{} to {}'.format(a, b))
        print('{} to {}'.format(a, b))
        print('{} to {}'.format(a, b))

        hanoi(n - 1, c, b, a)
        print('{} to {}'.format(b, c))
        print('{} to {}'.format(b, c))
        print('{} to {}'.format(b, c))
        
        hanoi(n - 1, a, b, c)
        
        
def three_colors_hanoi(n, a, b, c):
    if n == 1:
        print('{} to {}'.format(a, c))
        print('{} to {}'.format(a, b))
        print('{} to {}'.format(a, b))
        print('{} to {}'.format(c, a))
        print('{} to {}'.format(b, c))
    else:
        hanoi(n - 1, a, b, c)
        print('{} to {}'.format(a, b))
        print('{} to {}'.format(a, b))
        print('{} to {}'.format(a, b))
        
        hanoi(n - 1, c, b, a)
        print('{} to {}'.format(b, c))
        print('{} to {}'.format(b, c))
        print('{} to {}'.format(b, c))
        
        hanoi(n - 1, a, c, b)
        print('{} to {}'.format(c, a))
        
        hanoi(n - 1, b, c, a)
        print('{} to {}'.format(c, b))

        three_colors_hanoi(n - 1, a, b, c)
        
three_colors_hanoi(3, 'A', 'B', 'C')

move(A, B) :- writef("%p to %p\n", [A, B]).

hanoi(1, A, B, C) :-
    move(A, B), 
    move(A, B), 
    move(A, C), 
    move(B, C), 
    move(B, C), !.
hanoi(N, A, B, C) :-
    M is N - 1,
    hanoi(M, A, B, C),
    move(A, B), move(A, B), move(A, B),
    
    hanoi(M, C, B, A),
    move(B, C), move(B, C), move(B, C), 
    
    hanoi(M, A, B, C).
    
three_colors_hanoi(1, A, B, C) :-
    move(A, C), 
    move(A, B), 
    move(A, B), 
    move(C, A), 
    move(B, C), !.

three_colors_hanoi(N, A, B, C) :-
    M is N - 1,
    hanoi(M, A, B, C),
    move(A, B), move(A, B), move(A, B),
    
    hanoi(M, C, B, A),
    move(B, C), move(B, C), move(B, C),
    
    hanoi(M, A, C, B), 
    move(C, A),
    
    hanoi(M, B, C, A), 
    move(C, B),
    
    three_colors_hanoi(M, A, B, C). 
    
main(_) :-
    three_colors_hanoi(2, a, b, c).