Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
crowded-chess.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 * Mikael Lagerkvist <lagerkvist@gecode.org>
6 *
7 * Copyright:
8 * Christian Schulte, 2001
9 * Mikael Lagerkvist, 2005
10 *
11 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.org
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
36#include <gecode/driver.hh>
37#include <gecode/int.hh>
38#include <gecode/minimodel.hh>
39
40using namespace Gecode;
41
46const int kval[] = {
47 0, 0, 0, 0, 5,
48 9, 15, 21, 29, 37,
49 47, 57, 69, 81, 94,
50 109
51};
52
53namespace {
61 class Bishops : public Space {
62 public:
63 const int n;
65 bool valid_pos(int i, int j) {
66 return (i >= 0 && i < n) && (j >= 0 && j < n);
67 }
68 Bishops(int size)
69 : n(size), k(*this,n*n,0,1) {
70 Matrix<BoolVarArray> kb(k, n, n);
71 for (int l = n; l--; ) {
72 const int il = (n-1) - l;
73 BoolVarArgs d1(l+1), d2(l+1), d3(l+1), d4(l+1);
74 for (int i = 0; i <= l; ++i) {
75 d1[i] = kb(i+il, i);
76 d2[i] = kb(i, i+il);
77 d3[i] = kb((n-1)-i-il, i);
78 d4[i] = kb((n-1)-i, i+il);
79 }
80
81 linear(*this, d1, IRT_LQ, 1);
82 linear(*this, d2, IRT_LQ, 1);
83 linear(*this, d3, IRT_LQ, 1);
84 linear(*this, d4, IRT_LQ, 1);
85 }
86
87 linear(*this, k, IRT_EQ, 2*n - 2);
88 // Forced bishop placement from crowded chess model
89 rel(*this, kb(n-1, 0), IRT_EQ, 1);
90 rel(*this, kb(n-1, n-1), IRT_EQ, 1);
92 }
93 Bishops(Bishops& s) : Space(s), n(s.n) {
94 k.update(*this, s.k);
95 }
96 virtual Space* copy(void) {
97 return new Bishops(*this);
98 }
99 };
103 void init_bishops(int size) {
104 Bishops* prob = new Bishops(size);
105 DFS<Bishops> e(prob);
106 IntArgs ia(size*size);
107 delete prob;
108
109 bishops.init(size*size);
110
111 while (Bishops* s = e.next()) {
112 for (int i = size*size; i--; )
113 ia[i] = s->k[i].val();
114 bishops.add(ia);
115 delete s;
116 }
117
118 bishops.finalize();
119 }
120}
185class CrowdedChess : public Script {
186protected:
187 const int n;
192
196 enum
197 {Q,
204
205 // Is (i,j) a valid position on the board?
206 bool valid_pos(int i, int j) {
207 return (i >= 0 && i < n) &&
208 (j >= 0 && j < n);
209 }
210
213 static const int kmoves[4][2] = {
214 {-1,2}, {1,2}, {2,-1}, {2,1}
215 };
217 for (int x = n; x--; )
218 for (int y = n; y--; )
219 for (int i = 4; i--; )
220 if (valid_pos(x+kmoves[i][0], y+kmoves[i][1]))
221 rel(*this,
222 kb(x, y),
223 BOT_AND,
224 kb(x+kmoves[i][0], y+kmoves[i][1]),
225 0);
226 }
227
228
229public:
230 enum {
233 };
234
237 : Script(opt),
238 n(opt.size()),
239 s(*this, n*n, 0, PMAX-1),
240 queens(*this, n, 0, n-1),
241 rooks(*this, n, 0, n-1),
242 knights(*this, n*n, 0, 1) {
243 const int nkval = sizeof(kval)/sizeof(int);
244 const int nn = n*n, q = n, r = n, b = (2*n)-2,
245 k = n <= nkval ? kval[n-1] : kval[nkval-1];
246 const int e = nn - (q + r + b + k);
247
248 assert(nn == (e + q + r + b + k));
249
251
252 // ***********************
253 // Basic model
254 // ***********************
255
256 count(*this, s, E, IRT_EQ, e, opt.ipl());
257 count(*this, s, Q, IRT_EQ, q, opt.ipl());
258 count(*this, s, R, IRT_EQ, r, opt.ipl());
259 count(*this, s, B, IRT_EQ, b, opt.ipl());
260 count(*this, s, K, IRT_EQ, k, opt.ipl());
261
262 // Collect rows and columns for handling rooks and queens
263 for (int i = 0; i < n; ++i) {
264 IntVarArgs aa = m.row(i), bb = m.col(i);
265
266 count(*this, aa, Q, IRT_EQ, 1, opt.ipl());
267 count(*this, bb, Q, IRT_EQ, 1, opt.ipl());
268 count(*this, aa, R, IRT_EQ, 1, opt.ipl());
269 count(*this, bb, R, IRT_EQ, 1, opt.ipl());
270
271 // Connect (queens|rooks)[i] to the row it is in
272 element(*this, aa, queens[i], Q, IPL_DOM);
273 element(*this, aa, rooks[i], R, IPL_DOM);
274 }
275
276 // N-queens constraints
277 distinct(*this, queens, IPL_DOM);
278 distinct(*this, IntArgs::create(n,0,1), queens, IPL_DOM);
279 distinct(*this, IntArgs::create(n,0,-1), queens, IPL_DOM);
280
281 // N-rooks constraints
282 distinct(*this, rooks, IPL_DOM);
283
284 // Collect diagonals for handling queens and bishops
285 for (int l = n; l--; ) {
286 const int il = (n-1) - l;
287 IntVarArgs d1(l+1), d2(l+1), d3(l+1), d4(l+1);
288 for (int i = 0; i <= l; ++i) {
289 d1[i] = m(i+il, i);
290 d2[i] = m(i, i+il);
291 d3[i] = m((n-1)-i-il, i);
292 d4[i] = m((n-1)-i, i+il);
293 }
294
295 count(*this, d1, Q, IRT_LQ, 1, opt.ipl());
296 count(*this, d2, Q, IRT_LQ, 1, opt.ipl());
297 count(*this, d3, Q, IRT_LQ, 1, opt.ipl());
298 count(*this, d4, Q, IRT_LQ, 1, opt.ipl());
299 if (opt.propagation() == PROP_DECOMPOSE) {
300 count(*this, d1, B, IRT_LQ, 1, opt.ipl());
301 count(*this, d2, B, IRT_LQ, 1, opt.ipl());
302 count(*this, d3, B, IRT_LQ, 1, opt.ipl());
303 count(*this, d4, B, IRT_LQ, 1, opt.ipl());
304 }
305 }
306 if (opt.propagation() == PROP_TUPLE_SET) {
307 IntVarArgs b(s.size());
308 for (int i = s.size(); i--; )
309 b[i] = channel(*this, expr(*this, (s[i] == B)));
310 extensional(*this, b, bishops, opt.ipl());
311 }
312
313 // Handle knigths
314 // Connect knigths to board
315 for(int i = n*n; i--; )
316 knights[i] = expr(*this, (s[i] == K));
318
319
320 // ***********************
321 // Redundant constraints
322 // ***********************
323
324 // Queens and rooks not in the same place
325 // Faster than going through the channelled board-connection
326 for (int i = n; i--; )
327 rel(*this, queens[i], IRT_NQ, rooks[i]);
328
329 // Place bishops in two corners (from Schimpf and Hansens solution)
330 // Avoids some symmetries of the problem
331 rel(*this, m(n-1, 0), IRT_EQ, B);
332 rel(*this, m(n-1, n-1), IRT_EQ, B);
333
334
335 // ***********************
336 // Branching
337 // ***********************
338 // Place each piece in turn
339 branch(*this, s, INT_VAR_MIN_MIN(), INT_VAL_MIN());
340 }
341
344 : Script(e), n(e.n) {
345 s.update(*this, e.s);
346 queens.update(*this, e.queens);
347 rooks.update(*this, e.rooks);
348 knights.update(*this, e.knights);
349 }
350
352 virtual Space*
353 copy(void) {
354 return new CrowdedChess(*this);
355 }
356
358 virtual void
359 print(std::ostream& os) const {
361 char names[PMAX];
362 names[E] = '.'; names[Q] = 'Q'; names[R] = 'R';
363 names[B] = 'B'; names[K] = 'K';
364 const char* sep = n < 8 ? "\t\t" : "\t";
365
366 for (int r = 0; r < n; ++r){
367 // Print main board
368 os << '\t';
369 for (int c = 0; c < n; ++c) {
370 if (m(r, c).assigned()) {
371 os << names[m(r, c).val()];
372 } else {
373 os << " ";
374 }
375 }
376 // Print each piece on its own
377 for (int p = 0; p < PMAX; ++p) {
378 if (p == E) continue;
379 os << sep;
380 for (int c = 0; c < n; ++c) {
381 if (m(r, c).assigned()) {
382 if (m(r, c).val() == p)
383 os << names[p];
384 else
385 os << names[E];
386 } else {
387 os << " ";
388 }
389 }
390 }
391 os << std::endl;
392 }
393 os << std::endl;
394 }
395};
396
400int
401main(int argc, char* argv[]) {
402 SizeOptions opt("CrowdedChess");
403 opt.propagation(CrowdedChess::PROP_TUPLE_SET);
404 opt.propagation(CrowdedChess::PROP_TUPLE_SET,
405 "extensional",
406 "Use extensional propagation for bishops-placement");
407 opt.propagation(CrowdedChess::PROP_DECOMPOSE,
408 "decompose",
409 "Use decomposed propagation for bishops-placement");
410 opt.ipl(IPL_DOM);
411 opt.size(8);
412 opt.parse(argc,argv);
413 if (opt.size() < 5) {
414 std::cerr << "Error: size must be at least 5" << std::endl;
415 return 1;
416 }
417 init_bishops(opt.size());
419 return 0;
420}
421
422// STATISTICS: example-any
423
int main(int argc, char *argv[])
Main function.
void knight_constraints(void)
Post knight-constraints.
CrowdedChess(CrowdedChess &e)
Constructor for cloning e.
void init_bishops(int size)
Initialize bishops.
IntVarArray queens
Row of queen in column x.
enum CrowdedChess::@263340023323302220154063075062255036254004010355 piece
@ PMAX
Number of pieces (including empty squares)
@ E
Empty square.
IntVarArray s
The board.
virtual void print(std::ostream &os) const
Print solution.
@ PROP_DECOMPOSE
Propagate bishops placement with decomposition.
@ PROP_TUPLE_SET
Propagate bishops placement extensionally.
bool valid_pos(int i, int j)
CrowdedChess(const SizeOptions &opt)
The model of the problem.
IntVarArray rooks
Row of rook in column x.
TupleSet bishops
Set of valid positions for the bishops.
virtual Space * copy(void)
Copy during cloning.
BoolVarArray knights
True iff the corresponding place has a knight.
const int n
Board-size.
Passing Boolean variables.
Definition int.hh:721
Boolean variable array.
Definition int.hh:820
Depth-first search engine.
Definition search.hh:1036
static void run(const Options &opt, Script *s=NULL)
Passing integer arguments.
Definition int.hh:634
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
Definition array.hpp:76
Passing integer variables.
Definition int.hh:662
Integer variable array.
Definition int.hh:772
Matrix-interface for arrays.
Slice< A > col(int c) const
Access column c.
Definition matrix.hpp:183
Slice< A > row(int r) const
Access row r.
Definition matrix.hpp:177
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition base.hpp:46
Options for scripts with additional size parameter
Definition driver.hh:675
Computation spaces.
Definition core.hpp:1744
Class represeting a set of tuples.
Definition int.hh:2206
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition array.hpp:1019
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
const int kval[]
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition driver.hh:801
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
void extensional(Home home, const IntVarArgs &x, DFA d, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for extensional constraint described by a DFA.
@ IRT_EQ
Equality ( )
Definition int.hh:941
@ IRT_NQ
Disequality ( )
Definition int.hh:942
@ IRT_LQ
Less or equal ( )
Definition int.hh:943
@ BOT_AND
Conjunction.
Definition int.hh:966
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:994
Gecode toplevel namespace
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition channel.cpp:41
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:915
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Definition distinct.cpp:46
void element(Home home, IntSharedArray n, IntVar x0, IntVar x1, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for .
Definition element.cpp:39
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
Definition val.hpp:135
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:773
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
BoolVarBranch BOOL_VAR_DEGREE_MAX(BranchTbl tbl=nullptr)
Select variable with largest degree.
Definition var.hpp:389
Post propagator for SetVar x
Definition set.hh:773
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl=nullptr)
Select variable with smallest min.
Definition var.hpp:186