this repo has no description
dekker.one
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
47/**
48 * \brief %Example: n-%Queens puzzle
49 *
50 * Place n queens on an n times n chessboard such that they do not
51 * attack each other.
52 *
53 * \ingroup Example
54 *
55 */
56class Queens : public Script {
57public:
58 /// Position of queens on boards
59 IntVarArray q;
60 /// Propagation to use for model
61 enum {
62 PROP_BINARY, ///< Use only binary disequality constraints
63 PROP_MIXED, ///< Use single distinct and binary disequality constraints
64 PROP_DISTINCT ///< Use three distinct constraints
65 };
66 /// The actual problem
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 }
93 branch(*this, q, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
94 }
95
96 /// Constructor for cloning \a s
97 Queens(Queens& s) : Script(s) {
98 q.update(*this, s.q);
99 }
100
101 /// Perform copying during cloning
102 virtual Space*
103 copy(void) {
104 return new Queens(*this);
105 }
106
107 /// Print solution
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)
121/// Inspector showing queens on a chess board
122class QueensInspector : public Gist::Inspector {
123protected:
124 /// The graphics scene displaying the board
125 QGraphicsScene* scene;
126 /// The window containing the graphics scene
127 QMainWindow* mw;
128 /// The size of a field on the board
129 static const int unit = 20;
130public:
131 /// Constructor
132 QueensInspector(void) : scene(nullptr), mw(nullptr) {}
133 /// Inspect space \a s
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
159 /// Set up main window
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
175 /// Name of the inspector
176 virtual std::string name(void) { return "Board"; }
177 /// Finalize inspector
178 virtual void finalize(void) {
179 delete mw;
180 mw = nullptr;
181 }
182};
183
184#endif /* GECODE_HAS_GIST */
185
186/** \brief Main-function
187 * \relates Queens
188 */
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);
208 Script::run<Queens,DFS,SizeOptions>(opt);
209 return 0;
210}
211
212// STATISTICS: example-any
213