knights.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Mikael Lagerkvist <lagerkvist@gecode.org>
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Mikael Lagerkvist, 2008
* Christian Schulte, 2001
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/minimodel.hh>
#if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
#include <QtGui>
#if QT_VERSION >= 0x050000
#include <QtWidgets>
#endif
#endif
using namespace Gecode;
class Warnsdorff : public Brancher {
protected:
ViewArray<Int::IntView> x;
mutable int start;
class Choice : public Gecode::Choice {
public:
int pos;
int val;
Choice(const Brancher& b, int pos0, int val0)
: Gecode::Choice(b,2), pos(pos0), val(val0) {}
virtual void archive(Archive& e) const {
Gecode::Choice::archive(e);
e << pos << val;
}
};
Warnsdorff(Home home, ViewArray<Int::IntView>& xv)
: Brancher(home), x(xv), start(0) {}
Warnsdorff(Space& home, Warnsdorff& b)
: Brancher(home, b), start(b.start) {
x.update(home, b.x);
}
public:
virtual bool status(const Space&) const {
// A path to follow can be at most x.size() long
for (int n=x.size(); n--; ) {
if (!x[start].assigned())
return true;
// Follow path of assigned variables
start = x[start].val();
}
return false;
}
virtual Gecode::Choice* choice(Space&) {
Int::ViewValues<Int::IntView> iv(x[start]);
int n = iv.val();
unsigned int min = x[n].size();
++iv;
// Choose the value with the fewest neighbors
while (iv()) {
if (x[iv.val()].size() < min) {
n = iv.val();
min = x[n].size();
}
++iv;
}
return new Choice(*this, start, n);
}
virtual Choice* choice(const Space&, Archive& e) {
int pos, val;
e >> pos >> val;
return new Choice(*this, pos, val);
}
virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
unsigned int a) {
const Choice& c = static_cast<const Choice&>(_c);
if (a == 0)
return me_failed(x[c.pos].eq(home, c.val)) ? ES_FAILED : ES_OK;
else
return me_failed(x[c.pos].nq(home, c.val)) ? ES_FAILED : ES_OK;
}
virtual void print(const Space&, const Gecode::Choice& _c,
unsigned int a,
std::ostream& o) const {
const Choice& c = static_cast<const Choice&>(_c);
o << "x[" << c.pos << "] "
<< ((a == 0) ? "=" : "!=")
<< " " << c.val;
}
virtual Actor* copy(Space& home) {
return new (home) Warnsdorff(home, *this);
}
static void post(Home home, const IntVarArgs& x) {
ViewArray<Int::IntView> xv(home, x);
(void) new (home) Warnsdorff(home, xv);
}
virtual size_t dispose(Space&) {
return sizeof(*this);
}
};
class Knights : public Script {
public:
const int n;
IntVarArray succ;
enum {
PROP_REIFIED,
PROP_CIRCUIT
};
enum {
BRANCH_NAIVE,
BRANCH_WARNSDORFF,
};
int f(int x, int y) const {
return x + y*n;
}
int x(int f) const {
return f % n;
}
int y(int f) const {
return f / n;
}
IntSet neighbors(int i) {
static const int moves[8][2] = {
{-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}
};
int nbs[8]; int n_nbs = 0;
for (int m=0; m<8; m++) {
int nx = x(i) + moves[m][0], ny = y(i) + moves[m][1];
if ((nx >= 0) && (nx < n) && (ny >= 0) && (ny < n))
nbs[n_nbs++] = f(nx,ny);
}
return IntSet(nbs,n_nbs);
}
Knights(const SizeOptions& opt)
: Script(opt), n(opt.size()), succ(*this,n*n,0,n*n-1) {
switch (opt.branching()) {
case BRANCH_NAIVE:
branch(*this, succ, INT_VAR_NONE(), INT_VAL_MIN());
break;
case BRANCH_WARNSDORFF:
Warnsdorff::post(*this, succ);
break;
}
}
Knights(Knights& s) : Script(s), n(s.n) {
succ.update(*this, s.succ);
}
virtual void
print(std::ostream& os) const {
int* jump = new int[n*n];
{
int j=0;
for (int i=0; i<n*n; i++) {
jump[j]=i; j=succ[j].min();
}
}
os << "\t";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
os.width(3);
os << jump[f(i,j)] << " ";
}
os << std::endl << "\t";
}
os << std::endl;
delete [] jump;
}
};
class KnightsReified : public Knights {
public:
KnightsReified(const SizeOptions& opt) : Knights(opt) {
const int nn = n*n;
// Map knight to its predecessor of succesor on board
IntVarArgs jump(nn);
IntVarArgs pred(nn);
for (int i = nn; i--; ) {
IntVar p(*this,0,nn-1); pred[i]=p;
IntVar j(*this,0,nn-1); jump[i]=j;
}
// Place the first two knights
rel(*this, jump[f(0,0)], IRT_EQ, 0);
rel(*this, jump[f(1,2)], IRT_EQ, 1);
distinct(*this, jump, opt.ipl());
channel(*this, succ, pred, opt.ipl());
for (int f = 0; f < nn; f++) {
IntSet ds = neighbors(f);
for (IntSetValues i(ds); i(); ++i)
rel(*this,
expr(*this, (jump[i.val()]-jump[f] == 1)),
BOT_XOR,
expr(*this, (jump[i.val()]-jump[f] == 1-nn)),
expr(*this, (succ[f] == i.val())));
dom(*this, pred[f], ds);
dom(*this, succ[f], ds);
rel(*this, succ[f], IRT_NQ, pred[f]);
}
}
KnightsReified(KnightsReified& s) : Knights(s) {}
virtual Space*
copy(void) {
return new KnightsReified(*this);
}
};
class KnightsCircuit : public Knights {
public:
KnightsCircuit(const SizeOptions& opt) : Knights(opt) {
// Fix the first move
rel(*this, succ[0], IRT_EQ, f(1,2));
circuit(*this, succ, opt.ipl());
for (int f = 0; f < n*n; f++)
dom(*this, succ[f], neighbors(f));
}
KnightsCircuit(KnightsCircuit& s) : Knights(s) {}
virtual Space*
copy(void) {
return new KnightsCircuit(*this);
}
};
/*
* Just to fool some scripts:
* \brief %Example: n-Knight's tour
*
*/
#if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
class KnightsInspector : public Gist::Inspector {
protected:
QGraphicsScene* scene;
QMainWindow* mw;
static const int unit = 30;
public:
KnightsInspector(void) : scene(NULL), mw(NULL) {}
virtual void inspect(const Space& s) {
const Knights& k = static_cast<const Knights&>(s);
if (!scene)
initialize();
QList <QGraphicsItem*> itemList = scene->items();
foreach (QGraphicsItem* i, scene->items()) {
scene->removeItem(i);
delete i;
}
for (int i=0; i<k.n; i++) {
for (int j=0; j<k.n; j++) {
scene->addRect(i*unit,j*unit,unit,unit);
QPen pen(Qt::black, 2);
if (!k.succ[i*k.n+j].assigned()) {
pen.setColor(Qt::red);
pen.setStyle(Qt::DotLine);
pen.setWidth(0);
}
for (IntVarValues xv(k.succ[i*k.n+j]); xv(); ++xv) {
int ky = xv.val() % k.n;
int kx = xv.val() / k.n;
scene->addLine(i*unit+unit/2,j*unit+unit/2,
kx*unit+unit/2,ky*unit+unit/2,
pen);
}
}
}
mw->show();
}
void initialize(void) {
mw = new QMainWindow();
scene = new QGraphicsScene();
QGraphicsView* view = new QGraphicsView(scene);
view->setRenderHints(QPainter::Antialiasing);
mw->setCentralWidget(view);
mw->setAttribute(Qt::WA_QuitOnClose, false);
mw->setAttribute(Qt::WA_DeleteOnClose, false);
QAction* closeWindow = new QAction("Close window", mw);
closeWindow->setShortcut(QKeySequence("Ctrl+W"));
mw->connect(closeWindow, SIGNAL(triggered()),
mw, SLOT(close()));
mw->addAction(closeWindow);
}
virtual std::string name(void) { return "Board"; }
virtual void finalize(void) {
delete mw;
mw = NULL;
}
};
#endif
int
main(int argc, char* argv[]) {
SizeOptions opt("Knights");
opt.iterations(100);
opt.size(8);
opt.propagation(Knights::PROP_CIRCUIT);
opt.propagation(Knights::PROP_REIFIED, "reified");
opt.propagation(Knights::PROP_CIRCUIT, "circuit");
opt.branching(Knights::BRANCH_NAIVE);
opt.branching(Knights::BRANCH_NAIVE, "naive");
opt.branching(Knights::BRANCH_WARNSDORFF, "warnsdorff");
#if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
KnightsInspector ki;
opt.inspect.click(&ki);
#endif
opt.parse(argc,argv);
if (opt.propagation() == Knights::PROP_REIFIED) {
Script::run<KnightsReified,DFS,SizeOptions>(opt);
} else {
Script::run<KnightsCircuit,DFS,SizeOptions>(opt);
}
return 0;
}
// STATISTICS: example-any
Gecode::Actor
Base-class for both propagators and branchers.
Definition core.hpp:628
Gecode::Archive
Archive representation
Definition archive.hpp:42
Gecode::Brancher::Space
friend class Space
Definition core.hpp:1444
Gecode::Brancher::Brancher
Brancher(Home home)
Constructor for creation.
Definition core.hpp:3605
Gecode::Brancher::Choice
friend class Choice
Definition core.hpp:1445
Gecode::Choice
Choice for performing commit
Definition core.hpp:1412
Gecode::Choice::archive
virtual void archive(Archive &e) const
Archive into e.
Definition core.cpp:891
Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > >::run
static void run(const Options &opt, Script *s=NULL)
Gecode::FloatVal::x
FloatValImpType x
Implementation of float value.
Definition float.hh:425
Gecode::Gist::Inspector
Abstract base class for inspectors.
Definition gist.hh:99
Gecode::Gist::Inspector::inspect
virtual void inspect(const Space &s)=0
Call-back function.
Gecode::Gist::Inspector::finalize
virtual void finalize(void)
Clean up when Gist exits.
Definition gist.cpp:48
Gecode::Gist::Inspector::name
virtual std::string name(void)
Name of the inspector.
Definition gist.cpp:45
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::IntSetValues
Value iterator for integer sets.
Definition int.hh:333
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::IntVarArgs
Passing integer variables.
Definition int.hh:656
Gecode::IntVarArray
Integer variable array.
Definition int.hh:763
Gecode::IntVar
Integer variables.
Definition int.hh:371
Gecode::Int::ViewValues
Value iterator for integer views.
Definition view.hpp:94
Gecode::Iter::Ranges::ToValues::val
int val(void) const
Return current value.
Definition ranges-values.hpp:129
Gecode::SizeOptions
Options for scripts with additional size parameter
Definition driver.hh:675
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::VarArray::assigned
bool assigned(void) const
Test if all variables are assigned.
Definition array.hpp:1026
Gecode::ViewArray
View arrays.
Definition array.hpp:253
KnightsCircuit::KnightsCircuit
KnightsCircuit(KnightsCircuit &s)
Constructor for cloning s.
Definition knights.cpp:315
KnightsCircuit::KnightsCircuit
KnightsCircuit(const SizeOptions &opt)
Definition knights.cpp:305
KnightsCircuit::copy
virtual Space * copy(void)
Copy during cloning.
Definition knights.cpp:318
KnightsReified::KnightsReified
KnightsReified(const SizeOptions &opt)
Definition knights.cpp:252
KnightsReified::copy
virtual Space * copy(void)
Copy during cloning.
Definition knights.cpp:288
KnightsReified::KnightsReified
KnightsReified(KnightsReified &s)
Constructor for cloning s.
Definition knights.cpp:285
Knights::main
int main(int argc, char *argv[])
Main-function.
Definition knights.cpp:407
Knights::n
const int n
Size of board.
Definition knights.cpp:163
Knights::x
int x(int f) const
Return x coordinate at field f.
Definition knights.cpp:181
Knights::print
virtual void print(std::ostream &os) const
Print board.
Definition knights.cpp:219
Knights::neighbors
IntSet neighbors(int i)
Compute set of neighbour fields.
Definition knights.cpp:189
Knights::PROP_REIFIED
@ PROP_REIFIED
Use reified constraints.
Definition knights.cpp:168
Knights::PROP_CIRCUIT
@ PROP_CIRCUIT
Use single circuit constraints.
Definition knights.cpp:169
Knights::BRANCH_WARNSDORFF
@ BRANCH_WARNSDORFF
Use Warnsdorff's rule.
Definition knights.cpp:174
Knights::BRANCH_NAIVE
@ BRANCH_NAIVE
Use naive, lexicographical branching.
Definition knights.cpp:173
Knights::succ
IntVarArray succ
Maps board field to successor field.
Definition knights.cpp:165
Knights::Knights
Knights(const SizeOptions &opt)
Constructor.
Definition knights.cpp:202
Knights::Knights
Knights(Knights &s)
Constructor for cloning s.
Definition knights.cpp:214
Knights::f
int f(int x, int y) const
Return field at position x, y.
Definition knights.cpp:177
Knights::y
int y(int f) const
Return y coordinate at field f.
Definition knights.cpp:185
Test::Options::parse
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
Warnsdorff::Choice
Choice
Definition knights.cpp:65
Warnsdorff::Choice::pos
int pos
Position of variable.
Definition knights.cpp:68
Warnsdorff::Choice::Choice
Choice(const Brancher &b, int pos0, int val0)
Definition knights.cpp:74
Warnsdorff::Choice::val
int val
Value of variable.
Definition knights.cpp:70
Warnsdorff::Choice::archive
virtual void archive(Archive &e) const
Archive into e.
Definition knights.cpp:77
Warnsdorff::copy
virtual Actor * copy(Space &home)
Copy brancher.
Definition knights.cpp:144
Warnsdorff::choice
virtual Gecode::Choice * choice(Space &)
Return choice.
Definition knights.cpp:104
Warnsdorff::post
static void post(Home home, const IntVarArgs &x)
Post brancher.
Definition knights.cpp:148
Warnsdorff::Warnsdorff
Warnsdorff(Space &home, Warnsdorff &b)
Copy constructor.
Definition knights.cpp:87
Warnsdorff::x
ViewArray< Int::IntView > x
Views of the brancher.
Definition knights.cpp:61
Warnsdorff::dispose
virtual size_t dispose(Space &)
Delete brancher and return its size.
Definition knights.cpp:153
Warnsdorff::commit
virtual ExecStatus commit(Space &home, const Gecode::Choice &_c, unsigned int a)
Perform commit for choice _c and alternative a.
Definition knights.cpp:126
Warnsdorff::choice
virtual Choice * choice(const Space &, Archive &e)
Return choice.
Definition knights.cpp:120
Warnsdorff::Warnsdorff
Warnsdorff(Home home, ViewArray< Int::IntView > &xv)
Construct brancher.
Definition knights.cpp:84
Warnsdorff::start
int start
Next variable to branch on.
Definition knights.cpp:63
Warnsdorff::status
virtual bool status(const Space &) const
Check status of brancher, return true if alternatives left.
Definition knights.cpp:93
Warnsdorff::print
virtual void print(const Space &, const Gecode::Choice &_c, unsigned int a, std::ostream &o) const
Print explanation.
Definition knights.cpp:135
driver.hh
int.hh
Gecode::me_failed
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
Gecode::Script
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition driver.hh:801
Gecode::rel
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
Gecode::IRT_EQ
@ IRT_EQ
Equality ( ).
Definition int.hh:926
Gecode::IRT_NQ
@ IRT_NQ
Disequality ( ).
Definition int.hh:927
Gecode::BOT_XOR
@ BOT_XOR
Exclusive or.
Definition int.hh:955
minimodel.hh
Gecode
Gecode toplevel namespace
Gecode::channel
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition channel.cpp:41
Gecode::expr
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:915
Gecode::distinct
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Definition distinct.cpp:46
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
Gecode::dom
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition dom.cpp:40
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
Gecode::ES_FAILED
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
Gecode::circuit
void circuit(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a circuit.
Definition circuit.cpp:73
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})