解决 Prolog 中的逻辑谜题

Solving a logic riddle in Prolog

我正在 "early phase" 学习序言,遇到了一个很容易实现的逻辑谜题:

Link to the riddle | Link to solution


我们正在寻找满足以下条件的10位数字:

...


我想我首先需要对 .pl 文件实施规则,对吗? 解决方案的规则是:


我在序言中阅读了多篇规则介绍,但仍然不明白如何去做。谁能帮忙?会很棒:)

在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).

这会产生您 link 中指示的结果:

| ?- 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 版本快几倍。

因为你用 标记了这个,我想用关于 constraints.

的附加信息来扩充现有答案

重要的是,约束让您经常避免通过修剪搜索space所有组合的生成。

我们可以从数字的列表关联与这些描述的整数开始位数:

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] .

接下来,让我们描述一下列表 Ls 的长度为 N 的前缀可以被 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

对比:

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

因此,在这个具体案例中,基于约束的方法快几倍。这主要是由于约束 传播 的强大功能,求解器自动

这是一个与 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。作为与@mat 版本的细微差别 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 个数字。从好的方面来看,这种方法更快(与 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.