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