alphamet.gms : Alphametics - a Mathematical Puzzle

**Description**

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

**References**

- Kalvelagen, E, Model Building with GAMS. forthcoming
- de Wetering, A V, private communication.

**Large Model of Type :** MIP

**Category :** GAMS Model library

**Main file :** alphamet.gms

```
$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;
```