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


Savant, M, Ask Marilyn, 1988. Parade, May 23

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
   less(c,c)   'links having smaller neighbors'
   more(c,cc)  'links having larger neighbors'
   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;