source: lemon-project-template-glpk/deps/glpk/examples/crypto.mod @ 9:33de93886c88

/* CRYPTO, a crypto-arithmetic puzzle */

/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */

/* This problem comes from the newsgroup rec.puzzle.
   The numbers from 1 to 26 are assigned to the letters of the alphabet.
   The numbers beside each word are the total of the values assigned to
   the letters in the word (e.g. for LYRE: L, Y, R, E might be to equal
   5, 9, 20 and 13, or any other combination that add up to 47).
   Find the value of each letter under the equations:

   BALLET  45     GLEE  66     POLKA      59     SONG     61
   CELLO   43     JAZZ  58     QUARTET    50     SOPRANO  82
   CONCERT 74     LYRE  47     SAXOPHONE 134     THEME    72
   FLUTE   30     OBOE  53     SCALE      51     VIOLIN  100
   FUGUE   50     OPERA 65     SOLO       37     WALTZ    34

   Solution:
   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
   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

   Reference:
   Koalog Constraint Solver <http://www.koalog.com/php/jcs.php>,
   Simple problems, the crypto-arithmetic puzzle ALPHACIPHER. */

set LETTERS :=
{     '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'
};
/* set of letters */

set VALUES := 1..card(LETTERS);
/* set of values assigned to the letters */

set WORDS;
/* set of words */

param total{word in WORDS};
/* total[word] is the total of the values assigned to the letters in
   the word */

var x{i in LETTERS, j in VALUES}, binary;
/* x[i,j] = 1 means that letter i is assigned value j */

s.t. phi{i in LETTERS}: sum{j in VALUES} x[i,j] = 1;

s.t. psi{j in VALUES}: sum{i in LETTERS} x[i,j] = 1;

s.t. eqn{word in WORDS}: sum{k in 1..length(word), j in VALUES}
      j * x[substr(word,k,1), j] = total[word];

solve;

printf{i in LETTERS} "  %s", i;
printf "\n";

printf{i in LETTERS} " %2d", sum{j in VALUES} j * x[i,j];
printf "\n";

data;

param :  WORDS :   total :=
         BALLET       45
         CELLO        43
         CONCERT      74
         FLUTE        30
         FUGUE        50
         GLEE         66
         JAZZ         58
         LYRE         47
         OBOE         53
         OPERA        65
         POLKA        59
         QUARTET      50
         SAXOPHONE   134
         SCALE        51
         SOLO         37
         SONG         61
         SOPRANO      82
         THEME        72
         VIOLIN      100
         WALTZ        34 ;

end;