Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
queen-armies.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 *
6 * Copyright:
7 * Mikael Lagerkvist, 2006
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
35#include <gecode/driver.hh>
36#include <gecode/int.hh>
37#include <gecode/minimodel.hh>
38#include <gecode/set.hh>
39
40using namespace Gecode;
41
47
68public:
69 const int n;
71 W;
73 b;
75
77 enum {
80 };
81
85 n(opt.size()),
86 U(*this, IntSet::empty, IntSet(0, n*n)),
87 W(*this, IntSet::empty, IntSet(0, n*n)),
88 w(*this, n*n, 0, 1),
89 b(*this, n*n, 0, 1),
90 q(*this, 0, n*n)
91 {
92 // Basic rules of the model
93 for (int i = n*n; i--; ) {
94 // w[i] means that no blacks are allowed on A[i]
95 rel(*this, w[i] == (U || A[i]));
96 // Make sure blacks and whites are disjoint.
97 rel(*this, !w[i] || !b[i]);
98 // If i in U, then b[i] has a piece.
99 rel(*this, b[i] == (singleton(i) <= U));
100 }
101
102 // Connect optimization variable to number of pieces
103 linear(*this, w, IRT_EQ, q);
104 linear(*this, b, IRT_GQ, q);
105
106 // Connect cardinality of U to the number of black pieces.
107 IntVar unknowns = expr(*this, cardinality(U));
108 rel(*this, q <= unknowns);
109 linear(*this, b, IRT_EQ, unknowns);
110
111 if (opt.branching() == BRANCH_NAIVE) {
112 branch(*this, w, BOOL_VAR_NONE(), BOOL_VAL_MAX());
113 branch(*this, b, BOOL_VAR_NONE(), BOOL_VAL_MAX());
114 } else {
115 QueenBranch::post(*this);
116 assign(*this, b, BOOL_ASSIGN_MAX());
117 }
118 }
121 : IntMaximizeScript(s), n(s.n) {
122 U.update(*this, s.U);
123 W.update(*this, s.W);
124 w.update(*this, s.w);
125 b.update(*this, s.b);
126 q.update(*this, s.q);
127 }
129 virtual Space*
130 copy(void) {
131 return new QueenArmies(*this);
132 }
134 virtual IntVar cost(void) const {
135 return q;
136 }
138 virtual void
139 print(std::ostream& os) const {
140 os << '\t';
141 for (int i = 0; i < n*n; ++i) {
142 if (w[i].assigned() && w[i].val()) os << "W";
143 else if (b[i].assigned() && b[i].val()) os << "B";
144 else if (!w[i].assigned() && !b[i].assigned()) os << " ";
145 else os << ".";
146 if ((i+1)%n == 0) os << std::endl << (i!=(n*n-1)?"\t":"");
147 }
148 os << "Number of white queens: " << q << std::endl << std::endl;
149 }
150
158 class QueenBranch : public Brancher {
159 private:
161 mutable int start;
163 class Choice : public Gecode::Choice {
164 public:
166 int pos;
168 bool val;
172 Choice(const Brancher& b, int pos0, bool val0)
173 : Gecode::Choice(b,2), pos(pos0), val(val0) {}
175 virtual void archive(Archive& e) const {
177 e << pos << val;
178 }
179 };
180
182 QueenBranch(Home home)
183 : Brancher(home), start(0) {}
186 : Brancher(home, b), start(b.start) {}
187
188 public:
190 virtual bool status(const Space& home) const {
191 const QueenArmies& q = static_cast<const QueenArmies&>(home);
192 for (int i = start; i < q.n*q.n; ++i)
193 if (!q.w[i].assigned()) {
194 start = i;
195 return true;
196 }
197 // No non-assigned orders left
198 return false;
199 }
201 virtual Gecode::Choice* choice(Space& home) {
202 const QueenArmies& q = static_cast<const QueenArmies&>(home);
203 int maxsize = -1;
204 int pos = -1;
205
206 for (int i = start; i < q.n*q.n; ++i) {
207 if (q.w[i].assigned()) continue;
208 IntSetRanges ai(A[i]);
211 int size = Iter::Ranges::size(r);
212 if (size > maxsize) {
213 maxsize = size;
214 pos = i;
215 }
216 }
217
218 assert(pos != -1);
219 return new Choice(*this, pos, true);
220 }
222 virtual Choice* choice(const Space&, Archive& e) {
223 int pos, val;
224 e >> pos >> val;
225 return new Choice(*this, pos, val);
226 }
230 virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
231 unsigned int a) {
232 QueenArmies& q = static_cast<QueenArmies&>(home);
233 const Choice& c = static_cast<const Choice&>(_c);
234 bool val = (a == 0) ? c.val : !c.val;
235 return me_failed(Int::BoolView(q.w[c.pos]).eq(q, val))
236 ? ES_FAILED
237 : ES_OK;
238 }
240 virtual void print(const Space&, const Gecode::Choice& _c,
241 unsigned int a,
242 std::ostream& o) const {
243 const Choice& c = static_cast<const Choice&>(_c);
244 bool val = (a == 0) ? c.val : !c.val;
245 o << "w[" << c.pos << "] = " << val;
246 }
248 virtual Actor* copy(Space& home) {
249 return new (home) QueenBranch(home, *this);
250 }
252 static void post(QueenArmies& home) {
253 (void) new (home) QueenBranch(home);
254 }
256 virtual size_t dispose(Space&) {
257 return sizeof(*this);
258 }
259 };
260};
261
266int pos(int i, int j, int n) {
267 return i*n + j;
268}
269
273int
274main(int argc, char* argv[]) {
275 SizeOptions opt("QueenArmies");
276 opt.size(6);
277 opt.branching(QueenArmies::BRANCH_SPECIFIC);
278 opt.branching(QueenArmies::BRANCH_NAIVE, "naive");
279 opt.branching(QueenArmies::BRANCH_SPECIFIC, "specific");
280 opt.solutions(0);
281 opt.parse(argc,argv);
282
283 // Set up the A-sets
284 // A[i] will contain the values attacked by a queen at position i
285 int n = opt.size();
286 A = new IntSet[n*n];
287 int *p = new int[std::max(n*n, 25)];
288 int pn = 0;
289 for (int i = n; i--; ) {
290 for (int j = n; j--; ) {
291 int dir[][2] = {
292 { 0, 1},
293 { 1, 1},
294 { 1, 0},
295 { 0, -1},
296 {-1, -1},
297 {-1, 0},
298 { 1, -1},
299 {-1, 1}
300 };
301 p[pn++] = pos(i, j, n);
302 for (int k = 8; k--; ) {
303 for (int l = 0; l < n
304 && 0 <= (i+l*dir[k][0]) && (i+l*dir[k][0]) < n
305 && 0 <= (j+l*dir[k][1]) && (j+l*dir[k][1]) < n; ++l) {
306 p[pn++] = pos(i+l*dir[k][0], j+l*dir[k][1], n);
307 }
308 }
309
310 A[pos(i, j, n)] = IntSet(p, pn);
311
312 pn = 0;
313 }
314 }
315 delete [] p;
316
318 return 0;
319}
320
321// STATISTICS: example-any
NNF * l
Left subtree.
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Base-class for both propagators and branchers.
Definition core.hpp:628
friend class Brancher
Definition core.hpp:633
Archive representation
Definition archive.hpp:42
Boolean variable array.
Definition int.hh:808
Base-class for branchers.
Definition core.hpp:1442
friend class Choice
Definition core.hpp:1445
Choice for performing commit
Definition core.hpp:1412
virtual void archive(Archive &e) const
Archive into e.
Definition core.cpp:891
Parametric base-class for scripts.
Definition driver.hh:729
static void run(const Options &opt, Script *s=NULL)
Definition script.hpp:290
Home class for posting propagators
Definition core.hpp:856
Range iterator for integer sets.
Definition int.hh:292
Integer sets.
Definition int.hh:174
Integer variables.
Definition int.hh:371
Boolean view for Boolean variables.
Definition view.hpp:1380
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition bool.hpp:170
Range iterator for computing intersection (binary)
Iterator for the unknown ranges of a set variable.
Definition set.hh:334
Set variables
Definition set.hh:127
Options for scripts with additional size parameter
Definition driver.hh:675
Computation spaces.
Definition core.hpp:1742
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition array.hpp:1013
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition var.hpp:116
bool assigned(void) const
Test whether view is assigned.
Definition var.hpp:111
Custom brancher for Peacable queens.
virtual Gecode::Choice * choice(Space &home)
Return choice.
virtual void print(const Space &, const Gecode::Choice &_c, unsigned int a, std::ostream &o) const
Print explanation.
virtual ExecStatus commit(Space &home, const Gecode::Choice &_c, unsigned int a)
Perform commit for choice _c and alternative a.
virtual size_t dispose(Space &)
Delete brancher and return its size.
virtual bool status(const Space &home) const
Check status of brancher, return true if alternatives left.
static void post(QueenArmies &home)
Post brancher.
virtual Choice * choice(const Space &, Archive &e)
Return choice.
virtual Actor * copy(Space &home)
Copy brancher during cloning.
Example: Peaceable co-existing armies of queens
QueenArmies(const SizeOptions &opt)
Constructor.
int main(int argc, char *argv[])
Main-function.
int pos(int i, int j, int n)
Position of a piece in a square board.
virtual void print(std::ostream &os) const
Print solution.
BoolVarArray w
The placement of the white queens.
BoolVarArray b
The placement of the black queens.
@ BRANCH_NAIVE
Choose variables left to right.
@ BRANCH_SPECIFIC
Choose variable with problem specific strategy.
QueenArmies(QueenArmies &s)
Constructor for cloning.
virtual IntVar cost(void) const
Return solution cost.
IntVar q
The number of white queens placed.
SetVar W
Set of squares occupied by white queens.
virtual Space * copy(void)
Return copy during cloning.
const int n
SetVar U
Set of un-attacked squares.
IntSet * A
Position of a piece in a square board.
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
void assign(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatAssign vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Assign all x with variable selection vars and value selection vals.
Definition branch.cpp:111
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 linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition linear.cpp:41
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
@ IRT_EQ
Equality ( )
Definition int.hh:926
@ IRT_GQ
Greater or equal ( )
Definition int.hh:930
unsigned int size(I &i)
Size of all ranges of range iterator i.
Gecode toplevel namespace
BoolAssign BOOL_ASSIGN_MAX(void)
Select largest value.
Definition assign.hpp:105
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:915
BoolVarBranch BOOL_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:364
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
Definition val.hpp:135
SetExpr singleton(const LinIntExpr &)
Singleton expression.
Definition set-expr.cpp:691
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
LinIntExpr cardinality(const SetExpr &)
Cardinality of set expression.
Definition set-expr.cpp:817