鎖定挑戰的Prolog

Question

我剛開始學習序言和我被困在試圖解決這個難題：

我嘗試添加一些規則，這樣的例子http://swish.swi-prolog.org/example/houses_puzzle.pl，但我不能想出一個辦法。

我試過到目前爲止：

% Render the houses term as a nice table. 
:- use_rendering(table, 
     [header(h('N1', 'N2', 'N3'))]). 
numbers(Hs) :- 
    length(Hs, 1), 
    member(h(6,8,2), Hs), 
    member(h(6,1,4), Hs), 
    member(h(2,0,6), Hs), 
    member(h(7,3,8), Hs), 
    member(h(7,8,0), Hs), 
    correct_and_placed(6, 8, 2, Hs). 

correct_and_place(A, B, C, R). 

但我甚至不知道怎麼寫，可以檢查一個數字是否正確，並在合適的地方的規則。

Answer 1

現有的答案，我想補充使用CLP（FD） 約束一個版本。

我將使用的兩個構建塊是num_correct/3和num_well_placed/3。

首先，num_correct/3，與整數的兩個列表中的共同元素個數：

 
num_correct(Vs, Ns, Num) :- 
     foldl(num_correct_(Vs), Ns, 0, Num). 

num_correct_(Vs, Num, N0, N) :- 
     foldl(eq_disjunction(Num), Vs, 0, Disjunction), 
     Disjunction #<==> T, 
     N #= N0 + T. 

eq_disjunction(N, V, D0, D0 #\/ (N #= V)). 

樣品查詢：

 
?- num_correct([1,2,3], [3,5], Num). 
Num = 1. 

由於是純粹的關係特點，也適用於例如：更多一般查詢，例如：

 
?- num_correct([A], [B], Num). 
B#=A#<==>Num, 
Num in 0..1. 

其次，我使用num_well_placed/3，其涉及整數的兩個列表來  等於的數，其中相應元件是指數：

 
num_well_placed(Vs, Ns, Num) :- 
     maplist(num_well_placed_, Vs, Ns, Bs), 
     sum(Bs, #=, Num). 

num_well_placed_(V, N, B) :- (V #= N) #<==> B. 

再次，一個示例查詢和答覆：

 
?- num_well_placed([8,3,4], [0,3,4], Num). 
Num = 2. 

以下謂詞簡單地結合了這兩個：

 
num_correct_placed(Vs, Hs, C, P) :- 
     num_correct(Vs, Hs, C), 
     num_well_placed(Vs, Hs, P). 

 
lock(Vs) :- 
     Vs = [_,_,_], 
     Vs ins 0..9, 
     num_correct_placed(Vs, [6,8,2], 1, 1), 
     num_correct_placed(Vs, [6,1,4], 1, 0), 
     num_correct_placed(Vs, [2,0,6], 2, 0), 
     num_correct_placed(Vs, [7,3,8], 0, 0), 
     num_correct_placed(Vs, [7,8,0], 1, 0). 

在所有沒有搜索需要在這種情況下：因此，如下整個拼圖可配製

 
?- lock(Vs). 
Vs = [0, 4, 2]. 

而且，如果我概括遠最後一抹，即，如果我寫：

 
lock(Vs) :- 
     Vs = [_,_,_], 
     Vs ins 0..9, 
     num_correct_placed(Vs, [6,8,2], 1, 1), 
     num_correct_placed(Vs, [6,1,4], 1, 0), 
     num_correct_placed(Vs, [2,0,6], 2, 0), 
     num_correct_placed(Vs, [7,3,8], 0, 0), 
     *num_correct_placed(Vs, [7,8,0], 1, 0). 

那麼唯一的解決方案可以仍然在沒有搜索確定：

 
?- lock(Vs). 
Vs = [0, 4, 2]. 

事實上，我甚至也帶走的倒數第二個提示：

 
lock(Vs) :- 
     Vs = [_,_,_], 
     Vs ins 0..9, 
     num_correct_placed(Vs, [6,8,2], 1, 1), 
     num_correct_placed(Vs, [6,1,4], 1, 0), 
     num_correct_placed(Vs, [2,0,6], 2, 0), 
     *num_correct_placed(Vs, [7,3,8], 0, 0), 
     *num_correct_placed(Vs, [7,8,0], 1, 0). 

and still解決方案是獨一無二的，雖然我現在必須使用label/1找到它：

 
?- lock(Vs), label(Vs). 
Vs = [0, 4, 2] ; 
false. 

Answer 2

不知道我需要解釋這一點。您生成所有可能性，然後您編碼約束。

code(A,B,C) :- 
    member(A,[0,1,2,3,4,5,6,7,8,9]), 
    member(B,[0,1,2,3,4,5,6,7,8,9]), 
    member(C,[0,1,2,3,4,5,6,7,8,9]), 
    (A = 6 ; B = 8 ; C = 2), 
    (A = 1, \+ member(B,[6,4]), \+ member(C,[6,4]) 
    ; A = 4, \+ member(B,[6,1]), \+ member(C,[6,1]) 
    ; B = 6, \+ member(A,[1,4]), \+ member(C,[1,4]) 
    ; B = 4, \+ member(A,[6,1]), \+ member(C,[6,1]) 
    ; C = 6, \+ member(B,[1,4]), \+ member(A,[1,4]) 
    ; C = 1, \+ member(B,[6,4]), \+ member(A,[6,4])), 
    (A = 0, B = 2, C \= 6 
    ; A = 0, B = 6, C \= 2 
    ; A = 6, B = 2, C \= 0 
    ; B = 2, C = 0, A \= 6 
    ; B = 6, C = 2, A \= 0 
    ; B = 6, C = 0, A \= 2 
    ; C = 2, A = 0, B \= 6 
    ; C = 2, A = 6, B \= 0 
    ; C = 0, A = 6, B \= 2), 
    \+ member(A,[7,3,8]), \+ member(B,[7,3,8]), \+ member(C,[7,3,8]), 
    (A = 8, \+ member(B,[7,0]), \+ member(C,[7,0]) 
    ; A = 0, \+ member(B,[7,8]), \+ member(C,[7,8]) 
    ; B = 7, \+ member(A,[8,0]), \+ member(C,[8,0]) 
    ; B = 0, \+ member(A,[7,8]), \+ member(C,[7,8]) 
    ; C = 7, \+ member(B,[8,0]), \+ member(A,[8,0]) 
    ; C = 8, \+ member(B,[7,0]), \+ member(A,[7,0])). 

下面是結果：

| ?- code(A,B,C). 
A = 0, 
B = 4, 
C = 2 ? ; 
no 

Answer 3

我希望有更好的方法，但...

您可以實現「一個號碼是正確的，天時地利」如下

oneRightPlace(X, Y, Z, X, S2, S3) :- 
    \+ member(Y, [S2, S3]), 
    \+ member(Z, [S2, S3]). 

oneRightPlace(X, Y, Z, S1, Y, S3) :- 
    \+ member(X, [S1, S3]), 
    \+ member(Z, [S1, S3]). 

oneRightPlace(X, Y, Z, S1, S2, Z) :- 
    \+ member(X, [S1, S2]), 
    \+ member(Y, [S1, S2]). 

對於「一個數字是正確的但錯誤的地方，你可以使用

oneWrongPlace(X, Y, Z, S1, S2, S3) :- 
    member(X, [S2, S3]), 
    \+ member(Y, [S1, S2, S3]), 
    \+ member(Z, [S1, S2, S3]). 

oneWrongPlace(X, Y, Z, S1, S2, S3) :- 
    member(Y, [S1, S3]), 
    \+ member(X, [S1, S2, S3]), 
    \+ member(Z, [S1, S2, S3]). 

oneWrongPlace(X, Y, Z, S1, S2, S3) :- 
    member(Z, [S1, S2]), 
    \+ member(X, [S1, S2, S3]), 
    \+ member(Y, [S1, S2, S3]). 

「兩個號碼是正確的，但錯置於」，你可以寫

twoWrongPlace(X, Y, Z, S1, S2, S3) :- 
    member(X, [S2, S3]), 
    member(Y, [S1, S3]), 
    \+ member(Z, [S1, S2, S3]). 

twoWrongPlace(X, Y, Z, S1, S2, S3) :- 
    member(X, [S2, S3]), 
    member(Z, [S1, S2]), 
    \+ member(Y, [S1, S2, S3]). 

twoWrongPlace(X, Y, Z, S1, S2, S3) :- 
    member(Y, [S1, S3]), 
    member(Z, [S1, S2]), 
    \+ member(X, [S1, S2, S3]). 

而且，對於「什麼是正確的」，成爲簡單的

zeroPlace(X, Y, Z, S1, S2, S3) :- 
    \+ member(X, [S1, S2, S3]), 
    \+ member(Y, [S1, S2, S3]), 
    \+ member(Z, [S1, S2, S3]). 

現在，你可以把所有togheter and write

member(S1, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]), 
    member(S2, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]), 
    member(S3, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]), 
    oneRightPlace(6, 8, 2, S1, S2, S3), 
    oneWrongPlace(6, 1, 4, S1, S2, S3), 
    twoWrongPlace(2, 0, 6, S1, S2, S3), 
    zeroPlace(7, 3, 8, S1, S2, S3), 
    oneWrongPlace(7, 8, 0, S1, S2, S3). 

獲得（在S1,S2和S3）正確的解決方案。

前面的例子是不使用clp（fd）編寫的，我不太清楚，但是（我想）可以使用很多semplify。

Answer 4

因此，正如所有問題一樣，我傾向於寫一個通用解算器而不是特定求解器。從mastermind implementation我寫了，而以前借款（通過在這裏的一個問題催生了）我提出以下幾點：

compare(List,Reference,RightPlace,WrongPlace)需要兩個列表，並結合RightPlace與出現在同一個點上的第一個列表元素的數量第二個列表和WrongPlace以及出現在第二個列表中不同位置的元素數量（其中重複元素只有在兩個列表中都重複時才計數）。爲此，它使用...

right_place(List,Reference,RightPlace)它包裝蓄能器，並從每個列表的打印頭消耗的元素，增加他們匹配，並且...

any_match(List,Reference,Matches)它包裝消耗的頭部累加器列表清單，並儘可能從參考列表中選擇它，在發生這種情況時遞增。

WrongPlace然後是從Matches的數字中減去RightPlace個元素的數量。

最後，find_solutions(Soln)使用clpfd創建域（0-9）中的元素列表，然後映射indomain以創建組合。然後使用forall將每個組合與每個提示進行比較，以確保滿足所有提示約束。與提示把它放在一起，你會得到：

:- use_module(library(clpfd)). 

compare(List,Reference,RightPlace,WrongPlace) :- 
    right_place(List,Reference,RightPlace), 
    any_match(List,Reference,Matches), 
    WrongPlace #= Matches - RightPlace. 

right_place(List,Reference,RightPlace) :- 
    right_place(List,Reference,0,RightPlace). 

right_place([],[],RightPlace,RightPlace). 
right_place([Match|List],[Match|Reference],Accumulator,RightPlace) :- 
    NewAccumulator is Accumulator + 1, 
    right_place(List,Reference,NewAccumulator,RightPlace). 
right_place([A|List],[B|Reference],Accumulator,RightPlace) :- 
    A \= B, 
    right_place(List,Reference,Accumulator,RightPlace). 

any_match(List,Reference,Matches) :- 
    any_match(List,Reference,0,Matches). 

any_match([],_,Matches,Matches). 
any_match([Match|List],Reference,Accumulator,Matches) :- 
    select(Match,Reference,NewReference), 
    NewAccumulator is Accumulator + 1, 
    any_match(List,NewReference,NewAccumulator,Matches). 
any_match([Match|List],Reference,Accumulator,Matches) :- 
    \+member(Match,Reference), 
    any_match(List,Reference,Accumulator,Matches). 

find_solutions(Soln) :- 
    length(Soln,3), 
    Soln ins 0..9, 
    maplist(indomain,Soln), 
    forall(hint(X,Y,Z),compare(Soln,X,Y,Z)). 

hint([6,8,2],1,0). 
hint([6,1,4],0,1). 
hint([2,0,6],0,2). 
hint([7,3,8],0,0). 
hint([7,8,0],0,1).