| rev |
line source |
|
alpar@9
|
1 /* MONEY, a crypto-arithmetic puzzle */
|
|
alpar@9
|
2
|
|
alpar@9
|
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
|
|
alpar@9
|
4
|
|
alpar@9
|
5 /* This is the classic example of a crypto-arithmetic puzzle published
|
|
alpar@9
|
6 in the Strand Magazine by Henry Dudeney:
|
|
alpar@9
|
7
|
|
alpar@9
|
8 S E N D
|
|
alpar@9
|
9 +
|
|
alpar@9
|
10 M O R E
|
|
alpar@9
|
11 ---------
|
|
alpar@9
|
12 M O N E Y
|
|
alpar@9
|
13
|
|
alpar@9
|
14 In this puzzle the same letters mean the same digits. The question
|
|
alpar@9
|
15 is: how to replace all the letters with the respective digits that
|
|
alpar@9
|
16 makes the calculation correct?
|
|
alpar@9
|
17
|
|
alpar@9
|
18 The solution to this puzzle is:
|
|
alpar@9
|
19 O = 0, M = 1, Y = 2, E = 5, N = 6, D = 7, R = 8, and S = 9.
|
|
alpar@9
|
20
|
|
alpar@9
|
21 References:
|
|
alpar@9
|
22 H. E. Dudeney, in Strand Magazine vol. 68 (July 1924), pp. 97, 214.
|
|
alpar@9
|
23
|
|
alpar@9
|
24 (From Wikipedia, the free encyclopedia.) */
|
|
alpar@9
|
25
|
|
alpar@9
|
26 set LETTERS := { 'D', 'E', 'M', 'N', 'O', 'R', 'S', 'Y' };
|
|
alpar@9
|
27 /* set of letters */
|
|
alpar@9
|
28
|
|
alpar@9
|
29 set DIGITS := 0..9;
|
|
alpar@9
|
30 /* set of digits */
|
|
alpar@9
|
31
|
|
alpar@9
|
32 var x{i in LETTERS, d in DIGITS}, binary;
|
|
alpar@9
|
33 /* x[i,d] = 1 means that letter i is digit d */
|
|
alpar@9
|
34
|
|
alpar@9
|
35 s.t. one{i in LETTERS}: sum{d in DIGITS} x[i,d] = 1;
|
|
alpar@9
|
36 /* each letter must correspond exactly to one digit */
|
|
alpar@9
|
37
|
|
alpar@9
|
38 s.t. alldiff{d in DIGITS}: sum{i in LETTERS} x[i,d] <= 1;
|
|
alpar@9
|
39 /* different letters must correspond to different digits; note that
|
|
alpar@9
|
40 some digits may not correspond to any letters at all */
|
|
alpar@9
|
41
|
|
alpar@9
|
42 var dig{i in LETTERS};
|
|
alpar@9
|
43 /* dig[i] is a digit corresponding to letter i */
|
|
alpar@9
|
44
|
|
alpar@9
|
45 s.t. map{i in LETTERS}: dig[i] = sum{d in DIGITS} d * x[i,d];
|
|
alpar@9
|
46
|
|
alpar@9
|
47 var carry{1..3}, binary;
|
|
alpar@9
|
48 /* carry bits */
|
|
alpar@9
|
49
|
|
alpar@9
|
50 s.t. sum1: dig['D'] + dig['E'] = dig['Y'] + 10 * carry[1];
|
|
alpar@9
|
51 s.t. sum2: dig['N'] + dig['R'] + carry[1] = dig['E'] + 10 * carry[2];
|
|
alpar@9
|
52 s.t. sum3: dig['E'] + dig['O'] + carry[2] = dig['N'] + 10 * carry[3];
|
|
alpar@9
|
53 s.t. sum4: dig['S'] + dig['M'] + carry[3] = dig['O'] + 10 * dig['M'];
|
|
alpar@9
|
54 s.t. note: dig['M'] >= 1; /* M must not be 0 */
|
|
alpar@9
|
55
|
|
alpar@9
|
56 solve;
|
|
alpar@9
|
57 /* solve the puzzle */
|
|
alpar@9
|
58
|
|
alpar@9
|
59 display dig;
|
|
alpar@9
|
60 /* and display its solution */
|
|
alpar@9
|
61
|
|
alpar@9
|
62 end;
|
