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:

```

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:

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;