this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Lagerkvist <lagerkvist@gecode.org>
5 *
6 * Copyright:
7 * Mikael Lagerkvist, 2006
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34
35#include <gecode/driver.hh>
36#include <gecode/int.hh>
37#include <gecode/minimodel.hh>
38#include <gecode/set.hh>
39
40using namespace Gecode;
41
42/** \name Constant sets for attacking queens.
43 *
44 * \relates QueenArmies
45 */
46IntSet* A;
47
48/**
49 * \brief %Example: Peaceable co-existing armies of queens
50 *
51 * The goal of this problem is to place as many white and black queens
52 * on a chess-board without any two queens of different color
53 * attacking each other. The number of black queens should
54 * be greater than or equal to the number of white queens.
55 *
56 * This model is based on the one presented in "Models and Symmetry
57 * Breaking for 'Peaceable Armies of Queens'", by Barbara M. Smith, Karen
58 * E. Petrie, and Ian P. Gent.
59 *
60 * The smart version uses a custom brancher implementing a heuristic
61 * from the above paper, that helps speeding up the proof of
62 * optimality.
63 *
64 * \ingroup Example
65 *
66 */
67class QueenArmies : public IntMaximizeScript {
68public:
69 const int n;
70 SetVar U, ///< Set of un-attacked squares
71 W; ///< Set of squares occupied by white queens
72 BoolVarArray w, ///< The placement of the white queens
73 b; ///< The placement of the black queens
74 IntVar q; ///< The number of white queens placed.
75
76 /// Branching to use for model
77 enum {
78 BRANCH_NAIVE, ///< Choose variables left to right
79 BRANCH_SPECIFIC ///< Choose variable with problem specific strategy
80 };
81
82 /// Constructor
83 QueenArmies(const SizeOptions& opt) :
84 IntMaximizeScript(opt),
85 n(opt.size()),
86 U(*this, IntSet::empty, IntSet(0, n*n)),
87 W(*this, IntSet::empty, IntSet(0, n*n)),
88 w(*this, n*n, 0, 1),
89 b(*this, n*n, 0, 1),
90 q(*this, 0, n*n)
91 {
92 // Basic rules of the model
93 for (int i = n*n; i--; ) {
94 // w[i] means that no blacks are allowed on A[i]
95 rel(*this, w[i] == (U || A[i]));
96 // Make sure blacks and whites are disjoint.
97 rel(*this, !w[i] || !b[i]);
98 // If i in U, then b[i] has a piece.
99 rel(*this, b[i] == (singleton(i) <= U));
100 }
101
102 // Connect optimization variable to number of pieces
103 linear(*this, w, IRT_EQ, q);
104 linear(*this, b, IRT_GQ, q);
105
106 // Connect cardinality of U to the number of black pieces.
107 IntVar unknowns = expr(*this, cardinality(U));
108 rel(*this, q <= unknowns);
109 linear(*this, b, IRT_EQ, unknowns);
110
111 if (opt.branching() == BRANCH_NAIVE) {
112 branch(*this, w, BOOL_VAR_NONE(), BOOL_VAL_MAX());
113 branch(*this, b, BOOL_VAR_NONE(), BOOL_VAL_MAX());
114 } else {
115 QueenBranch::post(*this);
116 assign(*this, b, BOOL_ASSIGN_MAX());
117 }
118 }
119 /// Constructor for cloning
120 QueenArmies(QueenArmies& s)
121 : IntMaximizeScript(s), n(s.n) {
122 U.update(*this, s.U);
123 W.update(*this, s.W);
124 w.update(*this, s.w);
125 b.update(*this, s.b);
126 q.update(*this, s.q);
127 }
128 /// Return copy during cloning
129 virtual Space*
130 copy(void) {
131 return new QueenArmies(*this);
132 }
133 /// Return solution cost
134 virtual IntVar cost(void) const {
135 return q;
136 }
137 /// Print solution
138 virtual void
139 print(std::ostream& os) const {
140 os << '\t';
141 for (int i = 0; i < n*n; ++i) {
142 if (w[i].assigned() && w[i].val()) os << "W";
143 else if (b[i].assigned() && b[i].val()) os << "B";
144 else if (!w[i].assigned() && !b[i].assigned()) os << " ";
145 else os << ".";
146 if ((i+1)%n == 0) os << std::endl << (i!=(n*n-1)?"\t":"");
147 }
148 os << "Number of white queens: " << q << std::endl << std::endl;
149 }
150
151 /** \brief Custom brancher for Peacable queens
152 *
153 * Custom brancher that tries to place white queens so that they
154 * maximise the amount of un-attacked squares that become attacked.
155 *
156 * \relates QueenArmies
157 */
158 class QueenBranch : public Brancher {
159 private:
160 /// Cache of last computed decision
161 mutable int start;
162 /// Choice
163 class Choice : public Gecode::Choice {
164 public:
165 /// Position of variable
166 int pos;
167 /// Value of variable
168 bool val;
169 /** Initialize choice for brancher \a b, position \a pos0,
170 * and value \a val0.
171 */
172 Choice(const Brancher& b, int pos0, bool val0)
173 : Gecode::Choice(b,2), pos(pos0), val(val0) {}
174 /// Archive into \a e
175 virtual void archive(Archive& e) const {
176 Gecode::Choice::archive(e);
177 e << pos << val;
178 }
179 };
180
181 /// Construct brancher
182 QueenBranch(Home home)
183 : Brancher(home), start(0) {}
184 /// Constructor for cloning
185 QueenBranch(Space& home, QueenBranch& b)
186 : Brancher(home, b), start(b.start) {}
187
188 public:
189 /// Check status of brancher, return true if alternatives left.
190 virtual bool status(const Space& home) const {
191 const QueenArmies& q = static_cast<const QueenArmies&>(home);
192 for (int i = start; i < q.n*q.n; ++i)
193 if (!q.w[i].assigned()) {
194 start = i;
195 return true;
196 }
197 // No non-assigned orders left
198 return false;
199 }
200 /// Return choice
201 virtual Gecode::Choice* choice(Space& home) {
202 const QueenArmies& q = static_cast<const QueenArmies&>(home);
203 int maxsize = -1;
204 int pos = -1;
205
206 for (int i = start; i < q.n*q.n; ++i) {
207 if (q.w[i].assigned()) continue;
208 IntSetRanges ai(A[i]);
209 SetVarUnknownRanges qU(q.U);
210 Iter::Ranges::Inter<IntSetRanges, SetVarUnknownRanges> r(ai, qU);
211 int size = Iter::Ranges::size(r);
212 if (size > maxsize) {
213 maxsize = size;
214 pos = i;
215 }
216 }
217
218 assert(pos != -1);
219 return new Choice(*this, pos, true);
220 }
221 /// Return choice
222 virtual Choice* choice(const Space&, Archive& e) {
223 int pos, val;
224 e >> pos >> val;
225 return new Choice(*this, pos, val);
226 }
227 /** \brief Perform commit for choice \a _c and
228 * alternative \a a.
229 */
230 virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
231 unsigned int a) {
232 QueenArmies& q = static_cast<QueenArmies&>(home);
233 const Choice& c = static_cast<const Choice&>(_c);
234 bool val = (a == 0) ? c.val : !c.val;
235 return me_failed(Int::BoolView(q.w[c.pos]).eq(q, val))
236 ? ES_FAILED
237 : ES_OK;
238 }
239 /// Print explanation
240 virtual void print(const Space&, const Gecode::Choice& _c,
241 unsigned int a,
242 std::ostream& o) const {
243 const Choice& c = static_cast<const Choice&>(_c);
244 bool val = (a == 0) ? c.val : !c.val;
245 o << "w[" << c.pos << "] = " << val;
246 }
247 /// Copy brancher during cloning
248 virtual Actor* copy(Space& home) {
249 return new (home) QueenBranch(home, *this);
250 }
251 /// Post brancher
252 static void post(QueenArmies& home) {
253 (void) new (home) QueenBranch(home);
254 }
255 /// Delete brancher and return its size
256 virtual size_t dispose(Space&) {
257 return sizeof(*this);
258 }
259 };
260};
261
262/** \brief Position of a piece in a square board.
263 *
264 * \relates QueenArmies
265 */
266int pos(int i, int j, int n) {
267 return i*n + j;
268}
269
270/** \brief Main-function
271 * \relates QueenArmies
272 */
273int
274main(int argc, char* argv[]) {
275 SizeOptions opt("QueenArmies");
276 opt.size(6);
277 opt.branching(QueenArmies::BRANCH_SPECIFIC);
278 opt.branching(QueenArmies::BRANCH_NAIVE, "naive");
279 opt.branching(QueenArmies::BRANCH_SPECIFIC, "specific");
280 opt.solutions(0);
281 opt.parse(argc,argv);
282
283 // Set up the A-sets
284 // A[i] will contain the values attacked by a queen at position i
285 int n = opt.size();
286 A = new IntSet[n*n];
287 int *p = new int[std::max(n*n, 25)];
288 int pn = 0;
289 for (int i = n; i--; ) {
290 for (int j = n; j--; ) {
291 int dir[][2] = {
292 { 0, 1},
293 { 1, 1},
294 { 1, 0},
295 { 0, -1},
296 {-1, -1},
297 {-1, 0},
298 { 1, -1},
299 {-1, 1}
300 };
301 p[pn++] = pos(i, j, n);
302 for (int k = 8; k--; ) {
303 for (int l = 0; l < n
304 && 0 <= (i+l*dir[k][0]) && (i+l*dir[k][0]) < n
305 && 0 <= (j+l*dir[k][1]) && (j+l*dir[k][1]) < n; ++l) {
306 p[pn++] = pos(i+l*dir[k][0], j+l*dir[k][1], n);
307 }
308 }
309
310 A[pos(i, j, n)] = IntSet(p, pn);
311
312 pn = 0;
313 }
314 }
315 delete [] p;
316
317 IntMaximizeScript::run<QueenArmies,BAB,SizeOptions>(opt);
318 return 0;
319}
320
321// STATISTICS: example-any