Debian Codegraph @

tests/spec/examples/queen_ip.mzn

raw
1 /***
2 !Test
3 expected:
4 - !Result
5 solution: !Solution
6 q:
7 - [0, 0, 0, 0, 0, 0, 0, 1]
8 - [0, 0, 0, 1, 0, 0, 0, 0]
9 - [1, 0, 0, 0, 0, 0, 0, 0]
10 - [0, 0, 1, 0, 0, 0, 0, 0]
11 - [0, 0, 0, 0, 0, 1, 0, 0]
12 - [0, 1, 0, 0, 0, 0, 0, 0]
13 - [0, 0, 0, 0, 0, 0, 1, 0]
14 - [0, 0, 0, 0, 1, 0, 0, 0]
15 - !Result
16 solution: !Solution
17 q:
18 - [0, 0, 0, 1, 0, 0, 0, 0]
19 - [0, 0, 0, 0, 0, 1, 0, 0]
20 - [0, 0, 0, 0, 0, 0, 0, 1]
21 - [0, 0, 1, 0, 0, 0, 0, 0]
22 - [1, 0, 0, 0, 0, 0, 0, 0]
23 - [0, 0, 0, 0, 0, 0, 1, 0]
24 - [0, 0, 0, 0, 1, 0, 0, 0]
25 - [0, 1, 0, 0, 0, 0, 0, 0]
26 - !Result
27 solution: !Solution
28 q:
29 - [0, 0, 0, 0, 1, 0, 0, 0]
30 - [0, 0, 0, 0, 0, 0, 0, 1]
31 - [0, 0, 0, 1, 0, 0, 0, 0]
32 - [1, 0, 0, 0, 0, 0, 0, 0]
33 - [0, 0, 0, 0, 0, 0, 1, 0]
34 - [0, 1, 0, 0, 0, 0, 0, 0]
35 - [0, 0, 0, 0, 0, 1, 0, 0]
36 - [0, 0, 1, 0, 0, 0, 0, 0]
37 ***/
38
39 % n-queens example in Zinc using IP techniques
40 % By Ralph Becket
41
42 % MiniZinc version
43 % Peter Stuckey September 30 2006
44
45 int: n = 8;
46
47 set of int: rg = 0 .. n-1;
48
49 array [rg, rg] of var 0 .. 1: q :: add_to_output;
50
51 %
52 % Every row and column has exactly one queen.
53 % Every diagonal has at most one queen.
54 %
55
56 constraint forall (i in rg) (
57 ( sum (j in rg) (q[i, j]) = 1 )
58 /\ ( sum (j in rg) (q[j, i]) = 1 )
59 /\ ( sum (j, k in rg where j - k = i) (q[j, k]) <= 1 )
60 /\ ( sum (j, k in rg where j - k = - i) (q[j, k]) <= 1 )
61 /\ ( sum (j, k in rg where j - k = i) (q[n - 1 - j, k]) <= 1 )
62 /\ ( sum (j, k in rg where j - k = - i) (q[n - 1 - j, k]) <= 1 )
63 );
64
65 %
66 % Find the first solution.
67 %
68
69 solve ::
70 int_search(
71 array1d(1..n*n, q),
72 first_fail,
73 indomain_min,
74 complete
75 )
76 satisfy;
77
78 output ["8 queens, IP version:"] ++
79 [ if j = 0 then "\n" else "" endif ++
80 if fix(q[i, j]) = 1 then "Q " else ". " endif
81 | i, j in rg
82 ] ++
83 [ "\n" ];