Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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  * Last modified:
12  * $Date$ by $Author$
13  * $Revision$
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #include <gecode/driver.hh>
41 #include <gecode/int.hh>
42 #include <gecode/minimodel.hh>
43 
44 using namespace Gecode;
45 
50 const int kval[] = {
51  0, 0, 0, 0, 5,
52  9, 15, 21, 29, 37,
53  47, 57, 69, 81, 94,
54  109
55 };
56 
57 namespace {
65  class Bishops : public Space {
66  public:
67  const int n;
68  BoolVarArray k;
69  bool valid_pos(int i, int j) {
70  return (i >= 0 && i < n) && (j >= 0 && j < n);
71  }
72  Bishops(int size)
73  : n(size), k(*this,n*n,0,1) {
74  Matrix<BoolVarArray> kb(k, n, n);
75  for (int l = n; l--; ) {
76  const int il = (n-1) - l;
77  BoolVarArgs d1(l+1), d2(l+1), d3(l+1), d4(l+1);
78  for (int i = 0; i <= l; ++i) {
79  d1[i] = kb(i+il, i);
80  d2[i] = kb(i, i+il);
81  d3[i] = kb((n-1)-i-il, i);
82  d4[i] = kb((n-1)-i, i+il);
83  }
84 
85  linear(*this, d1, IRT_LQ, 1);
86  linear(*this, d2, IRT_LQ, 1);
87  linear(*this, d3, IRT_LQ, 1);
88  linear(*this, d4, IRT_LQ, 1);
89  }
90 
91  linear(*this, k, IRT_EQ, 2*n - 2);
92  // Forced bishop placement from crowded chess model
93  rel(*this, kb(n-1, 0), IRT_EQ, 1);
94  rel(*this, kb(n-1, n-1), IRT_EQ, 1);
95  branch(*this, k, BOOL_VAR_DEGREE_MAX(), BOOL_VAL_MAX());
96  }
97  Bishops(Bishops& s) : Space(s), n(s.n) {
98  k.update(*this, s.k);
99  }
100  virtual Space* copy(void) {
101  return new Bishops(*this);
102  }
103  };
107  void init_bishops(int size) {
108  Bishops* prob = new Bishops(size);
109  DFS<Bishops> e(prob);
110  IntArgs ia(size*size);
111  delete prob;
112 
113  bishops.init(size*size);
114 
115  while (Bishops* s = e.next()) {
116  for (int i = size*size; i--; )
117  ia[i] = s->k[i].val();
118  bishops.add(ia);
119  delete s;
120  }
121 
122  bishops.finalize();
123  }
124 }
189 class CrowdedChess : public Script {
190 protected:
191  const int n;
193  IntVarArray queens,
194  rooks;
196 
200  enum
201  {Q,
202  R,
203  B,
204  K,
205  E,
206  PMAX
207  } piece;
208 
209  // Is (i,j) a valid position on the board?
210  bool valid_pos(int i, int j) {
211  return (i >= 0 && i < n) &&
212  (j >= 0 && j < n);
213  }
214 
216  void knight_constraints(void) {
217  static const int kmoves[4][2] = {
218  {-1,2}, {1,2}, {2,-1}, {2,1}
219  };
220  Matrix<BoolVarArray> kb(knights, n, n);
221  for (int x = n; x--; )
222  for (int y = n; y--; )
223  for (int i = 4; i--; )
224  if (valid_pos(x+kmoves[i][0], y+kmoves[i][1]))
225  rel(*this,
226  kb(x, y),
227  BOT_AND,
228  kb(x+kmoves[i][0], y+kmoves[i][1]),
229  0);
230  }
231 
232 
233 public:
234  enum {
236  PROP_DECOMPOSE
237  };
238 
241  : Script(opt),
242  n(opt.size()),
243  s(*this, n*n, 0, PMAX-1),
244  queens(*this, n, 0, n-1),
245  rooks(*this, n, 0, n-1),
246  knights(*this, n*n, 0, 1) {
247  const int nkval = sizeof(kval)/sizeof(int);
248  const int nn = n*n, q = n, r = n, b = (2*n)-2,
249  k = n <= nkval ? kval[n-1] : kval[nkval-1];
250  const int e = nn - (q + r + b + k);
251 
252  assert(nn == (e + q + r + b + k));
253 
254  Matrix<IntVarArray> m(s, n);
255 
256  // ***********************
257  // Basic model
258  // ***********************
259 
260  count(*this, s, E, IRT_EQ, e, opt.ipl());
261  count(*this, s, Q, IRT_EQ, q, opt.ipl());
262  count(*this, s, R, IRT_EQ, r, opt.ipl());
263  count(*this, s, B, IRT_EQ, b, opt.ipl());
264  count(*this, s, K, IRT_EQ, k, opt.ipl());
265 
266  // Collect rows and columns for handling rooks and queens
267  for (int i = 0; i < n; ++i) {
268  IntVarArgs aa = m.row(i), bb = m.col(i);
269 
270  count(*this, aa, Q, IRT_EQ, 1, opt.ipl());
271  count(*this, bb, Q, IRT_EQ, 1, opt.ipl());
272  count(*this, aa, R, IRT_EQ, 1, opt.ipl());
273  count(*this, bb, R, IRT_EQ, 1, opt.ipl());
274 
275  // Connect (queens|rooks)[i] to the row it is in
276  element(*this, aa, queens[i], Q, IPL_DOM);
277  element(*this, aa, rooks[i], R, IPL_DOM);
278  }
279 
280  // N-queens constraints
281  distinct(*this, queens, IPL_DOM);
282  distinct(*this, IntArgs::create(n,0,1), queens, IPL_DOM);
283  distinct(*this, IntArgs::create(n,0,-1), queens, IPL_DOM);
284 
285  // N-rooks constraints
286  distinct(*this, rooks, IPL_DOM);
287 
288  // Collect diagonals for handling queens and bishops
289  for (int l = n; l--; ) {
290  const int il = (n-1) - l;
291  IntVarArgs d1(l+1), d2(l+1), d3(l+1), d4(l+1);
292  for (int i = 0; i <= l; ++i) {
293  d1[i] = m(i+il, i);
294  d2[i] = m(i, i+il);
295  d3[i] = m((n-1)-i-il, i);
296  d4[i] = m((n-1)-i, i+il);
297  }
298 
299  count(*this, d1, Q, IRT_LQ, 1, opt.ipl());
300  count(*this, d2, Q, IRT_LQ, 1, opt.ipl());
301  count(*this, d3, Q, IRT_LQ, 1, opt.ipl());
302  count(*this, d4, Q, IRT_LQ, 1, opt.ipl());
303  if (opt.propagation() == PROP_DECOMPOSE) {
304  count(*this, d1, B, IRT_LQ, 1, opt.ipl());
305  count(*this, d2, B, IRT_LQ, 1, opt.ipl());
306  count(*this, d3, B, IRT_LQ, 1, opt.ipl());
307  count(*this, d4, B, IRT_LQ, 1, opt.ipl());
308  }
309  }
310  if (opt.propagation() == PROP_TUPLE_SET) {
311  IntVarArgs b(s.size());
312  for (int i = s.size(); i--; )
313  b[i] = channel(*this, expr(*this, (s[i] == B)));
314  extensional(*this, b, bishops, opt.ipl());
315  }
316 
317  // Handle knigths
318  // Connect knigths to board
319  for(int i = n*n; i--; )
320  knights[i] = expr(*this, (s[i] == K));
321  knight_constraints();
322 
323 
324  // ***********************
325  // Redundant constraints
326  // ***********************
327 
328  // Queens and rooks not in the same place
329  // Faster than going through the channelled board-connection
330  for (int i = n; i--; )
331  rel(*this, queens[i], IRT_NQ, rooks[i]);
332 
333  // Place bishops in two corners (from Schimpf and Hansens solution)
334  // Avoids some symmetries of the problem
335  rel(*this, m(n-1, 0), IRT_EQ, B);
336  rel(*this, m(n-1, n-1), IRT_EQ, B);
337 
338 
339  // ***********************
340  // Branching
341  // ***********************
342  // Place each piece in turn
343  branch(*this, s, INT_VAR_MIN_MIN(), INT_VAL_MIN());
344  }
345 
348  : Script(e), n(e.n) {
349  s.update(*this, e.s);
350  queens.update(*this, e.queens);
351  rooks.update(*this, e.rooks);
352  knights.update(*this, e.knights);
353  }
354 
356  virtual Space*
357  copy(void) {
358  return new CrowdedChess(*this);
359  }
360 
362  virtual void
363  print(std::ostream& os) const {
364  Matrix<IntVarArray> m(s, n);
365  char names[PMAX];
366  names[E] = '.'; names[Q] = 'Q'; names[R] = 'R';
367  names[B] = 'B'; names[K] = 'K';
368  const char* sep = n < 8 ? "\t\t" : "\t";
369 
370  for (int r = 0; r < n; ++r){
371  // Print main board
372  os << '\t';
373  for (int c = 0; c < n; ++c) {
374  if (m(r, c).assigned()) {
375  os << names[m(r, c).val()];
376  } else {
377  os << " ";
378  }
379  }
380  // Print each piece on its own
381  for (int p = 0; p < PMAX; ++p) {
382  if (p == E) continue;
383  os << sep;
384  for (int c = 0; c < n; ++c) {
385  if (m(r, c).assigned()) {
386  if (m(r, c).val() == p)
387  os << names[p];
388  else
389  os << names[E];
390  } else {
391  os << " ";
392  }
393  }
394  }
395  os << std::endl;
396  }
397  os << std::endl;
398  }
399 };
400 
404 int
405 main(int argc, char* argv[]) {
406  SizeOptions opt("CrowdedChess");
409  "extensional",
410  "Use extensional propagation for bishops-placement");
412  "decompose",
413  "Use decomposed propagation for bishops-placement");
414  opt.ipl(IPL_DOM);
415  opt.size(8);
416  opt.parse(argc,argv);
417  if (opt.size() < 5) {
418  std::cerr << "Error: size must be at least 5" << std::endl;
419  return 1;
420  }
421  init_bishops(opt.size());
422  Script::run<CrowdedChess,DFS,SizeOptions>(opt);
423  return 0;
424 }
425 
426 // STATISTICS: example-any
427 
void size(unsigned int s)
Set default size.
Definition: options.hpp:590
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
Definition: array.hpp:72
Options for scripts with additional size parameter
Definition: driver.hh:679
Example: Crowded chessboard
Slice< A > col(int c) const
Access column c.
Definition: matrix.hpp:187
void finalize(void)
Finalize tuple set.
Definition: tuple-set.hpp:159
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
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.
Definition: branch.cpp:43
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition: channel.cpp:45
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:973
void propagation(int v)
Set default propagation value.
Definition: options.hpp:207
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
Definition: count.cpp:44
const int kval[]
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1060
CrowdedChess(CrowdedChess &e)
Constructor for cloning e.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:670
TupleSet bishops
Set of valid positions for the bishops.
Less or equal ( )
Definition: int.hh:907
Conjunction.
Definition: int.hh:930
void init_bishops(int size)
Initialize bishops.
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: base.hpp:50
IntVarArray queens
Row of queen in column x.
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition: linear.cpp:45
Integer variable array.
Definition: int.hh:742
IntVarArray rooks
Row of rook in column x.
void ipl(IntPropLevel i)
Set default integer propagation level.
Definition: options.hpp:220
Computation spaces.
Definition: core.hpp:1668
Parametric base-class for scripts.
Definition: driver.hh:733
void init(int a)
Initialize an uninitialized tuple set.
Definition: tuple-set.cpp:273
Gecode::IntSet d1(v1, 7)
Gecode::FloatVal c(-8, 8)
bool valid_pos(int i, int j)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
Definition: val.hpp:139
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Equality ( )
Definition: int.hh:905
Options opt
The options.
Definition: test.cpp:101
Gecode::IntSet d2(v2, 9)
Propagate bishops placement extensionally.
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl)
Select variable with smallest min.
Definition: var.hpp:190
Propagate bishops placement with decomposition.
CrowdedChess(const SizeOptions &opt)
The model of the problem.
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntPropLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
Definition: extensional.cpp:47
int main(int argc, char *argv[])
Main function.
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:59
unsigned int size(I &i)
Size of all ranges of range iterator i.
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl)
Post propagator for for all .
Definition: distinct.cpp:50
Gecode::IntSet d3(-8, 8)
Passing integer variables.
Definition: int.hh:637
Passing integer arguments.
Definition: int.hh:608
Passing Boolean variables.
Definition: int.hh:691
BoolVar expr(Home home, const BoolExpr &e, IntPropLevel ipl)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:632
Boolean variable array.
Definition: int.hh:787
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:769
Class represeting a set of tuples.
Definition: int.hh:2144
void knight_constraints(void)
Post knight-constraints.
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
virtual Space * copy(void)
Copy during cloning.
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:769
Empty square.
BoolVarArray knights
True iff the corresponding place has a knight.
BoolVarBranch BOOL_VAR_DEGREE_MAX(BranchTbl tbl)
Select variable with largest degree.
Definition: var.hpp:393
virtual void print(std::ostream &os) const
Print solution.
Slice< A > row(int r) const
Access row r.
Definition: matrix.hpp:181
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
Domain propagation Options: basic versus advanced propagation.
Definition: int.hh:958
Post propagator for SetVar x
Definition: set.hh:769
Matrix-interface for arrays.
Definition: minimodel.hh:2052
IntVarArray s
The board.
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
Definition: tuple-set.hpp:146
Gecode toplevel namespace
Disequality ( )
Definition: int.hh:906
Depth-first search engine.
Definition: search.hh:1039
void element(Home home, IntSharedArray c, IntVar x0, IntVar x1, IntPropLevel)
Post domain consistent propagator for .
Definition: element.cpp:43
const int n
Board-size.