coex.gms : Peacefully Coexisting Armies of Queens

Description

```Two armies of queens (black and white) peacefully coexist on a
chessboard when they are placed on the board in such a way that
no two queens from opposing armies can attack each other. The
problem is to find the maximum two equal-sized armies.
```

Reference

• Bosch, R A, Peaceably Coexisting Armies of Queens. OPTIMA MPS Newsletter 62 (1999), 6-9.

Large Model of Type : MIP

Category : GAMS Model library

Main file : coex.gms

``````\$title Peacefully Coexisting Armies of Queens (COEX,SEQ=219)

\$onText
Two armies of queens (black and white) peacefully coexist on a
chessboard when they are placed on the board in such a way that
no two queens from opposing armies can attack each other. The
problem is to find the maximum two equal-sized armies.

Bosch, R, Mind Sharpener. OPTIMA MPS Newsletter (2000).

Keywords: mixed integer linear programming, mathematical games, combinatorial optimization,
peaceably coexisting armies of queens
\$offText

Set i 'size of chess board' / 1*8 /;

Alias (i,j,ii,jj);

Set M(i,j,ii,jj) 'shared positions on the board';

M(i,j,ii,jj) = (ord(i) = ord(ii)) or
(ord(j) = ord(jj)) or
(abs(ord(i) - ord(ii)) = abs(ord(j) - ord(jj)));

Binary Variable
b(i,j) 'square occupied by a black queen'
w(i,j) 'square occupied by a white queen';

Variable tot 'total queens in each army';

Equation
eq1(i,j,ii,jj) 'keeps armies at peace'
eq2            'add up all the black queens'
eq3            'add up all the white queens';

eq1(m(i,j,ii,jj)).. b(i,j) + w(ii,jj) =l= 1;

eq2.. tot =e= sum((i,j), b(i,j));

eq3.. tot =e= sum((i,j), w(i,j));

Model armies / all /;

option limCol = 0, limRow = 0;

\$onText
* solution reported in OPTIMA
b.fx('6','2') = 1;
b.fx('7','2') = 1;
b.fx('8','2') = 1;
b.fx('7','1') = 1;
b.fx('8','1') = 1;
b.fx('7','6') = 1;
b.fx('8','6') = 1;
b.fx('7','7') = 1;
b.fx('8','7') = 1;
\$offText

solve armies maximizing tot using mip;
``````