lemon-project-template-glpk

annotate deps/glpk/examples/money.mod @ 11:4fc6ad2fb8a6

find changesets by author, revision, files, or words in the commit message
Test GLPK in src/main.cc
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 21:43:29 +0100
parents
children
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;