Description

This model finds all possible ways to arrange eight queens on a chess
board in such a way that no two queens check against any other queen.
The solution proceeds in two steps. In the first step, we find any
solution. In the second step we find all solutions by adding cuts to
to the original problem set. Finally, a reporting step is added
to print all solutions found. This problem has a long history. In 1850
it was investigated by C.F. Gauss, but he was unable to solve it
completely. There are 92 possible solutions.

Large Model of Types : MIP gams

Category : GAMS Model library

Main file : queens.gms

$title Maximum Queens Chess Problem (QUEENS,SEQ=103)

$onText
This model finds all possible ways to arrange eight queens on a chess
board in such a way that no two queens check against any other queen.
The solution proceeds in two steps. In the first step, we find any
solution. In the second step we find all solutions by adding cuts to
to the original problem set. Finally, a reporting step is added
to print all solutions found. This problem has a long history. In 1850
it was investigated by C.F. Gauss, but he was unable to solve it
completely. There are 92 possible solutions.


Dudeney, H E, Amusements in Mathematics. Dover, New York, 1970.

Beauvais, J, Solving the Maximum Queens Chess Problem with OSL. IBM
Kingston, EKKNEWS 2 (1991).

Keywords: mixed integer linear programming, maximum queens chess problem, n-queens
          problem, mathematical games, combinatorial optimization, constraint
          satisfaction problem
$offText

$eolCom //
$if not set iMax $set iMax 8
$eval s 2*%iMax%-3

Set
   i 'size of chess board' / 1*%iMax% /
   s 'diagonal offsets'    / 1*%s%    /;

Alias (i,j);

Parameter
   sh(s)  'shift values for diagonals'
   rev(i) 'reverse order';

sh(s)  = ord(s)  - card(i) + 1;
rev(i) = card(i) + 1 - 2*ord(i);
display sh, rev;

Binary Variable x(i,j) 'square occupied by queen';

Variable tot 'total squares occupied by queens';

Equation
   a(i) 'no to queens may be in the same rank'
   b(j) 'no to queens may be in the same file'
   c(s) 'no to queens may be in the same diagonal (forward)'
   d(s) 'no to queens may be in the same diagonal (backward)'
   obj  'objective definition';

a(i).. sum(j, x(i,j))                =e= 1;

b(j).. sum(i, x(i,j))                =e= 1;

c(s).. sum(i, x(i,i+sh(s)))          =l= 1;

d(s).. sum(i, x(i,i+(rev(i)+sh(s)))) =l= 1;

obj..  tot =e= sum((i,j), x(i,j));

Model queen1 'first model for queens' / all /;

option optCr = 0;

solve queen1 maximizing tot using mip;

$sTitle Find all remaining Solutions
Set
   nn    'max number of solutions groups' / 1*20 /
   n(nn) 'dynamic set for solution groups'
   t     'multiple solutions via rotations and reflections'
         / found   'original solution'
           rot-90  'original solution rotated  90 degrees'
           rot-180 'original solution rotated 180 degrees'
           rot-270 'original solution rotated 270 degrees'
           ref-h   'original solution reflected horizontally'
           ref-v   'original solution reflected vertically'
           ref-r   'original solution reflected diagonally main'
           ref-l   'original solution reflected diagonally back' /;

Scalar saverow, coloff;

Parameter cutval    'all possible solutions for cut generation';

Equation  cut(nn,t) 'known solutions to be eliminated';

cut(n,t).. sum((i,j), cutval(n,t,i,j)*x(i,j)) =l= card(i) - 1;

Model queens 'queens model with cuts' / all /;

option limRow = 0, limCol = 0, solPrint = off;

n(nn) = no;  // clear set of cuts;

queens.solveStat = %solveStat.normalCompletion%;
queens.modelStat = %modelStat.optimal%;

loop(nn$(queens.solveStat = %solveStat.normalCompletion% and
         queens.modelStat = %modelStat.optimal%),
   n(nn) = yes;   // add element to set;
   cutval(nn,'found'   ,i,j) = x.l(i       ,j       );
   cutval(nn,'rot-90'  ,i,j) = x.l(j+rev(j),i       );
   cutval(nn,'rot-180' ,i,j) = x.l(i+rev(i),j+rev(j));
   cutval(nn,'rot-270' ,i,j) = x.l(j       ,i+rev(i));
   cutval(nn,'ref-h'   ,i,j) = x.l(i+rev(i),j       );
   cutval(nn,'ref-v'   ,i,j) = x.l(i       ,j+rev(j));
   cutval(nn,'ref-r'   ,i,j) = x.l(j       ,i       );
   cutval(nn,'ref-l'   ,i,j) = x.l(j+rev(j),i+rev(i));
   solve queens maximizing tot using mip;
);

option  cutval:0:3:1;
display cutval;

$sTitle Write Solution Report to PUT File
File queen 'report file for solution groups';
put  queen;
queen.pc = 3;

Scalar
   saverow 'row position to start second report column'
   coloff  'column offset for board displays';

puttl 'Queens Solution Summary        ' system.date ' ' system.time
loop(n(nn),
   putPage;
   put @12 / / 'Solution Number ' ord(nn):3:0 ' of ' card(n):<3:0;
   saverow = File.cr;
   coloff  = 1;
   loop(t,
      if(ord(t) = 5,
         File.cr = saverow;
         coloff  = 31
      );
      put / / @coloff 'Type = ' t.tl / / @(coloff+2);
      loop(j, put j.tl:>2);
      loop(i,
         put / @coloff i.tl:>2;
         loop(j,
            if(cutval(n,t,i,j), put ' x';
            else put '  ';);
         );
      );
   );
);