COIN-OR::LEMON - Graph Library

source: glpk-cmake/examples/money.mod @ 1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 1.8 KB
Line 
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
26set LETTERS := { 'D', 'E', 'M', 'N', 'O', 'R', 'S', 'Y' };
27/* set of letters */
28
29set DIGITS := 0..9;
30/* set of digits */
31
32var x{i in LETTERS, d in DIGITS}, binary;
33/* x[i,d] = 1 means that letter i is digit d */
34
35s.t. one{i in LETTERS}: sum{d in DIGITS} x[i,d] = 1;
36/* each letter must correspond exactly to one digit */
37
38s.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
42var dig{i in LETTERS};
43/* dig[i] is a digit corresponding to letter i */
44
45s.t. map{i in LETTERS}: dig[i] = sum{d in DIGITS} d * x[i,d];
46
47var carry{1..3}, binary;
48/* carry bits */
49
50s.t. sum1: dig['D'] + dig['E']            = dig['Y'] + 10 * carry[1];
51s.t. sum2: dig['N'] + dig['R'] + carry[1] = dig['E'] + 10 * carry[2];
52s.t. sum3: dig['E'] + dig['O'] + carry[2] = dig['N'] + 10 * carry[3];
53s.t. sum4: dig['S'] + dig['M'] + carry[3] = dig['O'] + 10 * dig['M'];
54s.t. note: dig['M'] >= 1; /* M must not be 0 */
55
56solve;
57/* solve the puzzle */
58
59display dig;
60/* and display its solution */
61
62end;
Note: See TracBrowser for help on using the repository browser.