/*    S E N D
    + M O R E
    ---------
    M O N E Y
*/

solution([S, E, N, D, M, O, R, Y]) :-          /* says SENDMORY is a solution */
    digits(Digits),           /* set of usable digits       */

    element(D, Digits, D1),   /* D E Y column */
    element(E, D1, D2),
    sum(D, E, 0, Y, C1),
    element(Y, D2, D3),

    element(N, D3, D4),       /* N R E column */
    element(R, D4, D5),
    sum(N, R, C1, E, C2),

    element(O, D5, D6),       /* E O N column */
    sum(E, O, C2, N, C3),

    element(S, D6, D7),       /* S M O column */
    element(M, D7, _),
    sum(S, M, C3, O, M),

    M =\= 0.                  /* constrain M to be non-zero */

                    /* element(A, X, Y) says A is an element of X, residue Y */
element(A, [A | X], X). 
element(B, [A | X], [A | Y]) :-
    element(B, X, Y).

sum(A, B, C, Sum, Carry) :-    /* says Sum and Carry are from adding A, B, C */
    Sum is (A + B + C) mod 10,
    Carry is (A + B + C) // 10.

digits([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]).            /* says digits are 0 .. 9 */ 


show([S, E, N, D, M, O, R, Y]) :-     /* shows the result in formatted form */
    nl,
    show_chars([' ', S, E, N, D]),
    show_chars(['+', M, O, R, E]),
    write('----------'), nl,
    show_chars([  M, O, N, E, Y]). 
    
show_chars([]) :-                                  /* shows a list of chars */
    nl.
show_chars([C | Cs]) :-
    write(' '),
    write(C),
    show_chars(Cs).

test :-
    show(['S', 'E', 'N', 'D', 'M', 'O', 'R', 'Y']),
    solution(Solution),
    show(Solution),
    fail ; true.


/* results

           S E N D
         + M O R E
        ----------
         M O N E Y


           9 5 6 7
         + 1 0 8 5
        ----------
         1 0 6 5 2

*/