Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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 * 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
58class Warnsdorff : public Brancher {
59protected:
63 mutable int start;
65 class Choice : public Gecode::Choice {
66 public:
68 int pos;
70 int val;
74 Choice(const Brancher& b, int pos0, int val0)
75 : Gecode::Choice(b,2), pos(pos0), val(val0) {}
76
77 virtual void archive(Archive& e) const {
79 e << pos << val;
80 }
81 };
82
85 : Brancher(home), x(xv), start(0) {}
86
88 : Brancher(home, b), start(b.start) {
89 x.update(home, b.x);
90 }
91public:
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
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
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
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
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
144 virtual Actor* copy(Space& home) {
145 return new (home) Warnsdorff(home, *this);
146 }
147
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
153 virtual size_t dispose(Space&) {
154 return sizeof(*this);
155 }
156};
157
158
160class Knights : public Script {
161public:
163 const int n;
167 enum {
170 };
172 enum {
175 };
177 int f(int x, int y) const {
178 return x + y*n;
179 }
180
181 int x(int f) const {
182 return f % n;
183 }
184
185 int y(int f) const {
186 return f / n;
187 }
188
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
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
214 Knights(Knights& s) : Script(s), n(s.n) {
215 succ.update(*this, s.succ);
216 }
217
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
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
287 virtual Space*
288 copy(void) {
289 return new KnightsReified(*this);
290 }
291};
292
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
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)
331class KnightsInspector : public Gist::Inspector {
332protected:
334 QGraphicsScene* scene;
336 QMainWindow* mw;
338 static const int unit = 30;
339public:
341 KnightsInspector(void) : scene(NULL), mw(NULL) {}
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
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
394 virtual std::string name(void) { return "Board"; }
396 virtual void finalize(void) {
397 delete mw;
398 mw = NULL;
399 }
400};
401#endif
402
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) {
427 } else {
429 }
430 return 0;
431}
432
433// STATISTICS: example-any
434
Base-class for both propagators and branchers.
Definition core.hpp:628
Archive representation
Definition archive.hpp:42
friend class Space
Definition core.hpp:1446
Brancher(Home home)
Constructor for creation.
Definition core.hpp:3612
friend class Choice
Definition core.hpp:1447
Choice for performing commit
Definition core.hpp:1414
virtual void archive(Archive &e) const
Archive into e.
Definition core.cpp:892
static void run(const Options &opt, Script *s=NULL)
FloatValImpType x
Implementation of float value.
Definition float.hh:425
Abstract base class for inspectors.
Definition gist.hh:99
virtual void inspect(const Space &s)=0
Call-back function.
virtual void finalize(void)
Clean up when Gist exits.
Definition gist.cpp:48
virtual std::string name(void)
Name of the inspector.
Definition gist.cpp:45
Home class for posting propagators
Definition core.hpp:856
Value iterator for integer sets.
Definition int.hh:333
Integer sets.
Definition int.hh:174
Passing integer variables.
Definition int.hh:662
Integer variable array.
Definition int.hh:772
Integer variables.
Definition int.hh:371
Value iterator for integer views.
Definition view.hpp:94
int val(void) const
Return current value.
Options for scripts with additional size parameter
Definition driver.hh:675
Computation spaces.
Definition core.hpp:1744
bool assigned(void) const
Test if all variables are assigned.
Definition array.hpp:1032
View arrays.
Definition array.hpp:253
KnightsCircuit(KnightsCircuit &s)
Constructor for cloning s.
Definition knights.cpp:315
KnightsCircuit(const SizeOptions &opt)
Definition knights.cpp:305
virtual Space * copy(void)
Copy during cloning.
Definition knights.cpp:318
KnightsReified(const SizeOptions &opt)
Definition knights.cpp:252
virtual Space * copy(void)
Copy during cloning.
Definition knights.cpp:288
KnightsReified(KnightsReified &s)
Constructor for cloning s.
Definition knights.cpp:285
int main(int argc, char *argv[])
Main-function.
Definition knights.cpp:407
const int n
Size of board.
Definition knights.cpp:163
int x(int f) const
Return x coordinate at field f.
Definition knights.cpp:181
virtual void print(std::ostream &os) const
Print board.
Definition knights.cpp:219
IntSet neighbors(int i)
Compute set of neighbour fields.
Definition knights.cpp:189
@ PROP_REIFIED
Use reified constraints.
Definition knights.cpp:168
@ PROP_CIRCUIT
Use single circuit constraints.
Definition knights.cpp:169
@ BRANCH_WARNSDORFF
Use Warnsdorff's rule.
Definition knights.cpp:174
@ BRANCH_NAIVE
Use naive, lexicographical branching.
Definition knights.cpp:173
IntVarArray succ
Maps board field to successor field.
Definition knights.cpp:165
Knights(const SizeOptions &opt)
Constructor.
Definition knights.cpp:202
Knights(Knights &s)
Constructor for cloning s.
Definition knights.cpp:214
int f(int x, int y) const
Return field at position x, y.
Definition knights.cpp:177
int y(int f) const
Return y coordinate at field f.
Definition knights.cpp:185
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
int pos
Position of variable.
Definition knights.cpp:68
Choice(const Brancher &b, int pos0, int val0)
Definition knights.cpp:74
int val
Value of variable.
Definition knights.cpp:70
virtual void archive(Archive &e) const
Archive into e.
Definition knights.cpp:77
virtual Actor * copy(Space &home)
Copy brancher.
Definition knights.cpp:144
virtual Gecode::Choice * choice(Space &)
Return choice.
Definition knights.cpp:104
static void post(Home home, const IntVarArgs &x)
Post brancher.
Definition knights.cpp:148
Warnsdorff(Space &home, Warnsdorff &b)
Copy constructor.
Definition knights.cpp:87
ViewArray< Int::IntView > x
Views of the brancher.
Definition knights.cpp:61
virtual size_t dispose(Space &)
Delete brancher and return its size.
Definition knights.cpp:153
virtual ExecStatus commit(Space &home, const Gecode::Choice &_c, unsigned int a)
Perform commit for choice _c and alternative a.
Definition knights.cpp:126
virtual Choice * choice(const Space &, Archive &e)
Return choice.
Definition knights.cpp:120
Warnsdorff(Home home, ViewArray< Int::IntView > &xv)
Construct brancher.
Definition knights.cpp:84
int start
Next variable to branch on.
Definition knights.cpp:63
virtual bool status(const Space &) const
Check status of brancher, return true if alternatives left.
Definition knights.cpp:93
virtual void print(const Space &, const Gecode::Choice &_c, unsigned int a, std::ostream &o) const
Print explanation.
Definition knights.cpp:135
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition driver.hh:801
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
@ IRT_EQ
Equality ( )
Definition int.hh:941
@ IRT_NQ
Disequality ( )
Definition int.hh:942
@ BOT_XOR
Exclusive or.
Definition int.hh:970
Gecode toplevel namespace
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition channel.cpp:41
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:915
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Definition distinct.cpp:46
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition dom.cpp:40
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:773
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
void circuit(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a circuit.
Definition circuit.cpp:73
Post propagator for SetVar x
Definition set.hh:773
Gecode::IntArgs i({1, 2, 3, 4})