Generated on Fri Aug 31 2012 16:20:38 for Gecode by doxygen 1.8.1.2
queen-armies.cpp
Go to the documentation of this file.
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  * Last modified:
10  * $Date: 2011-05-11 20:44:17 +1000 (Wed, 11 May 2011) $ by $Author: tack $
11  * $Revision: 12001 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 
39 #include <gecode/driver.hh>
40 #include <gecode/int.hh>
41 #include <gecode/minimodel.hh>
42 #include <gecode/set.hh>
43 
44 using namespace Gecode;
45 
51 
71 class QueenArmies : public MaximizeScript {
72 public:
73  const int n;
74  SetVar U,
75  W;
77  b;
79 
81  enum {
83  BRANCH_SPECIFIC
84  };
85 
87  enum {
89  SEARCH_RESTART
90  };
91 
94  n(opt.size()),
95  U(*this, IntSet::empty, IntSet(0, n*n)),
96  W(*this, IntSet::empty, IntSet(0, n*n)),
97  w(*this, n*n, 0, 1),
98  b(*this, n*n, 0, 1),
99  q(*this, 0, n*n)
100  {
101  // Basic rules of the model
102  for (int i = n*n; i--; ) {
103  // w[i] means that no blacks are allowed on A[i]
104  rel(*this, w[i] == (U || A[i]));
105  // Make sure blacks and whites are disjoint.
106  rel(*this, !w[i] || !b[i]);
107  // If i in U, then b[i] has a piece.
108  rel(*this, b[i] == (singleton(i) <= U));
109  }
110 
111  // Connect optimization variable to number of pieces
112  linear(*this, w, IRT_EQ, q);
113  linear(*this, b, IRT_GQ, q);
114 
115  // Connect cardinality of U to the number of black pieces.
116  IntVar unknowns = expr(*this, cardinality(U));
117  rel(*this, q <= unknowns);
118  linear(*this, b, IRT_EQ, unknowns);
119 
120  if (opt.branching() == BRANCH_NAIVE) {
121  branch(*this, w, INT_VAR_NONE, INT_VAL_MAX);
122  branch(*this, b, INT_VAR_NONE, INT_VAL_MAX);
123  } else {
124  QueenBranch::post(*this);
125  assign(*this, b, INT_ASSIGN_MAX);
126  }
127  }
129  QueenArmies(bool share, QueenArmies& s)
130  : MaximizeScript(share,s), n(s.n) {
131  U.update(*this, share, s.U);
132  W.update(*this, share, s.W);
133  w.update(*this, share, s.w);
134  b.update(*this, share, s.b);
135  q.update(*this, share, s.q);
136  }
138  virtual Space*
139  copy(bool share) {
140  return new QueenArmies(share,*this);
141  }
143  virtual IntVar cost(void) const {
144  return q;
145  }
147  virtual void
148  print(std::ostream& os) const {
149  os << '\t';
150  for (int i = 0; i < n*n; ++i) {
151  if (w[i].assigned() && w[i].val()) os << "W";
152  else if (b[i].assigned() && b[i].val()) os << "B";
153  else if (!w[i].assigned() && !b[i].assigned()) os << " ";
154  else os << ".";
155  if ((i+1)%n == 0) os << std::endl << (i!=(n*n-1)?"\t":"");
156  }
157  os << "Number of white queens: " << q << std::endl << std::endl;
158  }
159 
167  class QueenBranch : public Brancher {
168  private:
170  mutable int start;
172  class Choice : public Gecode::Choice {
173  public:
175  int pos;
177  bool val;
181  Choice(const Brancher& b, int pos0, bool val0)
182  : Gecode::Choice(b,2), pos(pos0), val(val0) {}
184  virtual size_t size(void) const {
185  return sizeof(Choice);
186  }
188  virtual void archive(Archive& e) const {
190  e << pos << val;
191  }
192  };
193 
195  QueenBranch(Home home)
196  : Brancher(home), start(0) {}
198  QueenBranch(Space& home, bool share, QueenBranch& b)
199  : Brancher(home, share, b), start(b.start) {}
200 
201  public:
203  virtual bool status(const Space& home) const {
204  const QueenArmies& q = static_cast<const QueenArmies&>(home);
205  for (int i = start; i < q.n*q.n; ++i)
206  if (!q.w[i].assigned()) {
207  start = i;
208  return true;
209  }
210  // No non-assigned orders left
211  return false;
212  }
214  virtual Gecode::Choice* choice(Space& home) {
215  const QueenArmies& q = static_cast<const QueenArmies&>(home);
216  int maxsize = -1;
217  int pos = -1;
218 
219  for (int i = start; i < q.n*q.n; ++i) {
220  if (q.w[i].assigned()) continue;
221  IntSetRanges ai(A[i]);
222  SetVarUnknownRanges qU(q.U);
224  int size = Iter::Ranges::size(r);
225  if (size > maxsize) {
226  maxsize = size;
227  pos = i;
228  }
229  }
230 
231  assert(pos != -1);
232  return new Choice(*this, pos, true);
233  }
235  virtual Choice* choice(const Space&, Archive& e) {
236  int pos, val;
237  e >> pos >> val;
238  return new Choice(*this, pos, val);
239  }
243  virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
244  unsigned int a) {
245  QueenArmies& q = static_cast<QueenArmies&>(home);
246  const Choice& c = static_cast<const Choice&>(_c);
247  bool val = (a == 0) ? c.val : !c.val;
248  return me_failed(Int::BoolView(q.w[c.pos]).eq(q, val))
249  ? ES_FAILED
250  : ES_OK;
251  }
253  virtual Actor* copy(Space& home, bool share) {
254  return new (home) QueenBranch(home, share, *this);
255  }
257  static void post(QueenArmies& home) {
258  (void) new (home) QueenBranch(home);
259  }
261  virtual size_t dispose(Space&) {
262  return sizeof(*this);
263  }
264  };
265 };
266 
271 int pos(int i, int j, int n) {
272  return i*n + j;
273 }
274 
278 int
279 main(int argc, char* argv[]) {
280  SizeOptions opt("QueenArmies");
281  opt.size(6);
283  opt.branching(QueenArmies::BRANCH_NAIVE, "naive");
284  opt.branching(QueenArmies::BRANCH_SPECIFIC, "specific");
286  opt.search(QueenArmies::SEARCH_BAB, "bab");
287  opt.search(QueenArmies::SEARCH_RESTART, "restart");
288  opt.solutions(0);
289  opt.parse(argc,argv);
290 
291  // Set up the A-sets
292  // A[i] will contain the values attacked by a queen at position i
293  int n = opt.size();
294  A = new IntSet[n*n];
295  int *p = new int[std::max(n*n, 25)];
296  int pn = 0;
297  for (int i = n; i--; ) {
298  for (int j = n; j--; ) {
299  int dir[][2] = {
300  { 0, 1},
301  { 1, 1},
302  { 1, 0},
303  { 0, -1},
304  {-1, -1},
305  {-1, 0},
306  { 1, -1},
307  {-1, 1}
308  };
309  p[pn++] = pos(i, j, n);
310  for (int k = 8; k--; ) {
311  for (int l = 0; l < n
312  && 0 <= (i+l*dir[k][0]) && (i+l*dir[k][0]) < n
313  && 0 <= (j+l*dir[k][1]) && (j+l*dir[k][1]) < n; ++l) {
314  p[pn++] = pos(i+l*dir[k][0], j+l*dir[k][1], n);
315  }
316  }
317 
318  A[pos(i, j, n)] = IntSet(p, pn);
319 
320  pn = 0;
321  }
322  }
323  delete [] p;
324 
325 
326  switch (opt.search()) {
328  MaximizeScript::run<QueenArmies,BAB,SizeOptions>(opt); break;
330  MaximizeScript::run<QueenArmies,Restart,SizeOptions>(opt); break;
331  }
332  return 0;
333 }
334 
335 // STATISTICS: example-any