You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
41 lines
1.3 KiB
41 lines
1.3 KiB
/* QUEENS, a classic combinatorial optimization problem */
|
|
|
|
/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
|
|
|
|
/* The Queens Problem is to place as many queens as possible on the 8x8
|
|
(or more generally, nxn) chess board in a way that they do not fight
|
|
each other. This problem is probably as old as the chess game itself,
|
|
and thus its origin is not known, but it is known that Gauss studied
|
|
this problem. */
|
|
|
|
param n, integer, > 0, default 8;
|
|
/* size of the chess board */
|
|
|
|
var x{1..n, 1..n}, binary;
|
|
/* x[i,j] = 1 means that a queen is placed in square [i,j] */
|
|
|
|
s.t. a{i in 1..n}: sum{j in 1..n} x[i,j] <= 1;
|
|
/* at most one queen can be placed in each row */
|
|
|
|
s.t. b{j in 1..n}: sum{i in 1..n} x[i,j] <= 1;
|
|
/* at most one queen can be placed in each column */
|
|
|
|
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;
|
|
/* at most one queen can be placed in each "\"-diagonal */
|
|
|
|
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;
|
|
/* at most one queen can be placed in each "/"-diagonal */
|
|
|
|
maximize obj: sum{i in 1..n, j in 1..n} x[i,j];
|
|
/* objective is to place as many queens as possible */
|
|
|
|
/* solve the problem */
|
|
solve;
|
|
|
|
/* and print its optimal solution */
|
|
for {i in 1..n}
|
|
{ for {j in 1..n} printf " %s", if x[i,j] then "Q" else ".";
|
|
printf("\n");
|
|
}
|
|
|
|
end;
|