更快的实现在序言口头算术更快的实现在序言口头算术(Faster implementation of

我已经做了工作一般化口头算术 Prolog中解算器，但它的速度太慢。 这8分钟车程只需运行简单的表达SEND + MORE = MONE Y.有人可以帮助我，使运行速度更快？

/* 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:

这里业绩不佳是由于如果有任何可行的检查之前，在所有可能的字母分配。

我的建议是“早失败，常失败”。 也就是说，尽可能早地推动尽可能多的检查失败到指定的步骤，从而修剪搜索树。

克拉斯Lindbäck提出了一些很好的建议。 作为一个概括，两数相加当传送至多一个在每个地方。 所以不同的数字字母从左至右的分配可以通过补贴来检查在最右边的地方一个尚未未确定套利的可能性。 （当然在最终的“单位”的地方，没有进位）。

这是一个很多东西值得思考，这就是为什么约束逻辑，如垫子建议（以及你已经有fd_all_different / 1拉削），就是这样的便利。

---

添加了：这里的无约束逻辑Prolog的溶液，只使用一个辅助谓词省略/ 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,_).

我们下车到快速启动通过观察m必须从最左边的数字之和，因此1非零进位，而s必须是一些其他的非零数字。 该言论表明，其中其他字母可以确定性地分配基于已作出的选择值的步骤。

---

新增（2）：这里是两个加数，它不必有“地方”相同的长度/数“一般” cryptarithm求解。 为长度/ 2码，省略作为一个相当普遍的内部谓词，并且占用了由Will尼斯的建议，来电/ 3由选择/ 3 SWI-Prolog的用户的方便更换省略 。

我已经与暗洗测试这个！ 和SWI-Prolog的使用这些字母算术例子从Cryptarithms.com其涉及两个被加数，其中的每一个具有唯一的解。 我还由一个例如用一打的解决方案，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的，所以我不能提供任何代码片段。

加快蛮力解决方案的诀窍是快捷方式。 如果能够识别的范围内是无效组合的可以显着地减少组合的数目。

拿在手中的例子。 当人类解决它，她立刻注意到钱5位​​，而SEND多的只有4，所以M在钱一定是数字1，90了组合的％！

当构造算法的计算机上，我们尝试使用适用于所有可能的输入第一个快捷方式。 如果他们不能提供所需的性能，我们开始寻找捷径，只适用于输入的特定组合。 因此，我们离开了M = 1的快捷方式了。

相反，我会集中在最后一位数字。 我们知道，（d + E）MOD 10 = Y。这是我们在组合尝试的数量减少90％。

这一步应该把exacution略低于一分钟。

我们可以做些什么，如果这还不够吗？ 下一步：看倒数第二位！ 我们知道，（N + R +从d + E携带）模10 = E.

由于我们是通过最后一个数字的所有有效组合测试，对于每个测试，我们将知道的进位是0还是1，一种并发症（用于代码）进一步减少待测试的组合的数量是，我们会遇到重复（信被映射到已分配给另一个字母的数字）。 当我们遇到一个重复的，我们可以前进到下一个组合没有进一步下降的链条。

祝你的任务！

Answer 4:

你有

convert([A,B,C,D]) => convert([A,B,C])*10 + D 
 => (convert([A,B])*10+C)*10+D => ... 
 => ((A*10+B)*10+C)*10+D

所以，你可以用一个简单的线性递归表达这一点。

更重要的是，当你选择从您的域中的一个可能的数字0..9 ，你不应该使用数字再进行后续的选择：

selectM([A|As],S,Z):- select(A,S,S1),selectM(As,S1,Z).
selectM([],Z,Z). 

select/3是在SWI的Prolog可用。 这个工具的武装，你可以从你从而缩小域逐渐选择您的数字：

money_puzzle( [[S,E,N,D],[M,O,R,E],[M,O,N,E,Y]]):-
  Dom = [0,1,2,3,4,5,6,7,8,9],
  selectM([D,E],  Dom,Dom1),   add(D,E,0, Y,C1),   % D+E=Y
  selectM([Y,N,R],Dom1,Dom2),  add(N,R,C1,E,C2),   % N+R=E
  select(  O,     Dom2,Dom3),  add(E,O,C2,N,C3),   % E+O=N
  selectM([S,M],  Dom3,_),     add(S,M,C3,O,M),    % S+M=MO
  S \== 0, M \== 0.

我们可以添加两个数字进位，添加产生具有新的进位所得到的数字（比如， 4+8 (0) = 2 (1)即12）：

add(A,B,C1,D,C2):- N is A+B+C1, D is N mod 10, C2 is N // 10 .

因此实现， money_puzzle/1瞬间运行时，由于逐渐性质，其中数字被拾取并且马上测试：

?- time( money_puzzle(X) ).
% 27,653 inferences, 0.02 CPU in 0.02 seconds (100% CPU, 1380662 Lips)
X = [[9, 5, 6, 7], [1, 0, 8, 5], [1, 0, 6, 5, 2]] ;
No
?- time( (money_puzzle(X),fail) ).
% 38,601 inferences, 0.02 CPU in 0.02 seconds (100% CPU, 1927275 Lips)

现在的问题变成，使其通用性。

Answer 5:

以下是一张就可以了。 我用clpfd ， DCG和元谓词 mapfoldl/5 ：

:- meta_predicate mapfoldl(4,?,?,?,?).
mapfoldl(P_4,Xs,Zs, S0,S) :-
   list_mapfoldl_(Xs,Zs, S0,S, P_4).

:- meta_predicate list_mapfoldl_(?,?,?,?,4).
list_mapfoldl_([],[], S,S, _).
list_mapfoldl_([X|Xs],[Y|Ys], S0,S, P_4) :-
   call(P_4,X,Y,S0,S1),
   list_mapfoldl_(Xs,Ys, S1,S, P_4).

让我们把mapfoldl/5很好的利用，并做一些口头算术！

:- use_module(library(clpfd)).
:- use_module(library(lambda)).

digits_number(Ds,Z) :-
   Ds = [D0|_],
   Ds ins 0..9,
   D0 #\= 0,           % most-significant digit must not equal 0
   reverse(Ds,Rs),
   length(Ds,N),
   numlist(1,N,Es),    % exponents (+1)
   maplist(\E1^V^(V is 10**(E1-1)),Es,Ps),
   scalar_product(Ps,Rs,#=,Z).

list([]) --> [].
list([E|Es]) --> [E], list(Es).

cryptarithexpr_value([V|Vs],X) -->
   { digits_number([V|Vs],X) },
   list([V|Vs]).
cryptarithexpr_value(T0,T) -->
   { functor(T0,F,A)  },
   { dif(F-A,'.'-2)   },
   { T0 =.. [F|Args0] },
   mapfoldl(cryptarithexpr_value,Args0,Args),
   { T  =.. [F|Args] }.

crypt_arith_(Expr,Zs) :-
   phrase(cryptarithexpr_value(Expr,Goal),Zs0),
   (  member(Z,Zs0), \+var(Z)
   -> throw(error(uninstantiation_error(Expr),crypt_arith_/2)) 
   ;  true 
   ),
   sort(Zs0,Zs),
   all_different(Zs),
   call(Goal).

快速而肮脏的黑客转储发现所有的解决方案 ：

solve_n_dump(Opts,Eq) :-
   (  crypt_arith_(Eq,Zs),
      labeling(Opts,Zs),
      format('Eq = (~q), Zs = ~q.~n',[Eq,Zs]),
      false
   ;  true
   ).

solve_n_dump(Eq) :- solve_n_dump([],Eq).

让我们来试试吧！

?- solve_n_dump([S,E,N,D]+[M,O,R,E] #= [M,O,N,E,Y]).
Eq = ([9,5,6,7]+[1,0,8,5]#=[1,0,6,5,2]), Zs = [9,5,6,7,1,0,8,2].
true.

?- solve_n_dump([C,R,O,S,S]+[R,O,A,D,S] #= [D,A,N,G,E,R]).
Eq = ([9,6,2,3,3]+[6,2,5,1,3]#=[1,5,8,7,4,6]), Zs = [9,6,2,3,5,1,8,7,4].
true.

?- solve_n_dump([F,O,R,T,Y]+[T,E,N]+[T,E,N] #= [S,I,X,T,Y]).
Eq = ([2,9,7,8,6]+[8,5,0]+[8,5,0]#=[3,1,4,8,6]), Zs = [2,9,7,8,6,5,0,3,1,4].
true.

?- solve_n_dump([E,A,U]*[E,A,U] #= [O,C,E,A,N]).
Eq = ([2,0,3]*[2,0,3]#=[4,1,2,0,9]), Zs = [2,0,3,4,1,9].
true.

?- solve_n_dump([N,U,M,B,E,R] #= 3*[P,R,I,M,E]).
% same as:      [N,U,M,B,E,R] #= [P,R,I,M,E]+[P,R,I,M,E]+[P,R,I,M,E]
Eq = (3*[5,4,3,2,8]#=[1,6,2,9,8,4]), Zs = [5,4,3,2,8,1,6,9].
true.

?- solve_n_dump(3*[C,O,F,F,E,E] #= [T,H,E,O,R,E,M]).
Eq = (3*[8,3,1,1,9,9]#=[2,4,9,3,5,9,7]), Zs = [8,3,1,9,2,4,5,7].
true.

让我们做更多的一些尝试一些不同的标签选项 ：

?- time(solve_n_dump([],[D,O,N,A,L,D]+[G,E,R,A,L,D] #= [R,O,B,E,R,T])).
Eq = ([5,2,6,4,8,5]+[1,9,7,4,8,5]#=[7,2,3,9,7,0]), Zs = [5,2,6,4,8,1,9,7,3,0].
% 35,696,801 inferences, 3.929 CPU in 3.928 seconds (100% CPU, 9085480 Lips)
true.

?- time(solve_n_dump([ff],[D,O,N,A,L,D]+[G,E,R,A,L,D] #= [R,O,B,E,R,T])).
Eq = ([5,2,6,4,8,5]+[1,9,7,4,8,5]#=[7,2,3,9,7,0]), Zs = [5,2,6,4,8,1,9,7,3,0].
% 2,902,871 inferences, 0.340 CPU in 0.340 seconds (100% CPU, 8533271 Lips)
true.

Answer 6:

将内斯风格，广义（但假设length(A) <= length(B)求解器：

money_puzzle(A, B, C) :-
    maplist(reverse, [A,B,C], [X,Y,Z]),
    numlist(0, 9, Dom),
    swc(0, Dom, X,Y,Z),
    A \= [0|_], B \= [0|_].

swc(C, D0, [X|Xs], [Y|Ys], [Z|Zs]) :-
    peek(D0, X, D1),
    peek(D1, Y, D2),
    peek(D2, Z, D3),
    S is X+Y+C,
    ( S > 9 -> Z is S - 10, C1 = 1 ; Z = S, C1 = 0 ),
    swc(C1, D3, Xs, Ys, Zs).
swc(C, D0, [], [Y|Ys], [Z|Zs]) :-
    peek(D0, Y, D1),
    peek(D1, Z, D2),
    S is Y+C,
    ( S > 9 -> Z is S - 10, C1 = 1 ; Z = S, C1 = 0 ),
    swc(C1, D2, [], Ys, Zs).
swc(0, _, [], [], []).
swc(1, _, [], [], [1]).

peek(D, V, R) :- var(V) -> select(V, D, R) ; R = D.

性能：

?- time(money_puzzle([S,E,N,D],[M,O,R,E],[M,O,N,E,Y])).
% 38,710 inferences, 0.016 CPU in 0.016 seconds (100% CPU, 2356481 Lips)
S = 9,
E = 5,
N = 6,
D = 7,
M = 1,
O = 0,
R = 8,
Y = 2 ;
% 15,287 inferences, 0.009 CPU in 0.009 seconds (99% CPU, 1685686 Lips)
false.

?-  time(money_puzzle([D,O,N,A,L,D],[G,E,R,A,L,D],[R,O,B,E,R,T])).
% 14,526 inferences, 0.008 CPU in 0.008 seconds (99% CPU, 1870213 Lips)
D = 5,
O = 2,
N = 6,
A = 4,
L = 8,
G = 1,
E = 9,
R = 7,
B = 3,
T = 0 ;
% 13,788 inferences, 0.009 CPU in 0.009 seconds (99% CPU, 1486159 Lips)
false.

文章来源: Faster implementation of verbal arithmetic in Prolog