Generated on Sat Aug 25 2012 03:32:42 for Gecode by doxygen 1.8.1.2
black-hole.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 #include <gecode/driver.hh>
39 #include <gecode/int.hh>
40 
41 #include <vector>
42 #include <algorithm>
43 #include <sstream>
44 
45 using namespace Gecode;
46 
47 namespace {
48  using std::vector;
49 
51  vector<vector<int> > layout;
53  vector<int> layer, pile;
54 
61  void generate(int seed) {
62  // The layout consists of 17 piles of 3 cards each
63  layout = vector<vector<int> >(17, vector<int>(3));
64  // Deck without the Ace of Spades
65  vector<int> deck(51);
66  for (int i = 51; i--; ) deck[i] = i+1;
67  Support::RandomGenerator rnd(seed+1);
68  std::random_shuffle(deck.begin(), deck.end(), rnd);
69 
70  // Place cards from deck
71  int pos = 0;
72  for (int i = 17; i--; )
73  for (int j = 3; j--; )
74  layout[i][j] = deck[pos++];
75 
76  // Location-information for each card
77  layer = vector<int>(52);
78  pile = vector<int>(52);
79  for (int i = 17; i--; ) {
80  for (int j = 3; j--; ) {
81  layer[layout[i][j]] = j;
82  pile[ layout[i][j]] = i;
83  }
84  }
85  }
86 }
87 
88 
89 
99 protected:
103  mutable int start;
105  class Choice : public Gecode::Choice {
106  public:
108  int pos;
110  int val;
114  Choice(const Brancher& b, int pos0, int val0)
115  : Gecode::Choice(b,2), pos(pos0), val(val0) {}
117  virtual size_t size(void) const {
118  return sizeof(Choice);
119  }
121  virtual void archive(Archive& e) const {
123  e << pos << val;
124  }
125  };
126 
129  : Brancher(home), x(xv), start(0) {}
131  BlackHoleBranch(Space& home, bool share, BlackHoleBranch& b)
132  : Brancher(home, share, b), start(b.start) {
133  x.update(home, share, b.x);
134  }
135 
136 public:
138  virtual bool status(const Space&) const {
139  for (int i = start; i < x.size(); ++i)
140  if (!x[i].assigned()) {
141  start = i;
142  return true;
143  }
144  // No non-assigned orders left
145  return false;
146  }
148  virtual Choice* choice(Space&) {
149  int val = -1;
150  int w = 4;
151  for (Int::ViewValues<Int::IntView> vals(x[start]); vals(); ++vals)
152  if (layer[vals.val()] < w) {
153  val = vals.val();
154  if ((w = layer[vals.val()]) == 0) break;
155  }
156 
157  assert(val >= 1 && val < 52);
158  return new Choice(*this, start, val);
159  }
161  virtual Choice* choice(const Space&, Archive& e) {
162  int pos, val;
163  e >> pos >> val;
164  return new Choice(*this, pos, val);
165  }
167  virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
168  unsigned int a) {
169  const Choice& c = static_cast<const Choice&>(_c);
170  if (a)
171  return me_failed(x[c.pos].nq(home, c.val)) ? ES_FAILED : ES_OK;
172  else
173  return me_failed(x[c.pos].eq(home, c.val)) ? ES_FAILED : ES_OK;
174  }
176  virtual Actor* copy(Space& home, bool share) {
177  return new (home) BlackHoleBranch(home, share, *this);
178  }
180  static void post(Home home, IntVarArgs x) {
181  ViewArray<Int::IntView> xv(home, x);
182  (void) new (home) BlackHoleBranch(home, xv);
183  }
185  virtual size_t dispose(Space&) {
186  return sizeof(*this);
187  }
188 };
189 
190 
207 class BlackHole : public Script {
208 protected:
210  y;
211 
213  std::string
214  card(int val) const {
215  const char* suit = "SCHD";
216  std::ostringstream o;
217  o << std::setw(2) << (1 + (val%13)) << suit[val/13];
218  return o.str();
219  }
220 
221 public:
223  enum {
225  SYMMETRY_CONDITIONAL
226  };
228  enum {
231  PROPAGATION_TUPLE_SET
232  };
235  : x(*this, 52, 0,51), y(*this, 52, 0,51)
236  {
237  // Black ace at bottom
238  rel(*this, x[0], IRT_EQ, 0);
239 
240  // x is order and y is placement
241  channel(*this, x, y, opt.icl());
242 
243  // The placement rules: the absolute value of the difference
244  // between two consecutive cards is 1 or 12.
245  if (opt.propagation() == PROPAGATION_REIFIED) {
246  // Build table for accessing the rank of a card
247  IntArgs modtable(52);
248  for (int i = 0; i < 52; ++i) {
249  modtable[i] = i%13;
250  }
251  for (int i = 0; i < 51; ++i) {
252  IntVar x1(*this, 0, 12), x2(*this, 0, 12);
253  element(*this, modtable, x[i], x1);
254  element(*this, modtable, x[i+1], x2);
255  const int dr[2] = {1, 12};
256  IntVar diff(*this, IntSet(dr, 2));
257  rel(*this, abs(x1-x2) == diff, ICL_DOM);
258  }
259  } else if (opt.propagation() == PROPAGATION_DFA) {
260  // Build table for allowed tuples
261  REG expression;
262  for (int r = 13; r--; ) {
263  for (int s1 = 4; s1--; ) {
264  for (int s2 = 4; s2--; ) {
265  for (int i = -1; i <= 1; i+=2) {
266  REG r1 = REG(r+13*s1);
267  REG r2 = REG((r+i+52+13*s2)%52);
268  REG r = r1 + r2;
269  expression |= r;
270  }
271  }
272  }
273  }
274  DFA table(expression);
275 
276  for (int i = 51; i--; )
277  extensional(*this, IntVarArgs() << x[i] << x[i+1], table);
278 
279  } else { // opt.propagation() == PROPAGATION_TUPLE_SET)
280  // Build table for allowed tuples
281  TupleSet tupleSet;
282  for (int r = 13; r--; )
283  for (int s1 = 4; s1--; )
284  for (int s2 = 4; s2--; )
285  for (int i = -1; i <= 1; i+=2) {
286  tupleSet.add(IntArgs(2, r+13*s1, (r+i+52+13*s2)%52));
287  }
288  tupleSet.finalize();
289 
290  for (int i = 51; i--; )
291  extensional(*this, IntVarArgs() << x[i] << x[i+1], tupleSet);
292  }
293 
294  // A card must be played before the one under it.
295  for (int i = 17; i--; )
296  for (int j = 2; j--; )
297  rel(*this, y[layout[i][j]] < y[layout[i][j+1]]);
298 
299  // Compute and break the conditional symmetries that are dependent
300  // on the current layout.
301  // Two cards with the same rank but different suits are symmetric
302  // with respect to their placement in the black hole if changing
303  // their order does not affect any other card.
304  if (opt.symmetry() == SYMMETRY_CONDITIONAL) {
305  // For all ranks
306  for (int r = 13; r--; ) {
307  // For all pairs of suits
308  for (int s1 = 4; s1--; ) {
309  for (int s2 = s1; s2--; ) {
310  int c1 = 13*s1 + r,
311  c2 = 13*s2 + r;
312  // The ace of spades is already placed
313  if (c1 == 0 || c2 == 0) continue;
314  // Piles are handled by the rules of the game
315  if (pile[c1] == pile[c2]) continue;
316  // Fix the right order of the cards
317  int o1 = c1, o2 = c2;
318  if (pile[c1] > pile[c2] && layer[c2] >= layer[c1])
319  std::swap(o1, o2);
320  // cond is the condition for the symmetry
321  BoolVarArgs ba;
322  // Both cards played after the ones on top of them
323  for (int i = 0; i < layer[o1]; ++i)
324  ba << expr(*this, (y[layout[pile[o1]][i]] < y[o2]));
325  for (int i = 0; i < layer[o2]; ++i)
326  ba << expr(*this, (y[layout[pile[o2]][i]] < y[o1]));
327  // Both cards played before the ones under them
328  for (int i = layer[o1]+1; i < 3; ++i)
329  ba << expr(*this, (y[o2] < y[layout[pile[o1]][i]]));
330  for (int i = layer[o2]+1; i < 3; ++i)
331  ba << expr(*this, (y[o1] < y[layout[pile[o2]][i]]));
332  // Cond holds when all the above holds
333  BoolVar cond(*this, 0, 1);
334  rel(*this, BOT_AND, ba, cond);
335 
336  // If cond is fulfilled, then we can order the cards
337  // cond -> (y[o1] < y[o2])
338  rel(*this, !cond || (y[o1] < y[o2]));
339  }
340  }
341  }
342  }
343 
344  // Install custom brancher
345  BlackHoleBranch::post(*this, x);
346  }
347 
349  virtual void
350  print(std::ostream& os) const {
351  os << "Layout:" << std::endl;
352  for (int i = 0; i < 17; i++) {
353  for (int j = 0; j < 3; j++)
354  os << card(layout[i][j]) << " ";
355  if ((i+1) % 3 == 0)
356  os << std::endl;
357  else
358  os << " \t";
359  }
360  os << std::endl << std::endl;
361 
362  os << "Solution:" << std::endl;
363  for (int i = 0; i < 52; ++i) {
364  if (x[i].assigned())
365  os << card(x[i].val()) << " ";
366  else
367  os << " ";
368  if ((i + 1) % 13 == 0)
369  os << std::endl;
370  }
371  os << std::endl;
372  os << std::endl;
373  }
374 
376  BlackHole(bool share, BlackHole& s) : Script(share,s) {
377  x.update(*this, share, s.x);
378  y.update(*this, share, s.y);
379  }
381  virtual Space*
382  copy(bool share) {
383  return new BlackHole(share,*this);
384  }
385 };
386 
390 int
391 main(int argc, char* argv[]) {
392  SizeOptions opt("Black Hole patience");
395  "no symmetry breaking");
396  opt.symmetry(BlackHole::SYMMETRY_CONDITIONAL,"conditional",
397  "break conditional symmetries");
400  "reified", "use reified propagation");
402  "dfa", "use DFA-based extensional propagation");
404  "tuple-set", "use TupleSet-based extensional propagation");
405  opt.icl(ICL_DOM);
406  opt.parse(argc,argv);
407  // Generates the new board
408  generate(opt.size());
409  Script::run<BlackHole,DFS,SizeOptions>(opt);
410  return 0;
411 }
412 
413 // STATISTICS: example-any