在Prolog中更快地实现口头算术

Question

我已经在Prolog中制作了一个工作广义的动词算术求解器,但它太慢了.运行简单的表达SEND + MORE = MONE Y只需要8分钟.有人可以帮助我让它跑得更快吗？

/* verbalArithmetic(List,Word1,Word2,Word3) where List is the list of all 
possible letters in the words. The SEND+MORE = MONEY expression would then
be represented as
  verbalArithmetic([S,E,N,D,M,O,R,Y],[S,E,N,D],[M,O,R,E],[M,O,N,E,Y]). */

validDigit(X) :- member(X,[0,1,2,3,4,5,6,7,8,9]).
validStart(X) :- member(X,[1,2,3,4,5,6,7,8,9]).
assign([H|[]]) :- validDigit(H).         
assign([H|Tail]) :- validDigit(H), assign(Tail), fd_all_different([H|Tail]).

findTail(List,H,T) :- append(H,[T],List).

convert([T],T) :- validDigit(T).
convert(List,Num) :- findTail(List,H,T), convert(H,HDigit), Num is (HDigit*10+T).

verbalArithmetic(WordList,[H1|Tail1],[H2|Tail2],Word3) :- 
    validStart(H1), validStart(H2), assign(WordList), 
    convert([H1|Tail1],Num1),convert([H2|Tail2],Num2), convert(Word3,Num3), 
    Sum is Num1+Num2, Num3 = Sum.

Answer 1

考虑使用有限域约束,例如,在SWI-Prolog中:

:- use_module(library(clpfd)).

puzzle([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y]) :-
        Vars = [S,E,N,D,M,O,R,Y],
        Vars ins 0..9,
        all_different(Vars),
                  S*1000 + E*100 + N*10 + D +
                  M*1000 + O*100 + R*10 + E #=
        M*10000 + O*1000 + N*100 + E*10 + Y,
        M #\= 0, S #\= 0.

示例查询:

?- time((puzzle(As+Bs=Cs), label(As))).
% 5,803 inferences, 0.002 CPU in 0.002 seconds (98% CPU, 3553582 Lips)
As = [9, 5, 6, 7],
Bs = [1, 0, 8, 5],
Cs = [1, 0, 6, 5, 2] ;
% 1,411 inferences, 0.001 CPU in 0.001 seconds (97% CPU, 2093472 Lips)
false.

Answer 2

这里的性能差是由于在检查是否可行之前形成了所有可能的字母分配。

我的建议是“尽早失败，经常失败”。即，将尽可能多的失败检查尽早推入分配步骤，从而修剪搜索树。

克拉斯·林德贝克（KlasLindbäck）提出了一些好的建议。概括地说，当将两个数字相加时，进位在每个位置最多为一个。因此，可以从左到右检查字母从左到右的不同数字分配，以便在最右边位置进行尚未确定的进位。（当然，在最后的“单位”位置，没有进位。）

有很多事情要考虑，这就是为什么正如mat所建议的那样（并且您已经使用fd_all_different / 1提出了约束逻辑）如此便利。

补充： 这是一个没有约束逻辑的Prolog解决方案，仅使用一个辅助谓词omit / 3：

omit(H,[H|T],T).
omit(X,[H|T],[H|Y]) :- omit(X,T,Y).

它既从列表中选择一个项目，又生成不包含该项目的缩短列表。

然后是sendMoreMoney / 3的代码，它通过从左到右求和来搜索：

sendMoreMoney([S,E,N,D],[M,O,R,E],[M,O,N,E,Y]) :-
    M = 1,
    omit(S,[2,3,4,5,6,7,8,9],PoolO),
    (CarryS = 0 ; CarryS = 1),
    %% CarryS + S + M =      M*10 + O
    O is (CarryS + S + M) - (M*10), 
    omit(O,[0|PoolO],PoolE),
    omit(E,PoolE,PoolN),
    (CarryE = 0 ; CarryE = 1),
    %% CarryE + E + O = CarryS*10 + N
    N is (CarryE + E + O) - (CarryS*10),
    omit(N,PoolN,PoolR),
    (CarryN = 0 ; CarryN = 1),
    %% CarryN + N + R = CarryE*10 + E
    R is (CarryE*10 + E) - (CarryN + N),
    omit(R,PoolR,PoolD),
    omit(D,PoolD,PoolY),
    %%          D + E = CarryN*10 + Y
    Y is (D + E) - (CarryN*10),
    omit(Y,PoolY,_).

我们从最左边的数字总和（即1）开始必须观察到M必须是非零进位，从而开始快速入门。S必须是其他一些非零数字。注释显示了可以根据已经做出的选择确定性地分配其他字母的值的步骤。

新增（2）：这是用于两个被加数的“通用”密码求解器，它们不必具有相同的长度/数量的“位置”。对于码长/ 2被省略一个相当普遍的内部谓词，并且占用了由Will尼斯建议，将呼叫省略/ 3被替换选择/ 3为SWI-Prolog的用户的便利性。

我已经用Amzi测试过！和SWI-Prolog，使用来自Cryptarithms.com的那些alphametics示例，其中涉及两个求和，每个求和都有一个唯一的解决方案。我还用一个解决方案（I + AM = BEN）组成了一个示例，以测试正确的回溯。

solveCryptarithm([H1|T1],[H2|T2],Sum) :-
    operandAlign([H1|T1],[H2|T2],Sum,AddTop,AddPad,Carry,TSum,Pool),
    solveCryptarithmAux(H1,H2,AddTop,AddPad,Carry,TSum,Pool).

operandAlign(Add1,Add2,Sum,AddTop,AddPad,Carry,TSum,Pool) :-
    operandSwapPad(Add1,Add2,Length,AddTop,AddPad),
    length(Sum,Size),
    (   Size = Length
     -> ( Carry = 0, Sum = TSum , Pool = [1|Peel] )
     ;  ( Size is Length+1, Carry = 1, Sum = [Carry|TSum], Pool = Peel )
    ),
    Peel = [2,3,4,5,6,7,8,9,0].

operandSwapPad(List1,List2,Length,Longer,Padded) :-
    length(List1,Length1),
    length(List2,Length2),
    (   Length1 >= Length2
     -> ( Length = Length1, Longer = List1, Shorter = List2, Pad is Length1 - Length2 )
     ;  ( Length = Length2, Longer = List2, Shorter = List1, Pad is Length2 - Length1 )
    ),
    zeroPad(Shorter,Pad,Padded).

zeroPad(L,0,L).
zeroPad(L,K,P) :-
    K > 0,
    M is K-1,
    zeroPad([0|L],M,P).

solveCryptarithmAux(_,_,[],[],0,[],_).
solveCryptarithmAux(NZ1,NZ2,[H1|T1],[H2|T2],CarryOut,[H3|T3],Pool) :-
    ( CarryIn = 0 ; CarryIn = 1 ),   /* anticipatory carry */
    (   var(H1)
     -> select(H1,Pool,P_ol)
     ;  Pool = P_ol
    ),
    (   var(H2)
     -> select(H2,P_ol,P__l)
     ;  P_ol = P__l
    ),
    (   var(H3)
     -> ( H3 is H1 + H2 + CarryIn - 10*CarryOut, select(H3,P__l,P___) )
     ;  ( H3 is H1 + H2 + CarryIn - 10*CarryOut, P__l = P___ )
    ),
    NZ1 \== 0,
    NZ2 \== 0,
    solveCryptarithmAux(NZ1,NZ2,T1,T2,CarryIn,T3,P___).

我认为，这说明在“通用”求解器中可以实现从左到右的搜索/求值的优势，与较早的“量身定制”的代码相比，推理次数增加了大约两倍。

Answer 3

注意：这个答案讨论了一种减少需要尝试的组合数量的算法。我不懂Prolog，所以我无法提供任何代码片段。

加速暴力解决方案的技巧是走捷径。如果您可以识别一系列无效的组合，则可以大大减少组合​​的数量。

就拿手上的例子来说吧。当人类解决这个问题时，她立即注意到MONEY有5位数字，而SEND和MORE只有4位，所以MONEY中的M一定是数字1。90%的组合消失了！

在为计算机构建算法时，我们尝试首先使用适用于所有可能输入的快捷方式。如果它们无法提供所需的性能，我们就会开始寻找仅适用于特定输入组合的快捷方式。所以我们暂时保留 M=1 快捷方式。

相反，我会关注最后的数字。我们知道 (D+E) mod 10 = Y。这意味着我们要尝试的组合数量减少了 90%。

这一步应该会使执行时间缩短到不到一分钟。

如果这还不够，我们还能做什么？下一步：查看倒数第二个数字！我们知道（N+R+D+E 的进位）mod 10 = E。

由于我们正在测试最后一位数字的所有有效组合，因此对于每次测试，我们都会知道进位是 0 还是 1。进一步减少要测试的组合数量的复杂性（对于代码）是我们会遇到重复项（一个字母被映射到一个已经分配给另一个字母的数字）。当我们遇到重复项时，我们可以前进到下一个组合，而无需进一步沿着链向下走。

祝你的任务顺利！