$title Alphametics - A Mathematical Puzzle (ALPHAMET,SEQ=170) $onText Alphametics are a type of mathematical puzzle. Given a set of words, written down as a long-hand addition, find the mapping between letters and digits (values). For example: G E O R G I A 8 4 6 5 8 0 2 O R E G O N -> 6 5 4 8 6 3 V E R M O N T 1 4 5 9 6 3 7 ------------- --------------- V I R G I N I A 1 0 5 8 0 3 0 2 Additional information can be found at: http://www.gams.com/modlib/adddocs/alphametdoc.htm Brooke, A, Kendrick, D, and Meeraus, A, GAMS: A User's Guide. The Scientific Press, Redwood City, California, 1988. Keywords: mixed integer linear programming, alphametics $offText Set i 'letters' / g, e, o, r, i, a, n, v, m, t /; Alias (i,j); abort$(card(i) <> 10) "set i should contain 10 letters"; Set lead(i) / g, o, v / k 'slices' / 1*8 /; Parameter lhs(k,i) 'input count for each letter in slice' / 1.(a,n,t) 1 2.(i,o,n) 1 3.g 2 , 3.o 1 4.(r,e,m) 1 5.o 1 , 5.r 2 6.e 2 , 6.o 1 7.(g,v) 1 / rhs(i,k) 'result' / (v.8,i.7,r.6,g.5,i.4,n.3,i.2,a.1) 1.0 /; Variable z 'sum of carries - some objective' x(i,j) 'assignment of digits or values to letters' y(i) 'assigned value' c(k) 'carry'; Binary Variable x; Integer Variable c; Equation obj 'some objective' eq(k) 'defines addition for each slice' ydef(i) 'assigned value' x1(i) 'assignment constraint one' x2(j) 'assignment constraint two' ld(i) 'bound on lead letters'; obj.. z =e= sum(k, c(k - 1)); eq(k).. c(k-1) + sum(i, lhs(k,i)*y(i)) =e= sum(i, rhs(i,k)*y(i)) + 10*c(k)$(ord(k) <> card(k)); ydef(i).. y(i) =e= sum(j, (ord(j) - 1)*x(i,j)); x1(i).. sum(j, x(i,j)) =e= 1; x2(j).. sum(i, x(i,j)) =e= 1; ld(lead).. y(lead) =g= 1; Model m / all /; option optCr = 1, optCa = 100; solve m using mip minimizing z;