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 * Christian Schulte <schulte@gecode.org>
6 *
7 * Copyright:
8 * Mikael Lagerkvist, 2008
9 * Christian Schulte, 2001
10 *
11 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.org
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
36#include <gecode/driver.hh>
37#include <gecode/int.hh>
38#include <gecode/minimodel.hh>
39
40#if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
41#include <QtGui>
42#if QT_VERSION >= 0x050000
43#include <QtWidgets>
44#endif
45#endif
46
47using namespace Gecode;
48
49
50/** \brief Custom brancher for knight's tours using Warnsdorff's rule
51 *
52 * This class implements Warnsdorff's rule for finding knight's
53 * tours. The next position is choosen by taking the jump that
54 * minimizes the number of alternatives in the next step.
55 *
56 * \relates Knights
57 */
58class Warnsdorff : public Brancher {
59protected:
60 /// Views of the brancher
61 ViewArray<Int::IntView> x;
62 /// Next variable to branch on
63 mutable int start;
64 /// %Choice
65 class Choice : public Gecode::Choice {
66 public:
67 /// Position of variable
68 int pos;
69 /// Value of variable
70 int val;
71 /** Initialize choice for brancher \a b, position \a pos0,
72 * and value \a val0.
73 */
74 Choice(const Brancher& b, int pos0, int val0)
75 : Gecode::Choice(b,2), pos(pos0), val(val0) {}
76 /// Archive into \a e
77 virtual void archive(Archive& e) const {
78 Gecode::Choice::archive(e);
79 e << pos << val;
80 }
81 };
82
83 /// Construct brancher
84 Warnsdorff(Home home, ViewArray<Int::IntView>& xv)
85 : Brancher(home), x(xv), start(0) {}
86 /// Copy constructor
87 Warnsdorff(Space& home, Warnsdorff& b)
88 : Brancher(home, b), start(b.start) {
89 x.update(home, b.x);
90 }
91public:
92 /// Check status of brancher, return true if alternatives left
93 virtual bool status(const Space&) const {
94 // A path to follow can be at most x.size() long
95 for (int n=x.size(); n--; ) {
96 if (!x[start].assigned())
97 return true;
98 // Follow path of assigned variables
99 start = x[start].val();
100 }
101 return false;
102 }
103 /// Return choice
104 virtual Gecode::Choice* choice(Space&) {
105 Int::ViewValues<Int::IntView> iv(x[start]);
106 int n = iv.val();
107 unsigned int min = x[n].size();
108 ++iv;
109 // Choose the value with the fewest neighbors
110 while (iv()) {
111 if (x[iv.val()].size() < min) {
112 n = iv.val();
113 min = x[n].size();
114 }
115 ++iv;
116 }
117 return new Choice(*this, start, n);
118 }
119 /// Return choice
120 virtual Choice* choice(const Space&, Archive& e) {
121 int pos, val;
122 e >> pos >> val;
123 return new Choice(*this, pos, val);
124 }
125 /// Perform commit for choice \a _c and alternative \a a
126 virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
127 unsigned int a) {
128 const Choice& c = static_cast<const Choice&>(_c);
129 if (a == 0)
130 return me_failed(x[c.pos].eq(home, c.val)) ? ES_FAILED : ES_OK;
131 else
132 return me_failed(x[c.pos].nq(home, c.val)) ? ES_FAILED : ES_OK;
133 }
134 /// Print explanation
135 virtual void print(const Space&, const Gecode::Choice& _c,
136 unsigned int a,
137 std::ostream& o) const {
138 const Choice& c = static_cast<const Choice&>(_c);
139 o << "x[" << c.pos << "] "
140 << ((a == 0) ? "=" : "!=")
141 << " " << c.val;
142 }
143 /// Copy brancher
144 virtual Actor* copy(Space& home) {
145 return new (home) Warnsdorff(home, *this);
146 }
147 /// Post brancher
148 static void post(Home home, const IntVarArgs& x) {
149 ViewArray<Int::IntView> xv(home, x);
150 (void) new (home) Warnsdorff(home, xv);
151 }
152 /// Delete brancher and return its size
153 virtual size_t dispose(Space&) {
154 return sizeof(*this);
155 }
156};
157
158
159/// Base-class for knight's tour example
160class Knights : public Script {
161public:
162 /// Size of board
163 const int n;
164 /// Maps board field to successor field
165 IntVarArray succ;
166 /// Propagation to use for model
167 enum {
168 PROP_REIFIED, ///< Use reified constraints
169 PROP_CIRCUIT ///< Use single circuit constraints
170 };
171 /// Branching to use for model
172 enum {
173 BRANCH_NAIVE, ///< Use naive, lexicographical branching
174 BRANCH_WARNSDORFF, ///< Use Warnsdorff's rule
175 };
176 /// Return field at position \a x, \a y
177 int f(int x, int y) const {
178 return x + y*n;
179 }
180 /// Return x coordinate at field \a f
181 int x(int f) const {
182 return f % n;
183 }
184 /// Return y coordinate at field \a f
185 int y(int f) const {
186 return f / n;
187 }
188 /// Compute set of neighbour fields
189 IntSet neighbors(int i) {
190 static const int moves[8][2] = {
191 {-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}
192 };
193 int nbs[8]; int n_nbs = 0;
194 for (int m=0; m<8; m++) {
195 int nx = x(i) + moves[m][0], ny = y(i) + moves[m][1];
196 if ((nx >= 0) && (nx < n) && (ny >= 0) && (ny < n))
197 nbs[n_nbs++] = f(nx,ny);
198 }
199 return IntSet(nbs,n_nbs);
200 }
201 /// Constructor
202 Knights(const SizeOptions& opt)
203 : Script(opt), n(opt.size()), succ(*this,n*n,0,n*n-1) {
204 switch (opt.branching()) {
205 case BRANCH_NAIVE:
206 branch(*this, succ, INT_VAR_NONE(), INT_VAL_MIN());
207 break;
208 case BRANCH_WARNSDORFF:
209 Warnsdorff::post(*this, succ);
210 break;
211 }
212 }
213 /// Constructor for cloning \a s
214 Knights(Knights& s) : Script(s), n(s.n) {
215 succ.update(*this, s.succ);
216 }
217 /// Print board
218 virtual void
219 print(std::ostream& os) const {
220 int* jump = new int[n*n];
221 {
222 int j=0;
223 for (int i=0; i<n*n; i++) {
224 jump[j]=i; j=succ[j].min();
225 }
226 }
227 os << "\t";
228 for (int i = 0; i < n; i++) {
229 for (int j = 0; j < n; j++) {
230 os.width(3);
231 os << jump[f(i,j)] << " ";
232 }
233 os << std::endl << "\t";
234 }
235 os << std::endl;
236 delete [] jump;
237 }
238};
239
240/**
241 * \brief %Example: n-Knight's tour (simple model)
242 *
243 * Fill an n times n chess board with knight's moves such that
244 * the knight does a full tour (last move reaches first move
245 * again). The formulation is due to Gert Smolka.
246 *
247 * \ingroup Example
248 *
249 */
250class KnightsReified : public Knights {
251public:
252 KnightsReified(const SizeOptions& opt) : Knights(opt) {
253 const int nn = n*n;
254
255 // Map knight to its predecessor of succesor on board
256 IntVarArgs jump(nn);
257 IntVarArgs pred(nn);
258
259 for (int i = nn; i--; ) {
260 IntVar p(*this,0,nn-1); pred[i]=p;
261 IntVar j(*this,0,nn-1); jump[i]=j;
262 }
263
264 // Place the first two knights
265 rel(*this, jump[f(0,0)], IRT_EQ, 0);
266 rel(*this, jump[f(1,2)], IRT_EQ, 1);
267
268 distinct(*this, jump, opt.ipl());
269 channel(*this, succ, pred, opt.ipl());
270
271 for (int f = 0; f < nn; f++) {
272 IntSet ds = neighbors(f);
273 for (IntSetValues i(ds); i(); ++i)
274 rel(*this,
275 expr(*this, (jump[i.val()]-jump[f] == 1)),
276 BOT_XOR,
277 expr(*this, (jump[i.val()]-jump[f] == 1-nn)),
278 expr(*this, (succ[f] == i.val())));
279 dom(*this, pred[f], ds);
280 dom(*this, succ[f], ds);
281 rel(*this, succ[f], IRT_NQ, pred[f]);
282 }
283 }
284 /// Constructor for cloning \a s
285 KnightsReified(KnightsReified& s) : Knights(s) {}
286 /// Copy during cloning
287 virtual Space*
288 copy(void) {
289 return new KnightsReified(*this);
290 }
291};
292
293/**
294 * \brief %Example: n-%Knights tour (model using circuit)
295 *
296 * Fill an n times n chess board with knights such that the
297 * knights do a full tour by knights move (last knight reaches
298 * first knight again).
299 *
300 * \ingroup Example
301 *
302 */
303class KnightsCircuit : public Knights {
304public:
305 KnightsCircuit(const SizeOptions& opt) : Knights(opt) {
306 // Fix the first move
307 rel(*this, succ[0], IRT_EQ, f(1,2));
308
309 circuit(*this, succ, opt.ipl());
310
311 for (int f = 0; f < n*n; f++)
312 dom(*this, succ[f], neighbors(f));
313 }
314 /// Constructor for cloning \a s
315 KnightsCircuit(KnightsCircuit& s) : Knights(s) {}
316 /// Copy during cloning
317 virtual Space*
318 copy(void) {
319 return new KnightsCircuit(*this);
320 }
321};
322
323/*
324 * Just to fool some scripts:
325 * \brief %Example: n-Knight's tour
326 *
327 */
328
329#if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
330/// Inspector showing knight moves on a chess board
331class KnightsInspector : public Gist::Inspector {
332protected:
333 /// The graphics scene displaying the board
334 QGraphicsScene* scene;
335 /// The window containing the graphics scene
336 QMainWindow* mw;
337 /// The size of a field on the board
338 static const int unit = 30;
339public:
340 /// Constructor
341 KnightsInspector(void) : scene(nullptr), mw(nullptr) {}
342 /// Inspect space \a s
343 virtual void inspect(const Space& s) {
344 const Knights& k = static_cast<const Knights&>(s);
345
346 if (!scene)
347 initialize();
348 QList <QGraphicsItem*> itemList = scene->items();
349 foreach (QGraphicsItem* i, scene->items()) {
350 scene->removeItem(i);
351 delete i;
352 }
353
354 for (int i=0; i<k.n; i++) {
355 for (int j=0; j<k.n; j++) {
356 scene->addRect(i*unit,j*unit,unit,unit);
357
358 QPen pen(Qt::black, 2);
359 if (!k.succ[i*k.n+j].assigned()) {
360 pen.setColor(Qt::red);
361 pen.setStyle(Qt::DotLine);
362 pen.setWidth(0);
363 }
364 for (IntVarValues xv(k.succ[i*k.n+j]); xv(); ++xv) {
365 int ky = xv.val() % k.n;
366 int kx = xv.val() / k.n;
367 scene->addLine(i*unit+unit/2,j*unit+unit/2,
368 kx*unit+unit/2,ky*unit+unit/2,
369 pen);
370 }
371
372 }
373 }
374 mw->show();
375 }
376
377 /// Set up main window
378 void initialize(void) {
379 mw = new QMainWindow();
380 scene = new QGraphicsScene();
381 QGraphicsView* view = new QGraphicsView(scene);
382 view->setRenderHints(QPainter::Antialiasing);
383 mw->setCentralWidget(view);
384 mw->setAttribute(Qt::WA_QuitOnClose, false);
385 mw->setAttribute(Qt::WA_DeleteOnClose, false);
386 QAction* closeWindow = new QAction("Close window", mw);
387 closeWindow->setShortcut(QKeySequence("Ctrl+W"));
388 mw->connect(closeWindow, SIGNAL(triggered()),
389 mw, SLOT(close()));
390 mw->addAction(closeWindow);
391 }
392
393 /// Name of the inspector
394 virtual std::string name(void) { return "Board"; }
395 /// Finalize inspector
396 virtual void finalize(void) {
397 delete mw;
398 mw = nullptr;
399 }
400};
401#endif
402
403/** \brief Main-function
404 * \relates Knights
405 */
406int
407main(int argc, char* argv[]) {
408 SizeOptions opt("Knights");
409 opt.iterations(100);
410 opt.size(8);
411 opt.propagation(Knights::PROP_CIRCUIT);
412 opt.propagation(Knights::PROP_REIFIED, "reified");
413 opt.propagation(Knights::PROP_CIRCUIT, "circuit");
414 opt.branching(Knights::BRANCH_NAIVE);
415 opt.branching(Knights::BRANCH_NAIVE, "naive");
416 opt.branching(Knights::BRANCH_WARNSDORFF, "warnsdorff");
417
418#if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
419 KnightsInspector ki;
420 opt.inspect.click(&ki);
421#endif
422
423 opt.parse(argc,argv);
424
425 if (opt.propagation() == Knights::PROP_REIFIED) {
426 Script::run<KnightsReified,DFS,SizeOptions>(opt);
427 } else {
428 Script::run<KnightsCircuit,DFS,SizeOptions>(opt);
429 }
430 return 0;
431}
432
433// STATISTICS: example-any
434