我已经在Prolog中制作了一个可以使用的通用verbal arithmetic求解器，但是它太慢了。运行简单表达式S E N D + M O R E = M O N E 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.
最佳答案
考虑在SWI-Prolog中使用finite domain constraints:
:- 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.