Generated on Thu Feb 14 2013 20:59:22 for Gecode by doxygen 1.8.3.1
knights.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  * Christian Schulte <schulte@gecode.org>
6  *
7  * Copyright:
8  * Mikael Lagerkvist, 2008
9  * Christian Schulte, 2001
10  *
11  * Last modified:
12  * $Date: 2011-05-26 00:56:41 +1000 (Thu, 26 May 2011) $ by $Author: schulte $
13  * $Revision: 12022 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #include <gecode/driver.hh>
41 #include <gecode/int.hh>
42 #include <gecode/minimodel.hh>
43 
44 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
45 #include <QtGui>
46 #endif
47 
48 using namespace Gecode;
49 
50 
59 class Warnsdorff : public Brancher {
60 protected:
64  mutable int start;
66  class Choice : public Gecode::Choice {
67  public:
69  int pos;
71  int val;
75  Choice(const Brancher& b, int pos0, int val0)
76  : Gecode::Choice(b,2), pos(pos0), val(val0) {}
78  virtual size_t size(void) const {
79  return sizeof(Choice);
80  }
82  virtual void archive(Archive& e) const {
84  e << pos << val;
85  }
86  };
87 
90  : Brancher(home), x(xv), start(0) {}
92  Warnsdorff(Space& home, bool share, Warnsdorff& b)
93  : Brancher(home, share, b), start(b.start) {
94  x.update(home, share, b.x);
95  }
96 public:
98  virtual bool status(const Space&) const {
99  // A path to follow can be at most x.size() long
100  for (int n=x.size(); n--; ) {
101  if (!x[start].assigned())
102  return true;
103  // Follow path of assigned variables
104  start = x[start].val();
105  }
106  return false;
107  }
110  Int::ViewValues<Int::IntView> iv(x[start]);
111  int n = iv.val();
112  unsigned int min = x[n].size();
113  ++iv;
114  // Choose the value with the fewest neighbors
115  while (iv()) {
116  if (x[iv.val()].size() < min) {
117  n = iv.val();
118  min = x[n].size();
119  }
120  ++iv;
121  }
122  return new Choice(*this, start, n);
123  }
125  virtual Choice* choice(const Space&, Archive& e) {
126  int pos, val;
127  e >> pos >> val;
128  return new Choice(*this, pos, val);
129  }
131  virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
132  unsigned int a) {
133  const Choice& c = static_cast<const Choice&>(_c);
134  if (a == 0)
135  return me_failed(x[c.pos].eq(home, c.val)) ? ES_FAILED : ES_OK;
136  else
137  return me_failed(x[c.pos].nq(home, c.val)) ? ES_FAILED : ES_OK;
138  }
140  virtual Actor* copy(Space& home, bool share) {
141  return new (home) Warnsdorff(home, share, *this);
142  }
144  static void post(Home home, const IntVarArgs& x) {
145  ViewArray<Int::IntView> xv(home, x);
146  (void) new (home) Warnsdorff(home, xv);
147  }
149  virtual size_t dispose(Space&) {
150  return sizeof(*this);
151  }
152 };
153 
154 
156 class Knights : public Script {
157 public:
159  const int n;
163  enum {
165  PROP_CIRCUIT
166  };
168  enum {
171  };
173  int f(int x, int y) const {
174  return x + y*n;
175  }
177  int x(int f) const {
178  return f % n;
179  }
181  int y(int f) const {
182  return f / n;
183  }
186  static const int moves[8][2] = {
187  {-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}
188  };
189  int nbs[8]; int n_nbs = 0;
190  for (int m=0; m<8; m++) {
191  int nx = x(i) + moves[m][0], ny = y(i) + moves[m][1];
192  if ((nx >= 0) && (nx < n) && (ny >= 0) && (ny < n))
193  nbs[n_nbs++] = f(nx,ny);
194  }
195  return IntSet(nbs,n_nbs);
196  }
199  : n(opt.size()), succ(*this,n*n,0,n*n-1) {
200  switch (opt.branching()) {
201  case BRANCH_NAIVE:
202  branch(*this, succ, INT_VAR_NONE, INT_VAL_MIN);
203  break;
204  case BRANCH_WARNSDORFF:
205  Warnsdorff::post(*this, succ);
206  break;
207  }
208  }
210  Knights(bool share, Knights& s) : Script(share,s), n(s.n) {
211  succ.update(*this, share, s.succ);
212  }
214  virtual void
215  print(std::ostream& os) const {
216  int* jump = new int[n*n];
217  {
218  int j=0;
219  for (int i=0; i<n*n; i++) {
220  jump[j]=i; j=succ[j].min();
221  }
222  }
223  os << "\t";
224  for (int i = 0; i < n; i++) {
225  for (int j = 0; j < n; j++) {
226  os.width(3);
227  os << jump[f(i,j)] << " ";
228  }
229  os << std::endl << "\t";
230  }
231  os << std::endl;
232  delete [] jump;
233  }
234 };
235 
246 class KnightsReified : public Knights {
247 public:
249  const int nn = n*n;
250 
251  // Map knight to its predecessor of succesor on board
252  IntVarArgs jump(nn);
253  IntVarArgs pred(nn);
254 
255  for (int i = nn; i--; ) {
256  IntVar p(*this,0,nn-1); pred[i]=p;
257  IntVar j(*this,0,nn-1); jump[i]=j;
258  }
259 
260  // Place the first two knights
261  rel(*this, jump[f(0,0)], IRT_EQ, 0);
262  rel(*this, jump[f(1,2)], IRT_EQ, 1);
263 
264  distinct(*this, jump, opt.icl());
265  channel(*this, succ, pred, opt.icl());
266 
267  for (int f = 0; f < nn; f++) {
268  IntSet ds = neighbors(f);
269  for (IntSetValues i(ds); i(); ++i)
270  rel(*this,
271  expr(*this, (jump[i.val()]-jump[f] == 1)),
272  BOT_XOR,
273  expr(*this, (jump[i.val()]-jump[f] == 1-nn)),
274  expr(*this, (succ[f] == i.val())));
275  dom(*this, pred[f], ds);
276  dom(*this, succ[f], ds);
277  rel(*this, succ[f], IRT_NQ, pred[f]);
278  }
279  }
281  KnightsReified(bool share, KnightsReified& s) : Knights(share,s) {}
283  virtual Space*
284  copy(bool share) {
285  return new KnightsReified(share,*this);
286  }
287 };
288 
299 class KnightsCircuit : public Knights {
300 public:
302  // Fix the first move
303  rel(*this, succ[0], IRT_EQ, f(1,2));
304 
305  circuit(*this, succ, opt.icl());
306 
307  for (int f = 0; f < n*n; f++)
308  dom(*this, succ[f], neighbors(f));
309  }
311  KnightsCircuit(bool share, KnightsCircuit& s) : Knights(share,s) {}
313  virtual Space*
314  copy(bool share) {
315  return new KnightsCircuit(share,*this);
316  }
317 };
318 
319 /*
320  * Just to fool some scripts:
321  * \brief %Example: n-Knight's tour
322  *
323  */
324 
325 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
326 
327 class KnightsInspector : public Gist::Inspector {
328 protected:
330  QGraphicsScene* scene;
332  QMainWindow* mw;
334  static const int unit = 30;
335 public:
337  KnightsInspector(void) : scene(NULL), mw(NULL) {}
339  virtual void inspect(const Space& s) {
340  const Knights& k = static_cast<const Knights&>(s);
341 
342  if (!scene)
343  initialize();
344  QList <QGraphicsItem*> itemList = scene->items();
345  foreach (QGraphicsItem* i, scene->items()) {
346  scene->removeItem(i);
347  delete i;
348  }
349 
350  for (int i=0; i<k.n; i++) {
351  for (int j=0; j<k.n; j++) {
352  scene->addRect(i*unit,j*unit,unit,unit);
353 
354  QPen pen(Qt::black, 2);
355  if (!k.succ[i*k.n+j].assigned()) {
356  pen.setColor(Qt::red);
357  pen.setStyle(Qt::DotLine);
358  pen.setWidth(0);
359  }
360  for (IntVarValues xv(k.succ[i*k.n+j]); xv(); ++xv) {
361  int ky = xv.val() % k.n;
362  int kx = xv.val() / k.n;
363  scene->addLine(i*unit+unit/2,j*unit+unit/2,
364  kx*unit+unit/2,ky*unit+unit/2,
365  pen);
366  }
367 
368  }
369  }
370  mw->show();
371  }
372 
374  void initialize(void) {
375  mw = new QMainWindow();
376  scene = new QGraphicsScene();
377  QGraphicsView* view = new QGraphicsView(scene);
378  view->setRenderHints(QPainter::Antialiasing);
379  mw->setCentralWidget(view);
380  mw->setAttribute(Qt::WA_QuitOnClose, false);
381  mw->setAttribute(Qt::WA_DeleteOnClose, false);
382  QAction* closeWindow = new QAction("Close window", mw);
383  closeWindow->setShortcut(QKeySequence("Ctrl+W"));
384  mw->connect(closeWindow, SIGNAL(triggered()),
385  mw, SLOT(close()));
386  mw->addAction(closeWindow);
387  }
388 
390  virtual std::string name(void) { return "Board"; }
392  virtual void finalize(void) {
393  delete mw;
394  mw = NULL;
395  }
396 };
397 #endif
398 
402 int
403 main(int argc, char* argv[]) {
404  SizeOptions opt("Knights");
405  opt.iterations(100);
406  opt.size(8);
408  opt.propagation(Knights::PROP_REIFIED, "reified");
409  opt.propagation(Knights::PROP_CIRCUIT, "circuit");
411  opt.branching(Knights::BRANCH_NAIVE, "reified");
412  opt.branching(Knights::BRANCH_WARNSDORFF, "warnsdorff");
413 
414 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
415  KnightsInspector ki;
416  opt.inspect.click(&ki);
417 #endif
418 
419  opt.parse(argc,argv);
420 
421  if (opt.propagation() == Knights::PROP_REIFIED) {
422  Script::run<KnightsReified,DFS,SizeOptions>(opt);
423  } else {
424  Script::run<KnightsCircuit,DFS,SizeOptions>(opt);
425  }
426  return 0;
427 }
428 
429 // STATISTICS: example-any
430