Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/driver.hh>
35#include <gecode/int.hh>
36#include <gecode/minimodel.hh>
37
38#if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
39#include <QtGui>
40#if QT_VERSION >= 0x050000
41#include <QtWidgets>
42#endif
43#endif
44
45using namespace Gecode;
46
56class Queens : public Script {
57public:
61 enum {
65 };
67 Queens(const SizeOptions& opt)
68 : Script(opt), q(*this,opt.size(),0,opt.size()-1) {
69 const int n = q.size();
70 switch (opt.propagation()) {
71 case PROP_BINARY:
72 for (int i = 0; i<n; i++)
73 for (int j = i+1; j<n; j++) {
74 rel(*this, q[i] != q[j]);
75 rel(*this, q[i]+i != q[j]+j);
76 rel(*this, q[i]-i != q[j]-j);
77 }
78 break;
79 case PROP_MIXED:
80 for (int i = 0; i<n; i++)
81 for (int j = i+1; j<n; j++) {
82 rel(*this, q[i]+i != q[j]+j);
83 rel(*this, q[i]-i != q[j]-j);
84 }
85 distinct(*this, q, opt.ipl());
86 break;
87 case PROP_DISTINCT:
88 distinct(*this, IntArgs::create(n,0,1), q, opt.ipl());
89 distinct(*this, IntArgs::create(n,0,-1), q, opt.ipl());
90 distinct(*this, q, opt.ipl());
91 break;
92 }
94 }
95
97 Queens(Queens& s) : Script(s) {
98 q.update(*this, s.q);
99 }
100
102 virtual Space*
103 copy(void) {
104 return new Queens(*this);
105 }
106
108 virtual void
109 print(std::ostream& os) const {
110 os << "queens\t";
111 for (int i = 0; i < q.size(); i++) {
112 os << q[i] << ", ";
113 if ((i+1) % 10 == 0)
114 os << std::endl << "\t";
115 }
116 os << std::endl;
117 }
118};
119
120#if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
122class QueensInspector : public Gist::Inspector {
123protected:
125 QGraphicsScene* scene;
127 QMainWindow* mw;
129 static const int unit = 20;
130public:
132 QueensInspector(void) : scene(NULL), mw(NULL) {}
134 virtual void inspect(const Space& s) {
135 const Queens& q = static_cast<const Queens&>(s);
136
137 if (!scene)
138 initialize();
139 QList <QGraphicsItem*> itemList = scene->items();
140 foreach (QGraphicsItem* i, scene->items()) {
141 scene->removeItem(i);
142 delete i;
143 }
144
145 for (int i=0; i<q.q.size(); i++) {
146 for (int j=0; j<q.q.size(); j++) {
147 scene->addRect(i*unit,j*unit,unit,unit);
148 }
149 QBrush b(q.q[i].assigned() ? Qt::black : Qt::red);
150 QPen p(q.q[i].assigned() ? Qt::black : Qt::white);
151 for (IntVarValues xv(q.q[i]); xv(); ++xv) {
152 scene->addEllipse(QRectF(i*unit+unit/4,xv.val()*unit+unit/4,
153 unit/2,unit/2), p, b);
154 }
155 }
156 mw->show();
157 }
158
160 void initialize(void) {
161 mw = new QMainWindow();
162 scene = new QGraphicsScene();
163 QGraphicsView* view = new QGraphicsView(scene);
164 view->setRenderHints(QPainter::Antialiasing);
165 mw->setCentralWidget(view);
166 mw->setAttribute(Qt::WA_QuitOnClose, false);
167 mw->setAttribute(Qt::WA_DeleteOnClose, false);
168 QAction* closeWindow = new QAction("Close window", mw);
169 closeWindow->setShortcut(QKeySequence("Ctrl+W"));
170 mw->connect(closeWindow, SIGNAL(triggered()),
171 mw, SLOT(close()));
172 mw->addAction(closeWindow);
173 }
174
176 virtual std::string name(void) { return "Board"; }
178 virtual void finalize(void) {
179 delete mw;
180 mw = NULL;
181 }
182};
183
184#endif /* GECODE_HAS_GIST */
185
189int
190main(int argc, char* argv[]) {
191 SizeOptions opt("Queens");
192 opt.iterations(500);
193 opt.size(100);
194 opt.propagation(Queens::PROP_DISTINCT);
195 opt.propagation(Queens::PROP_BINARY, "binary",
196 "only binary disequality constraints");
197 opt.propagation(Queens::PROP_MIXED, "mixed",
198 "single distinct and binary disequality constraints");
199 opt.propagation(Queens::PROP_DISTINCT, "distinct",
200 "three distinct constraints");
201
202#if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
203 QueensInspector ki;
204 opt.inspect.click(&ki);
205#endif
206
207 opt.parse(argc,argv);
209 return 0;
210}
211
212// STATISTICS: example-any
213
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
Parametric base-class for scripts.
Definition driver.hh:729
static void run(const Options &opt, Script *s=NULL)
Definition script.hpp:290
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
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
Definition array.hpp:76
Integer variable array.
Definition int.hh:763
Value iterator for integer variables.
Definition int.hh:490
Options for scripts with additional size parameter
Definition driver.hh:675
Computation spaces.
Definition core.hpp:1742
bool assigned(void) const
Test if all variables are assigned.
Definition array.hpp:1026
int size(void) const
Return size of array (number of elements)
Definition array.hpp:926
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition array.hpp:1013
Example: n-Queens puzzle
Definition queens.cpp:56
virtual Space * copy(void)
Perform copying during cloning.
Definition queens.cpp:103
int main(int argc, char *argv[])
Main-function.
Definition queens.cpp:190
@ PROP_DISTINCT
Use three distinct constraints.
Definition queens.cpp:64
@ PROP_BINARY
Use only binary disequality constraints.
Definition queens.cpp:62
@ PROP_MIXED
Use single distinct and binary disequality constraints.
Definition queens.cpp:63
Queens(const SizeOptions &opt)
The actual problem.
Definition queens.cpp:67
Queens(Queens &s)
Constructor for cloning s.
Definition queens.cpp:97
virtual void print(std::ostream &os) const
Print solution.
Definition queens.cpp:109
IntVarArray q
Position of queens on boards.
Definition queens.cpp:59
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
Gecode toplevel namespace
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Definition distinct.cpp:46
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest domain size.
Definition var.hpp:206
Gecode::IntArgs i({1, 2, 3, 4})