解决逻辑谜题在序言

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.