雙色、三色河內塔

December 1, 2021

雙色河內塔與三色河內塔是由〈河內塔〉介紹過的規則衍生而來,雙色河內塔要將下圖左上,移動盤子成為右下:

雙色、三色河內塔

三色河內塔是將下圖左上,移動盤子成為右上:

雙色、三色河內塔

解法思路

無論是雙色河內塔或是三色河內塔,解法觀念與之前介紹過的〈河內塔〉類似,不過這次遞迴解法的目的不同。

只有兩個盤子時,只要將第一柱的黃色移動至第二柱,而接下來第一柱的藍色移動至第三柱;若有四個盤子,首先必須用遞迴完成下圖左上至右下的移動:

雙色、三色河內塔

接下來最底層的就不用管它們了,因為已經就定位,只要再處理第一柱的上面兩個盤子就可以了;六個盤的情況呢?一樣!首先必須用遞迴完成下圖左上至右下的移動:

雙色、三色河內塔

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

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

雙色、三色河內塔

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

雙色、三色河內塔

程式實作:雙色河內塔

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).
# 我寫的玩具語言 https://github.com/JustinSDK/toy_lang

def hanoi(n, a, b, c) {
    if n == 1 {
        println('{0} to {1}'.format(a, b))
        println('{0} to {1}'.format(a, c))
        println('{0} to {1}'.format(b, c))
    }
    else {
        hanoi(n - 1, a, b, c)
        println('{0} to {1}'.format(a, b))
        hanoi(n - 1, c, a, b)
        println('{0} to {1}'.format(a, c))
        hanoi(n - 1, b, c, a)
        println('{0} to {1}'.format(b, c))
        hanoi(n - 1, a, b, c)
    }
}
        
def two_colors_hanoi(n, a, b, c) {
    if n == 1 {
        println('{0} to {1}'.format(a, b))
        println('{0} to {1}'.format(a, c))
     }
     else {
        hanoi(n - 1, a, b, c)
        println('{0} to {1}'.format(a, b))
        hanoi(n - 1, c, a, b)
        println('{0} to {1}'.format(a, c))
        hanoi(n - 1, b, c, a)

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

程式實作:三色河內塔

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).
# 我寫的玩具語言 https://github.com/JustinSDK/toy_lang

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

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

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