Prolog中的四色定理（使用動態謂詞）

Question

我正在使用SWI-Prolog根據四色定理（http://en.wikipedia.org/wiki/Four_color_theorem）對地圖着色。到目前爲止，我的計劃是這樣的：

colour(red). 
colour(blue). 

map_color(A,B,C) :- colour(A), 
     colour(B), 
     colour(C), 
     C \= B, 
     C \= A. 

（實際編程'會比較複雜，有4種顏色和更多的領域，但我想我會開始了一個簡單的情況下）

現在，我想避免具有相同結構的雙重解決方案。例如。對於包含三個字段的地圖，「紅色，紅色，藍色」解決方案的結構與「藍色，藍色，紅色」結構相同，只是顏色名稱不同，我不希望它們都顯示。

所以我想我會有一個動態謂詞解決方案/ 3，並調用斷言（解決方案（A，B，C））在我的map_color謂詞的末尾。然後，對於每個解決方案，檢查它們是否已經作爲解決方案/ 3事實存在。問題是我不得不斷言解決方案（Color1，Color1，Color2），即爲了進行統一檢查而使用變量。我想不出一種方法來實現這一點。

所以，問題是，什麼是最好的方式來斷言一個找到的解決方案，然後進行統一測試，以便「紅色，紅色，藍色」將統一爲「藍色，藍色，紅色」？

Answer 1

爲了建立關係變量之間：

mask_helper(_, _, [], []). 
mask_helper(A, B, [A|_], [B|_]):- !. 
mask_helper(A, B, [X|Xs], [_|Ys]):- 
    A \= X, 
    mask_helper(A, B, Xs, Ys). 

mask([], []). 
mask([X|Xs], [Y|Ys]):- 
    mask_helper(X,Y,Xs,Ys), 
    mask(Xs, Ys). 

，你可以建立你的面具：

?- mask([red,red,blue],X). 
X = [_G300, _G300, _G306] . 

但：

?- mask([red,red,blue],X), mask([blue,red,red],Y), X=Y. 
X = [_G27, _G27, _G27], 
Y = [_G27, _G27, _G27]. 

即如果您將使用assert（沒有規則正文），則與Color1 \= Color2沒有任何關係。

你可以考慮像事端顏色分配（很流行的做法）的順序：

colour(red). colour(green). colour(blue). 

colour_order(red, red). 
colour_order(red, green). 
colour_order(red, blue). 
colour_order(green, green). 
colour_order(green, blue). 

colour_code([]). 
colour_code([X]):- colour(X). 
colour_code([X|[Y|T]]):- 
    colour_order(X,Y), 
    colour_code([Y|T]). 

map_color(A,B,C):- 
    colour_code([A,B,C]), 
    C \= B, C \= A. 

但同樣，你永遠不會導致「紅，藍，紅」，如果你的條件將是A \= B, B \= C。

想想：

unify([], [], _). 
unify([X|Xs], [Y|Ys], M):- 
    member((X=Z), M), !, 
    Z = Y, 
    unify(Xs, Ys, M). 

unify([X|Xs], [Y|Ys], M):- 
    % X is not assigned yet 
    not(member((_=Y),M)), % Y is not used as well 
    unify(Xs, Ys, [(X=Y)|M]). 

比你可以比較：

?- unify([red,red,blue],[blue,blue,red],[]). 
true. 

?- unify([red,red,blue],[blue,blue,blue],[]). 
false. 

?- unify([red,red,blue],[blue,red,red],[]). 
false. 

Answer 2

我認爲最簡單的解決方案是說A總是呈現紅色（例如）。