解決邏輯謎題在序言

Question

我在學習序言的「早期階段」和整個邏輯謎語接縫容易實現傳來：

Link to the riddle | Link to solution

---

我們正在尋找滿足以下條件的10位數字：

• 所有的0-9位出現一次。
• 前2位是整除2.
• 前3位是被3整除

...

• 前10位是整除10

---

我想我首先需要將規則實施到.pl文件嗎？ 從解決方案的規則是：

• 一個整數可以除以1除以餘數。
• 如果最後一位數字是直的，整數可以被2整除。
• 整數可以被3分割而沒有餘如果其橫向總和是被3整除
• 整數可以除以4無如果最後兩個數字是整除4.
• 的整數餘數是由5整除如果最後一個數字是整除5.
• 一個整數是整除6沒有餘如果其橫向總和是被3整除並通過2.
• 一個整數的最後一位數字是被8整除，而不如果最後三位數字可以被8整除，則爲餘數。
• 整數可以被9整除如果一個其橫向和餘數爲整除9.
• 一個整數是被10整除沒有餘如果最後位爲0。

---

予讀取多個介紹到在序言但仍然規則不知道怎麼做。誰能幫忙？將是偉大的:)

Answer 1

在Prolog中解決這類問題的基本方法是生成所有可能性，然後過濾它們。在這種情況下，我們需要的十個數字，沒有重複的列表，以及長度爲N每個前綴應該由N.是整除

puzzle([A,B,C,D,E,F,G,H,I,J]) :- 
    select(A,[0,1,2,3,4,5,6,7,8,9],List1), 
    select(B,List1,List2), select(C,List2,List3), select(D,List3,List4), 
    select(E,List4,List5), select(F,List5,List6), select(G,List6,List7), 
    select(H,List7,List8), select(I,List8,List9), List9 = [J], 
    divisible([A,B],2), 
    divisible([A,B,C],3), 
    divisible([A,B,C,D],4), 
    divisible([A,B,C,D,E],5), 
    divisible([A,B,C,D,E,F],6), 
    divisible([A,B,C,D,E,F,G],7), 
    divisible([A,B,C,D,E,F,G,H],8), 
    divisible([A,B,C,D,E,F,G,H,I],9), 
    divisible([A,B,C,D,E,F,G,H,I,J],10). 

即使整除可以輕鬆實現：

divisible(Is,D) :- 
    combine(Is,N), 
    R is N rem D, R == 0. 

但那麼我們還需要一些技術來在整數，字符和原子之間進行轉換。

:- use_module(library(lists)). 

combine(Is,N) :- 
    maplist(conv,Is,As), concat_list(As,A), 
    atom_chars(A,Cs), number_chars(N,Cs). 

conv(I,A) :- 
    number_chars(I,[C]), atom_chars(A,[C]). 

concat_list([A1,A2|As],Atom) :- 
    atom_concat(A1,A2,A3), 
    concat_list([A3|As],Atom). 
concat_list([A],A). 

這將產生在您的鏈接顯示的結果：

| ?- puzzle(X). 
X = [3,8,1,6,5,4,7,2,9,0] ? ; 
no 
| ?- 

增加：如果你想更快，而不僅僅是買和其他人一樣一個更大的計算機，您可以交錯產生&代碼的測試部分：

puzzle2([A,B,C,D,E,F,G,H,I,J]) :- 
    select(A,[0,1,2,3,4,5,6,7,8,9],List1), 
    select(B,List1,List2), divisible([A,B],2), 
    select(C,List2,List3), divisible([A,B,C],3), 
    select(D,List3,List4), divisible([A,B,C,D],4), 
    select(E,List4,List5), divisible([A,B,C,D,E],5), 
    select(F,List5,List6), divisible([A,B,C,D,E,F],6), 
    select(G,List6,List7), divisible([A,B,C,D,E,F,G],7), 
    select(H,List7,List8), divisible([A,B,C,D,E,F,G,H],8), 
    select(I,List8,List9), divisible([A,B,C,D,E,F,G,H,I],9), 
    List9 = [J], divisible([A,B,C,D,E,F,G,H,I,J],10). 

使用SWI Prolog的，我得到以下計時：

?- time((puzzle(_),false)). 
32m% 142,709,118 inferences, 76.333 CPU in 76.650 seconds (100% CPU, 1869553 Lips) 

?- time((puzzle2(_),false)). 
32m% 157,172 inferences, 0.142 CPU in 0.144 seconds (98% CPU, 1108945 Lips) 

?- time((num(_),false)). 
32m% 2,802,204 inferences, 1.008 CPU in 1.028 seconds (98% CPU, 2779208 Lips) 

這似乎暗示puzzle2版本比下面給出的num版本快幾倍。

Answer 2

由於您已將此標記爲clpfd，我想用現有答案補充有關約束的其他信息。

重要的是，限制讓你經常避免所有組合的產生由修剪的搜索空間爲 你。

 
digits_integer(Ds0, I) :- 
     reverse(Ds0, Ds), 
     Ds0 ins 0..9, 
     foldl(pow, Ds, 0-0, I-_). 

pow(D, I0-P0, I-P) :- 
     I #= I0 + D*10^P0, 
     P #= P0 + 1. 

這裏有兩個例子查詢：

我們可以通過與的數字由這些數字所描述的整數列表開始

 
?- digits_integer([1,2,3], I). 
I = 123. 

?- digits_integer(Ds, 302). 
Ds = [3, 0, 2] . 

接下來，讓我們我們描述了列表的前綴長度爲  N   Ls是整除通過  N：

 
n_divisible(Ls, N) :- 
     length(Prefix, N), 
     append(Prefix, _, Ls), 
     digits_integer(Prefix, I), 
     I mod N #= 0. 

整體解決方案因此可以描述爲：

 
solution(Ds) :- 
     length(Ds, 10), 
     Ds ins 0..9, 
     all_distinct(Ds), 
     E in 2..10, 
     findall(E, indomain(E), Es), 
     maplist(n_divisible(Ds), Es). 

樣品查詢：

 
?- solution(Ds), label(Ds). 
Ds = [3, 8, 1, 6, 5, 4, 7, 2, 9, 0] ; 
false. 

讓我們簡單地比較性能的兩種解決方案：

 
?- time((puzzle(Vs),false)). 
% 142,709,119 inferences, 14.865 CPU in 14.867 seconds 

VS：

 
?- time((solution(Ds),label(Ds),false)). 
% 19,384,173 inferences, 2.166 CPU in 2.166 seconds 

因此，基於約束的方法是在這個具體的例子快好幾倍。這主要是由於約束力傳播，其中解算器自動執行。

Answer 3

這是一個與CLP（FD）略有不同的方法。首先讓我們考慮一個謂詞，它描述一個列表，它的前n個元素和n個元素產生的數量之間的關係。這個版本有點類似，但比@ mat的digits_integer/2要少一些。

:- use_module(library(clpfd)). 

digits_firstn_number_(_D,0,Num,Num). 
digits_firstn_number_([D|Ds],X1,Num,Acc0) :- 
    X1 #> 0, 
    X0 #= X1-1, 
    Acc1 #= Acc0*10+D, 
    digits_firstn_number_(Ds,X0,Num,Acc1). 

調用謂詞num/1由目標num_/2，描述實際的關係，第二個進球label/1所標註的數字的列表，它是num_/2第二個參數。至於@墊的版本num/1微小的差別具有實際數量，而不是作爲一個參數的數字列表：

num(Num) :- 
    num_(Num,Digits),  % <- actual relation 
    label(Digits).  % <- labeling the digits 

的實際關係，num_/2不同範圍內，作爲整除規則是，只要有可能，表示爲限制在相應的數字（如你鏈接的解決方案建議），而不是在相應的數字：

num_(Num,Digits) :- 
    Digits=[A,B,C,D,E,F,G,H,I,J], 
    Digits ins 0..9, 
    all_distinct(Digits),      % divisibility for: 
    0 #= B mod 2,        % <- first 2 digits 
    0 #= (A+B+C) mod 3,      % <- first 3 digits 
    digits_firstn_number_([C,D],2,Num4,0), % <- first 4 digits 
    0 #= Num4 mod 4,       % <- first 4 digits 
    0 #= (E) mod 5,       % <- first 5 digits 
    0 #= (A+B+C+D+E+F) mod 3,     % <- first 6 digits 
    0 #= F mod 2,        % <- first 6 digits 
    digits_firstn_number_(Digits,7,Num7,0), % <- first 7 digits 
    0 #= Num7 mod 7,       % <- first 7 digits 
    digits_firstn_number_([F,G,H],3,Num8,0), % <- first 8 digits 
    0 #= Num8 mod 8,       % <- first 8 digits 
    0 #= (A+B+C+D+E+F+G+H+I) mod 9,   % <- first 9 digits 
    J #= 0,         % <- all 10 digits 
    digits_firstn_number_(Digits,10,Num,0). % <- the actual number 

這種方法（除了更多的代碼）的缺點是，它是非常朝着這個特定的難題量身定做，同時@ mat的版本可以更容易地擴展到搜索n具有不同數量的具有相似約束的數字（前n個數字可被n整除）。上側這種方法更快（以SWI-Prolog的（多線程，64位，版本6.6.4）相比）：

?- time((num(Num),false)). 
% 2,544,064 inferences, 0.486 CPU in 0.486 seconds (100% CPU, 5235403 Lips) 
false. 

?- time((solution(Ds),label(Ds),false)). 
% 19,289,281 inferences, 3.323 CPU in 3.324 seconds (100% CPU, 5805472 Lips) 
false. 

當然，num/1產生相同的溶液：

?- num(Num). 
Num = 3816547290 ; 
false.