Re: Riddle Solver send+more=money

Andreas Kochenburger <akk@xxxxxxxxxx> wrote in message news:<3v9p61tsn7mn9qm3768o3kqoqnv4tbp24k@xxxxxxx>...
> Hi,
> I had my last contact with Turbo Prolog < 20 years ago.
>
> Now my son came home with a riddle that he wanted to solve:
> A lazy student wrote his fater a letter asking for more money. The
> father responded: I'll send you MONEY if you can answer how much it'll
> be. The amount is defined by SEND+MORE=MONEY, whereby each letter
> stands for a number 0..9.
>
> Of course we found the solution. Then my son wanted to program a brute
> force solver in Delphi. I answered: there is a very elegant
> programming language called Prolog that is very good at solving such
> kind of problems. He answered: show me. And now I'm stuck with a red
> face ;-)
>
> I fumbled and fumbled... all I get is error messages. I am looking for
> an elegant solution, not a brute force looping, that would be faster
> in C.
>
> Could somebody help a red-faced father? I promise I won't cheat ;-)
> I'll give credits to the author and prove to my son how helpful a
> benevolent newsgroup can be!!!
>
> Cheers, Andreas
>
> http://www.minforth.net.ms/

A Constraint solution is much more expressive and offers better
performance.

I also think it is easier to understand as the determinism of the
programmed solution offered before is not necessary for such a
small problem.



:- import(const_domain).

send([[S,E,N,D], [M,O,R,E], [M,O,N,E,Y]]) :-
Digits = [M,O,S,N,R,E,D,Y],
Carries = [C1,C2,C3,C4],
Digits in 0..9,
Carries in 0..1,

Y + 10 * C1 ?= E + D,
E + 10 * C2 ?= R + N + C1,
N + 10 * C3 ?= O + E + C2,
O + 10 * C4 ?= M + S + C3,
M ?= C4,

M ?>= 1,
S ?>= 1,
all_distinct(Digits),
label(Digits).
.