44 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST) 46 #if QT_VERSION >= 0x050000 81 virtual size_t size(
void)
const {
96 :
Brancher(home, share, b), start(b.start) {
103 for (
int n=x.
size();
n--; ) {
107 start = x[start].val();
125 return new Choice(*
this, start, n);
131 return new Choice(*
this, pos, val);
145 std::ostream& o)
const {
147 o <<
"x[" << c.
pos <<
"] " 148 << ((a == 0) ?
"=" :
"!=")
153 return new (home)
Warnsdorff(home, share, *
this);
162 return sizeof(*this);
185 int f(
int x,
int y)
const {
198 static const int moves[8][2] = {
199 {-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}
201 int nbs[8];
int n_nbs = 0;
202 for (
int m=0; m<8; m++) {
203 int nx =
x(i) + moves[m][0], ny = y(i) + moves[m][1];
204 if ((nx >= 0) && (nx < n) && (ny >= 0) && (ny < n))
205 nbs[n_nbs++] = f(nx,ny);
211 :
Script(opt), n(opt.
size()), succ(*this,n*n,0,n*n-1) {
216 case BRANCH_WARNSDORFF:
228 int* jump =
new int[n*
n];
231 for (
int i=0;
i<n*
n;
i++) {
232 jump[j]=
i; j=succ[j].min();
236 for (
int i = 0;
i <
n;
i++) {
237 for (
int j = 0; j <
n; j++) {
239 os << jump[f(
i,j)] <<
" ";
241 os << std::endl <<
"\t";
267 for (
int i = nn;
i--; ) {
269 IntVar j(*
this,0,nn-1); jump[
i]=j;
279 for (
int f = 0; f < nn; f++) {
283 expr(*
this, (jump[
i.val()]-jump[f] == 1)),
285 expr(*
this, (jump[
i.val()]-jump[f] == 1-nn)),
286 expr(*
this, (succ[f] ==
i.val())));
287 dom(*
this, pred[f], ds);
288 dom(*
this, succ[f], ds);
319 for (
int f = 0; f <
n*
n; f++)
320 dom(*
this, succ[f], neighbors(f));
337 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST) 342 QGraphicsScene* scene;
346 static const int unit = 30;
349 KnightsInspector(
void) : scene(NULL), mw(NULL) {}
351 virtual void inspect(
const Space& s) {
356 QList <QGraphicsItem*> itemList = scene->items();
357 foreach (QGraphicsItem*
i, scene->items()) {
358 scene->removeItem(i);
362 for (
int i=0; i<k.
n; i++) {
363 for (
int j=0; j<k.
n; j++) {
364 scene->addRect(i*unit,j*unit,unit,unit);
366 QPen pen(Qt::black, 2);
368 pen.setColor(Qt::red);
369 pen.setStyle(Qt::DotLine);
373 int ky = xv.val() % k.
n;
374 int kx = xv.val() / k.
n;
375 scene->addLine(i*unit+unit/2,j*unit+unit/2,
376 kx*unit+unit/2,ky*unit+unit/2,
386 void initialize(
void) {
387 mw =
new QMainWindow();
388 scene =
new QGraphicsScene();
389 QGraphicsView* view =
new QGraphicsView(scene);
390 view->setRenderHints(QPainter::Antialiasing);
391 mw->setCentralWidget(view);
392 mw->setAttribute(Qt::WA_QuitOnClose,
false);
393 mw->setAttribute(Qt::WA_DeleteOnClose,
false);
394 QAction* closeWindow =
new QAction(
"Close window", mw);
395 closeWindow->setShortcut(QKeySequence(
"Ctrl+W"));
396 mw->connect(closeWindow, SIGNAL(triggered()),
398 mw->addAction(closeWindow);
402 virtual std::string name(
void) {
return "Board"; }
404 virtual void finalize(
void) {
426 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST) 431 opt.
parse(argc,argv);
434 Script::run<KnightsReified,DFS,SizeOptions>(
opt);
436 Script::run<KnightsCircuit,DFS,SizeOptions>(
opt);
Value iterator for integer variables.
int y(int f) const
Return y coordinate at field f.
void size(unsigned int s)
Set default size.
Options for scripts with additional size parameter
Warnsdorff(Home home, ViewArray< Int::IntView > &xv)
Construct brancher.
void update(Space &, bool share, ViewArray< View > &a)
Update array to be a clone of array a.
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
const int n
Size of board.
virtual size_t dispose(Space &)
Delete brancher and return its size.
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
void propagation(int v)
Set default propagation value.
KnightsReified(bool share, KnightsReified &s)
Constructor for cloning s.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Example: n-Knights tour (model using circuit)
bool assigned(void) const
Test if all variables are assigned.
bool pos(const View &x)
Test whether x is postive.
Use Warnsdorff's rule.
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Multi _c(Gecode::IntArgs(3, 1, 2, 3))
class Gecode::Options::_I inspect
void circuit(Home home, int offset, const IntVarArgs &x, IntPropLevel ipl)
Post propagator such that x forms a circuit.
void ipl(IntPropLevel i)
Set default integer propagation level.
Value iterator for integer views.
int pos
Position of variable.
ViewArray< Int::IntView > x
Views of the brancher.
Abstract base class for inspectors.
Parametric base-class for scripts.
void iterations(unsigned int i)
Set default number of iterations.
virtual Space * copy(bool share)
Copy during cloning.
int val(void) const
Return current value.
Base-class for both propagators and branchers.
KnightsCircuit(bool share, KnightsCircuit &s)
Constructor for cloning s.
Knights(bool share, Knights &s)
Constructor for cloning s.
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Gecode::FloatVal c(-8, 8)
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
int val
Value of variable.
struct Gecode::@554::NNF::@60::@62 a
For atomic nodes.
int p
Number of positive literals for node type.
int f(int x, int y) const
Return field at position x, y.
Gecode::IntArgs i(4, 1, 2, 3, 4)
virtual Gecode::Choice * choice(Space &)
Return choice.
Base-class for branchers.
Example: n-Knight's tour (simple model)
int n
Number of negative literals for node type.
Execution has resulted in failure.
KnightsCircuit(const SizeOptions &opt)
IntValBranch INT_VAL_MIN(void)
Select smallest value.
unsigned int size(I &i)
Size of all ranges of range iterator i.
void click(Gist::Inspector *i)
Add inspector that reacts on node double clicks.
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl)
Post propagator for for all .
Use single circuit constraints.
static void post(Home home, const IntVarArgs &x)
Post brancher.
Knights(const SizeOptions &opt)
Constructor.
void branching(int v)
Set default branching value.
virtual Actor * copy(Space &home, bool share)
Copy brancher.
virtual bool status(const Space &) const
Check status of brancher, return true if alternatives left.
Passing integer variables.
BoolVar expr(Home home, const BoolExpr &e, IntPropLevel ipl)
Post Boolean expression and return its value.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
KnightsReified(const SizeOptions &opt)
int main(int argc, char *argv[])
Main-function.
Node * x
Pointer to corresponding Boolean expression node.
int x(int f) const
Return x coordinate at field f.
virtual void archive(Archive &e) const
Archive into e.
Choice for performing commit
int start
Next variable to branch on.
Base-class for knight's tour example.
bool assigned(View x, int v)
Whether x is assigned to value v.
virtual Space * copy(bool share)
Copy during cloning.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
virtual void print(const Space &, const Gecode::Choice &_c, unsigned int a, std::ostream &o) const
Print explanation.
Custom brancher for knight's tours using Warnsdorff's rule.
Value iterator for integer sets.
virtual void print(std::ostream &os) const
Print board.
virtual size_t size(void) const
Report size occupied.
Warnsdorff(Space &home, bool share, Warnsdorff &b)
Copy constructor.
IntSet neighbors(int i)
Compute set of neighbour fields.
Use naive, lexicographical branching.
Choice(const Brancher &b, int pos0, int val0)
virtual void archive(Archive &e) const
Archive into e.
virtual Choice * choice(const Space &, Archive &e)
Return choice.
Gecode toplevel namespace
struct Gecode::@554::NNF::@60::@61 b
For binary nodes (and, or, eqv)
int size(void) const
Return size of array (number of elements)
IntVarArray succ
Maps board field to successor field.
Home class for posting propagators
virtual ExecStatus commit(Space &home, const Gecode::Choice &_c, unsigned int a)
Perform commit for choice _c and alternative a.
bool me_failed(ModEvent me)
Check whether modification event me is failed.