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


Reference

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

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

$offtext
sets 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;

equations 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;