1

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).
Avrohom Yisroel
  • 8,555
  • 8
  • 50
  • 106
  • You should understand the differences between `is`, `=:=`, `=`, `==` and so on. Those are documented well enough, it just takes reading and trying things out. – TA_intern Mar 23 '23 at 05:04
  • @TA_intern I'm learning slowly, just haven't got my head round them yet! – Avrohom Yisroel Mar 23 '23 at 14:31
  • @AvrohomYisroel if you were writing your code in Python it would be eight nested loops `for S in range(0,9): for E in range(0,9): for N in range(0,9):` and is a brute force counter from 0 through 99,999,999 with ~14 sums to test each one; that's one and a half billion operations to try all of them. Any approach which is algorithmically more clever, reasons more about how the sum constrains the possible values for each variable and narrows the search space has the potential to run much faster. (That's one way clpfd helps, it can reason about solving arithmetic equations). – TessellatingHeckler Mar 23 '23 at 18:30

4 Answers4

2

First of all, this problem is much better suited for . 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.

false
  • 10,264
  • 13
  • 101
  • 209
  • Thanks for the reply, but you lost me! Remember, I'm just getting started with Prolog, so things like [clpfd] (which looks hugely powerful) are way beyond my current understanding. Also, as part of my learning, I want to try doing things like this explicitly, as it's a great way to learn the language. Once I have a good understanding, I can take advantage of libraries and packages to make coding easier. – Avrohom Yisroel Mar 23 '23 at 14:45
  • Also, please can you explain a bit more about how I'd use `op`? It looks very helpful, but [the docs](https://www.swi-prolog.org/pldoc/man?predicate=op/3) are a bit obscure for the beginner, and I'm not sure how I would use this to see the results you posted. Sorry if this is a dumb question, but it's all somewhat overwhelming when I'm still taking baby steps with this wonderful language. Thanks again. – Avrohom Yisroel Mar 23 '23 at 14:47
  • That's a declaration for this operator. Write it as I did into the same file with the program. And for a beginner,it's simple: Do not define your own operators at all :-) – false Mar 23 '23 at 15:12
  • 1
    As for clpfd, many consider this even simpler than using `is` and the like.. Just look at the solutions under the tag. – false Mar 23 '23 at 15:14
  • 1
    Thanks for both comments. I'll add them to my ever-growing list of things I need to learn about Prolog! – Avrohom Yisroel Mar 23 '23 at 15:35
1

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

Scott Hunter
  • 48,888
  • 12
  • 60
  • 101
  • Please can you explain why I needed `is` rather than `=` there? I thought `is` was for binding values and `=` was for comparing, which is why I used `=` on that last line, as I was comparing one previously bound variable with the sum of two previously bound variables. – Avrohom Yisroel Mar 22 '23 at 23:42
  • I also realised after making your change that I got the puzzle wrong. I needed to check that `M` was not zero, and that all the variables were different. Once I added those lines in, it solved the puzzle. Took 84 seconds, which surprised me, but was still a lot quicker than it would have taken me! – Avrohom Yisroel Mar 22 '23 at 23:43
  • @AvrohomYisroel "*as I was comparing one previously bound variable with the sum of two previously bound variables*" - `Line1 + Line2` is not the sum of two previously bound variables, it's the arithmetic equation which would become the sum if it was evaluated. `=` does not evaluate those, `is` does evaluate them. – TessellatingHeckler Mar 23 '23 at 02:42
1

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.
brebs
  • 3,462
  • 2
  • 3
  • 12
  • Thanks for posting that. It's way more complex than my code, but runs almost instantly, as compared to the 84s mine took. It's going to take me some time to digest your code and understand it, but I can see there's plenty to learn here! – Avrohom Yisroel Mar 23 '23 at 14:32
  • 1
    @AvrohomYisroel: Better spend your time using `clpfd` instead. This solutions has a lot of quite strange implicit assumptions like `M = 1` and `S \= 0` which are not evident and should rather be found out by the program itself. – false Mar 24 '23 at 11:19
  • @false Thanks, I am looking at it, but it's just so much information to take in at once. I'm still down at the bottom of the learning curve, so am trying to get my head around Prolog itself. Adding in a package like this at the same time is proving quite a challenge! Not giving up, but it's going slowly. – Avrohom Yisroel Mar 24 '23 at 15:08
  • I've replaced the (unfair optimization) `M = 1` with `dif(M, 0)`, which exists to prevent answers where the starting digit of a number is zero. This has little effect on the original version, but does slow down the "tidied alternative". – brebs Mar 25 '23 at 21:14
0

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.
brebs
  • 3,462
  • 2
  • 3
  • 12