これが私の見解です。clpfd、dcg、およびmeta-predicate を使用します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]。
真実。
?- 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]。
真実。
?- 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]。
真実。
?- solve_n_dump([E,A,U]*[E,A,U] #= [O,C,E,A,N])。
式 = ([2,0,3]*[2,0,3]#=[4,1,2,0,9])、Zs = [2,0,3,4,1,9]。
真実。
?- solve_n_dump([N、U、M、B、E、R] #= 3*[P、R、I、M、E])。
% 以下と同じ: [N,U,M,B,E,R] #= [P,R,I,M,E]+[P,R,I,M,E]+[P,R,I,自分]
Eq = (3*[5,4,3,2,8]#=[1,6,2,9,8,4])、Zs = [5,4,3,2,8,1,6, 9]。
真実。
?- 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]。
真実。
もう少しやって、いくつかの異なるラベル付けオプションを試してみましょう:
?- 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 推論、3.928 秒で 3.929 CPU (100% CPU、9085480 リップ)
真実。
?- 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 推論、0.340秒で 0.340 CPU (100% CPU、8533271 リップ)
真実。