Generated on Thu Mar 7 2013 10:21:14 for Gecode by doxygen 1.8.3.1
queens.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2001
8  *
9  * Last modified:
10  * $Date: 2011-05-03 00:31:59 +1000 (Tue, 03 May 2011) $ by $Author: schulte $
11  * $Revision: 11982 $
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 #include <gecode/minimodel.hh>
41 
42 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
43 #include <QtGui>
44 #endif
45 
46 using namespace Gecode;
47 
57 class Queens : public Script {
58 public:
62  enum {
65  PROP_DISTINCT
66  };
69  : q(*this,opt.size(),0,opt.size()-1) {
70  const int n = q.size();
71  switch (opt.propagation()) {
72  case PROP_BINARY:
73  for (int i = 0; i<n; i++)
74  for (int j = i+1; j<n; j++) {
75  rel(*this, q[i] != q[j]);
76  rel(*this, q[i]+i != q[j]+j);
77  rel(*this, q[i]-i != q[j]-j);
78  }
79  break;
80  case PROP_MIXED:
81  for (int i = 0; i<n; i++)
82  for (int j = i+1; j<n; j++) {
83  rel(*this, q[i]+i != q[j]+j);
84  rel(*this, q[i]-i != q[j]-j);
85  }
86  distinct(*this, q, opt.icl());
87  break;
88  case PROP_DISTINCT:
89  distinct(*this, IntArgs::create(n,0,1), q, opt.icl());
90  distinct(*this, IntArgs::create(n,0,-1), q, opt.icl());
91  distinct(*this, q, opt.icl());
92  break;
93  }
95  }
96 
98  Queens(bool share, Queens& s) : Script(share,s) {
99  q.update(*this, share, s.q);
100  }
101 
103  virtual Space*
104  copy(bool share) {
105  return new Queens(share,*this);
106  }
107 
109  virtual void
110  print(std::ostream& os) const {
111  os << "queens\t";
112  for (int i = 0; i < q.size(); i++) {
113  os << q[i] << ", ";
114  if ((i+1) % 10 == 0)
115  os << std::endl << "\t";
116  }
117  os << std::endl;
118  }
119 };
120 
121 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
122 
123 class QueensInspector : public Gist::Inspector {
124 protected:
126  QGraphicsScene* scene;
128  QMainWindow* mw;
130  static const int unit = 20;
131 public:
133  QueensInspector(void) : scene(NULL), mw(NULL) {}
135  virtual void inspect(const Space& s) {
136  const Queens& q = static_cast<const Queens&>(s);
137 
138  if (!scene)
139  initialize();
140  QList <QGraphicsItem*> itemList = scene->items();
141  foreach (QGraphicsItem* i, scene->items()) {
142  scene->removeItem(i);
143  delete i;
144  }
145 
146  for (int i=0; i<q.q.size(); i++) {
147  for (int j=0; j<q.q.size(); j++) {
148  scene->addRect(i*unit,j*unit,unit,unit);
149  }
150  QBrush b(q.q[i].assigned() ? Qt::black : Qt::red);
151  QPen p(q.q[i].assigned() ? Qt::black : Qt::white);
152  for (IntVarValues xv(q.q[i]); xv(); ++xv) {
153  scene->addEllipse(QRectF(i*unit+unit/4,xv.val()*unit+unit/4,
154  unit/2,unit/2), p, b);
155  }
156  }
157  mw->show();
158  }
159 
161  void initialize(void) {
162  mw = new QMainWindow();
163  scene = new QGraphicsScene();
164  QGraphicsView* view = new QGraphicsView(scene);
165  view->setRenderHints(QPainter::Antialiasing);
166  mw->setCentralWidget(view);
167  mw->setAttribute(Qt::WA_QuitOnClose, false);
168  mw->setAttribute(Qt::WA_DeleteOnClose, false);
169  QAction* closeWindow = new QAction("Close window", mw);
170  closeWindow->setShortcut(QKeySequence("Ctrl+W"));
171  mw->connect(closeWindow, SIGNAL(triggered()),
172  mw, SLOT(close()));
173  mw->addAction(closeWindow);
174  }
175 
177  virtual std::string name(void) { return "Board"; }
179  virtual void finalize(void) {
180  delete mw;
181  mw = NULL;
182  }
183 };
184 
185 #endif /* GECODE_HAS_GIST */
186 
190 int
191 main(int argc, char* argv[]) {
192  SizeOptions opt("Queens");
193  opt.iterations(500);
194  opt.size(100);
196  opt.propagation(Queens::PROP_BINARY, "binary",
197  "only binary disequality constraints");
198  opt.propagation(Queens::PROP_MIXED, "mixed",
199  "single distinct and binary disequality constraints");
200  opt.propagation(Queens::PROP_DISTINCT, "distinct",
201  "three distinct constraints");
202 
203 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
204  QueensInspector ki;
205  opt.inspect.click(&ki);
206 #endif
207 
208  opt.parse(argc,argv);
209  Script::run<Queens,DFS,SizeOptions>(opt);
210  return 0;
211 }
212 
213 // STATISTICS: example-any
214