COIN-OR::LEMON - Graph Library

source: glpk-cmake/examples/crypto.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: 2.4 KB
Line 
1/* CRYPTO, a crypto-arithmetic puzzle */
2
3/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
4
5/* This problem comes from the newsgroup rec.puzzle.
6   The numbers from 1 to 26 are assigned to the letters of the alphabet.
7   The numbers beside each word are the total of the values assigned to
8   the letters in the word (e.g. for LYRE: L, Y, R, E might be to equal
9   5, 9, 20 and 13, or any other combination that add up to 47).
10   Find the value of each letter under the equations:
11
12   BALLET  45     GLEE  66     POLKA      59     SONG     61
13   CELLO   43     JAZZ  58     QUARTET    50     SOPRANO  82
14   CONCERT 74     LYRE  47     SAXOPHONE 134     THEME    72
15   FLUTE   30     OBOE  53     SCALE      51     VIOLIN  100
16   FUGUE   50     OPERA 65     SOLO       37     WALTZ    34
17
18   Solution:
19   A, B,C, D, E,F, G, H, I, J, K,L,M, N, O, P,Q, R, S,T,U, V,W, X, Y, Z
20   5,13,9,16,20,4,24,21,25,17,23,2,8,12,10,19,7,11,15,3,1,26,6,22,14,18
21
22   Reference:
23   Koalog Constraint Solver <http://www.koalog.com/php/jcs.php>,
24   Simple problems, the crypto-arithmetic puzzle ALPHACIPHER. */
25
26set LETTERS :=
27{     'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
28      'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'
29};
30/* set of letters */
31
32set VALUES := 1..card(LETTERS);
33/* set of values assigned to the letters */
34
35set WORDS;
36/* set of words */
37
38param total{word in WORDS};
39/* total[word] is the total of the values assigned to the letters in
40   the word */
41
42var x{i in LETTERS, j in VALUES}, binary;
43/* x[i,j] = 1 means that letter i is assigned value j */
44
45s.t. phi{i in LETTERS}: sum{j in VALUES} x[i,j] = 1;
46
47s.t. psi{j in VALUES}: sum{i in LETTERS} x[i,j] = 1;
48
49s.t. eqn{word in WORDS}: sum{k in 1..length(word), j in VALUES}
50      j * x[substr(word,k,1), j] = total[word];
51
52solve;
53
54printf{i in LETTERS} "  %s", i;
55printf "\n";
56
57printf{i in LETTERS} " %2d", sum{j in VALUES} j * x[i,j];
58printf "\n";
59
60data;
61
62param :  WORDS :   total :=
63         BALLET       45
64         CELLO        43
65         CONCERT      74
66         FLUTE        30
67         FUGUE        50
68         GLEE         66
69         JAZZ         58
70         LYRE         47
71         OBOE         53
72         OPERA        65
73         POLKA        59
74         QUARTET      50
75         SAXOPHONE   134
76         SCALE        51
77         SOLO         37
78         SONG         61
79         SOPRANO      82
80         THEME        72
81         VIOLIN      100
82         WALTZ        34 ;
83
84end;
Note: See TracBrowser for help on using the repository browser.