Prolog implementation of SEND + MORE = MONEY isn't finding a result

Question

I'm getting started with Prolog, and decided to try the famous SEND+MORE=MONEY puzzle, as it seemed fairly straightforward. However, my implementation does find a result.

Can anyone see what I did wrong?

smm([S, E, N, D, M, O, R, Y]) :-
  maplist(between(0, 9), [S, E, N, D, M, O, R, Y]),
  Line1 is           S*1000 + E*100 + N*10 + D,
  Line2 is           M*1000 + O*100 + R*10 + E,
  Sum   is M*10000 + O*1000 + N*100 + E*10 + Y,
  Sum = Line1 + Line2.

I'm not sure this is even the best way to approach this puzzle, so please feel free to make any (constructive!) comments on my code.

Update: Just in case anyone comes here looking for a solution to the puzzle, the code above wouldn't have worked anyway, as I forgot two important constraints, that M should not be zero, and that no two variables should be the same digit.

My amended code that works is as follows, but note that it slow. It took about 84s to solve on my machine, as compared to the code posted below by brebs, which solved it faster than I could see!

smm([S, E, N, D, M, O, R, Y]) :-
  maplist(between(0, 9), [S, E, N, D, M, O, R, Y]),
  M =\= 0,
  unique([S, E, N, D, M, O, R, Y]),
  Line1 is           S*1000 + E*100 + N*10 + D,
  Line2 is           M*1000 + O*100 + R*10 + E,
  Sum   is M*10000 + O*1000 + N*100 + E*10 + Y,
  Sum   is Line1 + Line2.

unique([]).
unique([H|T]) :- not(memberchk(H, T)), unique(T).

Answer 1

Just as you use is to compute the arithmetic expressions for Line1, Line2 and Sum, you need to use it for Line1 + Line2.

Answer 2

First of all, this problem is much better suited for clpfd. See these questions.

How could you have found that error yourself? After all, not each and every error is so easy to spot. Here is a method you can apply in any situation where you get an unexpected failure.

:- op(950, fy, *).

*_G_0.

smm(_/*[S, E, N, D, M, O, R, Y]*/) :-
   maplist(between(0, 9), [S, E, N, D, M, O, R, Y]),
   * Line1 is           S*1000 + E*100 + N*10 + D,
   * Line2 is           M*1000 + O*100 + R*10 + E,
   Sum   is M*10000 + O*1000 + N*100 + E*10 + Y,
   Sum = Line1 + Line2.

?- smm(Xs).
   false, unexpected. % takes quite some time

Because this fragment already fails, also your original program fails. And we can elaborate this even further on by expanding maplist/2.

smm(_/*[S, E, N, D, M, O, R, Y]*/) :-
   * between(0, 9, S),
   between(0, 9, E),
   between(0, 9, N),
   * between(0, 9, D),
   between(0, 9, M),
   between(0, 9, O),
   * between(0, 9, R),
   between(0, 9, Y),
   * Line1 is           S*1000 + E*100 + N*10 + D,
   * Line2 is           M*1000 + O*100 + R*10 + E,
   Sum   is M*10000 + O*1000 + N*100 + E*10 + Y,
   Sum = Line1 + Line2.

?- smm(Xs).
   false, unexpected. % much faster

So anywhere in the remaining visible part there must be an error.

Answer 3

Many months ago, I tweaked a solution I found online (which no longer exists). Not saying it's perfect code, but food for thought:

all_diff(L) :-
    \+ (append(_,[X|R],L), memberchk(X,R)).

digit(N) :-
    between(0, 9, N).

carry(0).
carry(1).

go:-
    send_more_money([S,E,N,D,M,O,R,Y]),
    result([S,E,N,D,M,O,R,Y]).

result([S,E,N,D,M,O,R,Y]):-
    nl, write('  S E N D'), tab(5), out([' ', S, E, N, D]),
    nl, write('  M O R E'), tab(5), out([' ', M, O, R, E]),
    nl, write('---------'), tab(5), write(--------------),
    nl, write('M O N E Y'), tab(5), out([M, O, N, E, Y]),
    nl.

out([]).
out([C | Rest]) :-
    write(C),
    write(' '),
    out(Rest).

send_more_money(Ds):-
    Ds = [S, E, N, D, M, O, R, Y],
    % A multi-digit number cannot start with 0
    dif(M, 0),
    column(0, 0, C2, M,  0),  % Cn are the carries
    column(S, M, C3, O, C2),
    column(E, O, C4, N, C3),
    column(N, R, C4, E, C5),
    column(D, E,  0, Y, C5),
    all_diff(Ds).

column(DigitInLine1, DigitInLine2, Carry, DigitInLine3, NewCarry) :-
    carry(Carry),  % try 0 and 1 in turn
    digit(DigitInLine1),
    digit(DigitInLine2),
    Sum is DigitInLine1 + DigitInLine2 + Carry,
    NewCarry is Sum // 10,
    DigitInLine3 is Sum - (10 * NewCarry).

:- writeln('The puzzle SEND+MORE=MONEY has been loaded').
:- writeln('To solve it: go.').

Result in swi-prolog:

?- time(go).

  S E N D       9 5 6 7 
  M O R E       1 0 8 5 
---------     --------------
M O N E Y     1 0 6 5 2 
% 2,436 inferences, 0.000 CPU in 0.000 seconds (99% CPU, 5432383 Lips)
true ;
% 1,223 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 10963792 Lips)
false.

Here's a (tidied but slower) variation:

send_more_money(Ds):-
    Ds = [S, E, N, D, M, O, R, Y],
    numlist(0, 9, NL),
    % A multi-digit number cannot start with 0
    dif(M, 0),
    digits_perm(Ds, NL),
    column(D, E,  0, Y, C1),
    column(N, R, C1, E, C2),
    column(E, O, C2, N, C3),
    column(S, M, C3, O, C4),
    column(0, 0, C4, M,  0).  % Cn are the carries

column(DigitInLine1, DigitInLine2, Carry, DigitInLine3, NewCarry) :-
    Sum is DigitInLine1 + DigitInLine2 + Carry,
    NewCarry is Sum // 10,
    DigitInLine3 is Sum - (10 * NewCarry).

digits_perm([], _).
digits_perm([H|T], NL) :-
    select(H, NL, NL0),
    digits_perm(T, NL0).

Result in swi-prolog:

?- time(send_more_money(Ds)).
% 12,984,725 inferences, 0.782 CPU in 0.782 seconds (100% CPU, 16600060 Lips)
Ds = [9, 5, 6, 7, 1, 0, 8, 2] ;
% 480,046 inferences, 0.030 CPU in 0.030 seconds (100% CPU, 16230337 Lips)
false.

Answer 4

Here is a generic solver:

add_digits_09(DigRows, DigSum) :-
    reverse_lists(DigRows, DigRowsR),
    reverse(DigSum, DigSumR),
    numlist(0, 9, Digits),
    % Start digit cannot be zero
    DigSum = [DSH|_],
    dif(DSH, 0),
    add_digits_09_(DigSumR, DigRowsR, Digits, 0).

add_digits_09_([], _, _, 0).
add_digits_09_([Sum|DigSum], DigRows, Digits, Carry) :-
    % Sum the column
    sum_column(DigRows, Digits, Carry, ColSum, Digits0, DigRows0),
    (   ColSum < 10
    ->  Sum = ColSum,
        Carry1 = 0
    ;   Sum is ColSum - 10,
        Carry1 = 1
    ),
    digit_select(Sum, Digits0, Digits00),
    add_digits_09_(DigSum, DigRows0, Digits00, Carry1).

reverse_lists([], []).
reverse_lists([H|T], [R|Rs]) :-
    reverse(H, R),
    reverse_lists(T, Rs).

sum_column(DigRows, Digits, Carry, ColSum, Digits0, DigRows0) :-
    sum_column_(DigRows, Digits, 0, ColSum0, Digits0, DigRows0),
    ColSum is ColSum0 + Carry.

sum_column_([], Digits, Sum, Sum, Digits, []).
% F means final
sum_column_([H|T], Digits, Upto, Sum, Digits0F, [DT|DigRows0]) :-
    H = [D|DT],
    digit_select(D, Digits, Digits0),
    Upto1 is Upto + D,
    sum_column_(T, Digits0, Upto1, Sum, Digits0F, DigRows0).

digit_select(D, Digits, Digits0) :-
    (   var(D)
    ->  select(D, Digits, Digits0)
    % Ensure is gone from list
    ;   select(D, Digits, Digits0)
    ->  true
    % Is already gone
    ;   Digits0 = Digits
    ).

Results in swi-prolog:

?- time(add_digits_09([[0,S,E,N,D], [0,M,O,R,E]], [M,O,N,E,Y])).
% 156,397 inferences, 0.006 CPU in 0.006 seconds (100% CPU, 24700704 Lips)
S = 9,
E = 5,
N = 6,
D = 7,
M = 1,
O = 0,
R = 8,
Y = 2 ;
% 43,689 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 22319777 Lips)
false.

?- time(add_digits_09([[0,0,E,A,T], [0,T,H,A,T]], [A,P,P,L,E])).
% 21,141 inferences, 0.001 CPU in 0.001 seconds (99% CPU, 17262144 Lips)
E = 8,
A = 1,
T = 9,
H = 2,
P = 0,
L = 3 ;
% 2,153 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 5315918 Lips)
false.

?- A = 7, time(add_digits_09([[0,C,R,O,S,S], [0,R,O,A,D,S]], [D,A,N,G,E,R])).
% 26,171 inferences, 0.003 CPU in 0.003 seconds (100% CPU, 9876777 Lips)
A = G, G = 7,
C = 9,
R = N, N = 8,
O = 0,
S = 4,
D = 1,
E = 5 ;
% 34,899 inferences, 0.006 CPU in 0.006 seconds (100% CPU, 5704604 Lips)
false.