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; |
---|