Here I take it upon myself. I use clpfd , dcg , and 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).
Put mapfoldl/5 for good use and do some verbal arithmetic!
:- 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(FA,'.'-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).
Quick and dirty hack all the solutions found:
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).
Give it a try!
? - 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, nine].
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
Take a few more and try a few options:
? - 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