alpar@1: /* CRYPTO, a crypto-arithmetic puzzle */
alpar@1: 
alpar@1: /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
alpar@1: 
alpar@1: /* This problem comes from the newsgroup rec.puzzle.
alpar@1:    The numbers from 1 to 26 are assigned to the letters of the alphabet.
alpar@1:    The numbers beside each word are the total of the values assigned to
alpar@1:    the letters in the word (e.g. for LYRE: L, Y, R, E might be to equal
alpar@1:    5, 9, 20 and 13, or any other combination that add up to 47).
alpar@1:    Find the value of each letter under the equations:
alpar@1: 
alpar@1:    BALLET  45     GLEE  66     POLKA      59     SONG     61
alpar@1:    CELLO   43     JAZZ  58     QUARTET    50     SOPRANO  82
alpar@1:    CONCERT 74     LYRE  47     SAXOPHONE 134     THEME    72
alpar@1:    FLUTE   30     OBOE  53     SCALE      51     VIOLIN  100
alpar@1:    FUGUE   50     OPERA 65     SOLO       37     WALTZ    34
alpar@1: 
alpar@1:    Solution:
alpar@1:    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
alpar@1:    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
alpar@1: 
alpar@1:    Reference:
alpar@1:    Koalog Constraint Solver <http://www.koalog.com/php/jcs.php>,
alpar@1:    Simple problems, the crypto-arithmetic puzzle ALPHACIPHER. */
alpar@1: 
alpar@1: set LETTERS :=
alpar@1: {     'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
alpar@1:       'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'
alpar@1: };
alpar@1: /* set of letters */
alpar@1: 
alpar@1: set VALUES := 1..card(LETTERS);
alpar@1: /* set of values assigned to the letters */
alpar@1: 
alpar@1: set WORDS;
alpar@1: /* set of words */
alpar@1: 
alpar@1: param total{word in WORDS};
alpar@1: /* total[word] is the total of the values assigned to the letters in
alpar@1:    the word */
alpar@1: 
alpar@1: var x{i in LETTERS, j in VALUES}, binary;
alpar@1: /* x[i,j] = 1 means that letter i is assigned value j */
alpar@1: 
alpar@1: s.t. phi{i in LETTERS}: sum{j in VALUES} x[i,j] = 1;
alpar@1: 
alpar@1: s.t. psi{j in VALUES}: sum{i in LETTERS} x[i,j] = 1;
alpar@1: 
alpar@1: s.t. eqn{word in WORDS}: sum{k in 1..length(word), j in VALUES}
alpar@1:       j * x[substr(word,k,1), j] = total[word];
alpar@1: 
alpar@1: solve;
alpar@1: 
alpar@1: printf{i in LETTERS} "  %s", i;
alpar@1: printf "\n";
alpar@1: 
alpar@1: printf{i in LETTERS} " %2d", sum{j in VALUES} j * x[i,j];
alpar@1: printf "\n";
alpar@1: 
alpar@1: data;
alpar@1: 
alpar@1: param :  WORDS :   total :=
alpar@1:          BALLET       45
alpar@1:          CELLO        43
alpar@1:          CONCERT      74
alpar@1:          FLUTE        30
alpar@1:          FUGUE        50
alpar@1:          GLEE         66
alpar@1:          JAZZ         58
alpar@1:          LYRE         47
alpar@1:          OBOE         53
alpar@1:          OPERA        65
alpar@1:          POLKA        59
alpar@1:          QUARTET      50
alpar@1:          SAXOPHONE   134
alpar@1:          SCALE        51
alpar@1:          SOLO         37
alpar@1:          SONG         61
alpar@1:          SOPRANO      82
alpar@1:          THEME        72
alpar@1:          VIOLIN      100
alpar@1:          WALTZ        34 ;
alpar@1: 
alpar@1: end;