lemon-project-template-glpk

comparison deps/glpk/examples/queens.mod @ 10:5545663ca997

find changesets by author, revision, files, or words in the commit message
Configure GLPK build
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 21:42:23 +0100 (2011-11-06)
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:6c0b7bb69b64
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;