marilyn.gms : Numerical Puzzle

Description

```Place the digits 1 trough 8 in eight circles connected shown below, but
with one restriction: Any two circles next to each other must have digits
assigned that are not serial.

1
/| \
2-3-4
|X|X|
5-6-7
\|/
8
```

Large Model of Type : MIP

Category : GAMS Model library

Main file : marilyn.gms

``````\$title Numerical Puzzle (MARILYN,SEQ=193)

\$onText
Place the digits 1 trough 8 in eight circles connected shown below, but
with one restriction: Any two circles next to each other must have digits
assigned that are not serial.

1
/| \
2-3-4
|X|X|
5-6-7
\|/
8

Keywords: mixed integer linear programming, eight-digit puzzle
\$offText

Set
c 'circles' / c1*c8            /
net(c,c)    / c1.(c2,c3,c4)
c2.(c3,c5,c6)
c3.(c4,c5,c6,c7)
c4.(c6,c7)
c5.(c6,c8)
c6.(c7,c8)
c7.c8            /;

Alias (c,cc);

net(c,cc) = net(c,cc) + net(cc,c);

Integer Variable x(c) 'digits to be placed in circles';

Binary Variable
ll(c,cc) 'less or greater indicator'
y(c,cc)  'digit assignment';

Variable dummy;

Equation
cross(c,cc) 'links are one way or the other'
digit(c)    'assignment of digits to circles'
rowsum(c)   'assignment condition 1'
colsum(c)   'assignment condition 2'
obj;

x.lo(c) = 1;
x.up(c) = 8;

* distance to neighbor at least 2
* neighbor(net(c,cc))..  abs(x(cc) - x(c)) =g= 2;
less(net(c,cc))..  x(cc) =l= x(c) - 2 + 9*ll(c,cc);

more(net(c,cc))..  x(cc) =g= x(c) + 2 - 9*ll(cc,c);

cross(net(c,cc)).. ll(c,cc) + ll(cc,c) =e= 1;

* assign  the values of 1,2,..8 to x
* digit(c).. sum(cc, x(cc) = ord(c)) =e= 1;
digit(c)..  x(c) =e= sum(cc, ord(cc)*y(c,cc));

rowsum(c).. sum(cc, y(c,cc)) =e= 1;

colsum(c).. sum(cc, y(cc,c)) =e= 1;

obj..       dummy =e= sum(c, x(c));

* obj below is very slow on some systems
* obj.. dummy =e= sum(c, ord(c)*x(c));
Model m / all /;

* use bbpreproc for osl
solve m us mip min dummy;
``````
GAMS Development Corp.
GAMS Software GmbH

General Information and Sales
U.S. (+1) 202 342-0180
Europe: (+49) 221 949-9170