1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/examples/queens.mod	Mon Dec 06 13:09:21 2010 +0100
     1.3 @@ -0,0 +1,41 @@
     1.4 +/* QUEENS, a classic combinatorial optimization problem */
     1.5 +
     1.6 +/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
     1.7 +
     1.8 +/* The Queens Problem is to place as many queens as possible on the 8x8
     1.9 +   (or more generally, nxn) chess board in a way that they do not fight
    1.10 +   each other. This problem is probably as old as the chess game itself,
    1.11 +   and thus its origin is not known, but it is known that Gauss studied
    1.12 +   this problem. */
    1.13 +
    1.14 +param n, integer, > 0, default 8;
    1.15 +/* size of the chess board */
    1.16 +
    1.17 +var x{1..n, 1..n}, binary;
    1.18 +/* x[i,j] = 1 means that a queen is placed in square [i,j] */
    1.19 +
    1.20 +s.t. a{i in 1..n}: sum{j in 1..n} x[i,j] <= 1;
    1.21 +/* at most one queen can be placed in each row */
    1.22 +
    1.23 +s.t. b{j in 1..n}: sum{i in 1..n} x[i,j] <= 1;
    1.24 +/* at most one queen can be placed in each column */
    1.25 +
    1.26 +s.t. c{k in 2-n..n-2}: sum{i in 1..n, j in 1..n: i-j == k} x[i,j] <= 1;
    1.27 +/* at most one queen can be placed in each "\"-diagonal */
    1.28 +
    1.29 +s.t. d{k in 3..n+n-1}: sum{i in 1..n, j in 1..n: i+j == k} x[i,j] <= 1;
    1.30 +/* at most one queen can be placed in each "/"-diagonal */
    1.31 +
    1.32 +maximize obj: sum{i in 1..n, j in 1..n} x[i,j];
    1.33 +/* objective is to place as many queens as possible */
    1.34 +
    1.35 +/* solve the problem */
    1.36 +solve;
    1.37 +
    1.38 +/* and print its optimal solution */
    1.39 +for {i in 1..n}
    1.40 +{  for {j in 1..n} printf " %s", if x[i,j] then "Q" else ".";
    1.41 +   printf("\n");
    1.42 +}
    1.43 +
    1.44 +end;