|
1 /* QUEENS, a classic combinatorial optimization problem */ |
|
2 |
|
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ |
|
4 |
|
5 /* The Queens Problem is to place as many queens as possible on the 8x8 |
|
6 (or more generally, nxn) chess board in a way that they do not fight |
|
7 each other. This problem is probably as old as the chess game itself, |
|
8 and thus its origin is not known, but it is known that Gauss studied |
|
9 this problem. */ |
|
10 |
|
11 param n, integer, > 0, default 8; |
|
12 /* size of the chess board */ |
|
13 |
|
14 var x{1..n, 1..n}, binary; |
|
15 /* x[i,j] = 1 means that a queen is placed in square [i,j] */ |
|
16 |
|
17 s.t. a{i in 1..n}: sum{j in 1..n} x[i,j] <= 1; |
|
18 /* at most one queen can be placed in each row */ |
|
19 |
|
20 s.t. b{j in 1..n}: sum{i in 1..n} x[i,j] <= 1; |
|
21 /* at most one queen can be placed in each column */ |
|
22 |
|
23 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; |
|
24 /* at most one queen can be placed in each "\"-diagonal */ |
|
25 |
|
26 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; |
|
27 /* at most one queen can be placed in each "/"-diagonal */ |
|
28 |
|
29 maximize obj: sum{i in 1..n, j in 1..n} x[i,j]; |
|
30 /* objective is to place as many queens as possible */ |
|
31 |
|
32 /* solve the problem */ |
|
33 solve; |
|
34 |
|
35 /* and print its optimal solution */ |
|
36 for {i in 1..n} |
|
37 { for {j in 1..n} printf " %s", if x[i,j] then "Q" else "."; |
|
38 printf("\n"); |
|
39 } |
|
40 |
|
41 end; |