COIN-OR::LEMON - Graph Library

source: glpk-cmake/examples/queens.mod @ 1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 1.3 KB
Line 
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
11param n, integer, > 0, default 8;
12/* size of the chess board */
13
14var x{1..n, 1..n}, binary;
15/* x[i,j] = 1 means that a queen is placed in square [i,j] */
16
17s.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
20s.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
23s.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
26s.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
29maximize 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 */
33solve;
34
35/* and print its optimal solution */
36for {i in 1..n}
37{  for {j in 1..n} printf " %s", if x[i,j] then "Q" else ".";
38   printf("\n");
39}
40
41end;
Note: See TracBrowser for help on using the repository browser.