Debian Codegraph @

tests/spec/examples/battleships.mzn.model

raw
1 % battleships.mzn.model
2 % Ralph Becket <[email protected]>
3 % Wed Dec 10 13:51:12 EST 2008
4 % vim: ft=zinc ts=4 sw=4 et tw=0
5 %
6 % A battleships puzzle involves working out where each of a fleet of ships
7 % lies on a square grid. Clues are given in two ways: some parts of the
8 % grid may be revealed as containing open water or part of a ship; and the
9 % total number of parts of ships appearing in a row or column may also be
10 % specified. Individual ships are always surrounded by open water, even
11 % at the corners.
12 %
13 % The following example is taken from
14 % http://wpc.puzzles.com/history/tests/1999qtest/test.htm
15 %
16 % w _ _ _ _ w _ _ _ 2 Fleet:
17 % S w _ _ _ _ _ _ _ 2 1 battleship SSSS
18 % _ _ _ _ _ _ _ _ _ 3 2 cruisers SSS SSS
19 % w _ _ _ _ _ _ w _ 2 3 destroyers SS SS SS
20 % _ _ _ _ _ _ _ _ _ 2 4 submarines S S S S
21 % _ w S w _ _ _ _ _ 1
22 % _ _ w _ _ _ _ S _ 5
23 % _ _ _ _ _ _ _ _ _ 1
24 % _ _ _ _ _ _ _ _ _ 2
25 %
26 % 4 0 3 2 2 2 1 4 2
27 %
28 % In this model, each square on the grid is a number from 0..4
29 % (0 being water, 4 denoting the bows of a battleship). A Cruiser,
30 % for instance, is described by a contiguous pattern 0 1 2 3 0 on
31 % the board. Consider the following neighbourhood:
32 %
33 % a b c
34 % d x e
35 % f g h
36 %
37 % Precisely one of the following must hold:
38 % - x is 0
39 % - x is b + 1 and d = e = 0
40 % - x is d + 1 and b = g = 0
41 %
42 % We also need to specify constraints on diagonally adjacent squares:
43 % - if x < b then d = e = 0
44 % - if x < d then b = g = 0
45 %
46 % The column (row) constraints specify how many non-zero elements a
47 % column (row) must have.
48 %
49 % The fleet constraints specify how many instances of each positive number
50 % must appear on the board.
51
52 include "count.mzn";
53
54 % Parameter: the length of side of the grid.
55 %
56 int: n;
57
58 % Parameter: the number of ships of each class.
59 %
60 int: n_classes;
61 set of int: class = 1..n_classes;
62 array [class] of int: class_sizes;
63
64 set of int: sq = {0} union class;
65
66 % The row and column sums.
67 %
68 array [1..n] of var 0..n: row_sums;
69 array [1..n] of var 0..n: col_sums;
70
71 % We extend the board by one in each direction to add a sea border.
72 %
73 set of int: row = 2..(n + 1);
74 set of int: col = 2..(n + 1);
75 set of int: ROW = 1..(n + 2);
76 set of int: COL = 1..(n + 2);
77 array [ROW, COL] of var sq: a;
78
79 % Add the sea border to the board.
80 %
81 constraint forall (r in {1, n + 2}, c in COL) (a[r, c] = 0);
82 constraint forall (r in ROW, c in {1, n + 2}) (a[r, c] = 0);
83
84 % Add the ship constraints.
85 %
86 constraint
87 forall (r in row, c in col) (
88 (
89 a[r, c] = 0
90 )
91 \/
92 (
93 a[r, c] = a[r, c - 1] + 1
94 /\ a[r - 1, c] = 0
95 /\ a[r + 1, c] = 0
96 )
97 \/
98 (
99 a[r, c] = a[r - 1, c] + 1
100 /\ a[r, c - 1] = 0
101 /\ a[r, c + 1] = 0
102 )
103 );
104
105 % Add the diagonal constraints.
106 %
107 constraint
108 forall (r in row, c in col) (
109 (
110 a[r, c] < a[r, c - 1]
111 )
112 ->
113 (
114 a[r - 1, c] = 0
115 /\ a[r + 1, c] = 0
116 )
117 );
118
119 constraint
120 forall (r in row, c in col) (
121 (
122 a[r, c] < a[r - 1, c]
123 )
124 ->
125 (
126 a[r, c - 1] = 0
127 /\ a[r, c + 1] = 0
128 )
129 );
130
131 % Add the row and column constraints.
132 %
133 constraint
134 forall (r in row) (count([a[r, c] | c in col], 0, n - row_sums[r - 1]));
135
136 constraint
137 forall (c in col) (count([a[r, c] | r in row], 0, n - col_sums[c - 1]));
138
139 % Add the fleet constraints (a_flat is the 1D flattenning of the board, a).
140 %
141 array [1..(n * n)] of var sq: a_flat = [a[r, c] | r in row, c in col];
142
143 constraint
144 forall (s in class) (
145 count(a_flat, s, sum (i in class where i >= s) (class_sizes[i]))
146 );
147
148 solve
149 :: int_search(a_flat, first_fail, indomain_max, complete)
150 satisfy;
151
152 output [ show(a[r, c]) ++ if c = n then "\n" else " " endif
153 | r in row, c in col
154 ];
155