Generated on Sat Jan 12 2019 20:58:51 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  * 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 
40 using namespace Gecode;
41 
46 const int kval[] = {
47  0, 0, 0, 0, 5,
48  9, 15, 21, 29, 37,
49  47, 57, 69, 81, 94,
50  109
51 };
52 
53 namespace {
61  class Bishops : public Space {
62  public:
63  const int n;
64  BoolVarArray k;
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);
91  branch(*this, k, BOOL_VAR_DEGREE_MAX(), BOOL_VAL_MAX());
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 }
185 class CrowdedChess : public Script {
186 protected:
187  const int n;
189  IntVarArray queens,
190  rooks;
192 
196  enum
197  {Q,
198  R,
199  B,
200  K,
201  E,
202  PMAX
203  } piece;
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 
212  void knight_constraints(void) {
213  static const int kmoves[4][2] = {
214  {-1,2}, {1,2}, {2,-1}, {2,1}
215  };
216  Matrix<BoolVarArray> kb(knights, n, n);
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 
229 public:
230  enum {
232  PROP_DECOMPOSE
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 
250  Matrix<IntVarArray> m(s, n);
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));
317  knight_constraints();
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 {
360  Matrix<IntVarArray> m(s, n);
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 
400 int
401 main(int argc, char* argv[]) {
402  SizeOptions opt("CrowdedChess");
405  "extensional",
406  "Use extensional propagation for bishops-placement");
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());
418  Script::run<CrowdedChess,DFS,SizeOptions>(opt);
419  return 0;
420 }
421 
422 // STATISTICS: example-any
423 
void size(unsigned int s)
Set default size.
Definition: options.hpp:586
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
Definition: array.hpp:76
Options for scripts with additional size parameter
Definition: driver.hh:675
Example: Crowded chessboard
Slice< A > col(int c) const
Access column c.
Definition: matrix.hpp:183
void finalize(void)
Finalize tuple set.
Definition: tuple-set.hpp:155
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
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:39
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition: channel.cpp:41
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:908
void propagation(int v)
Set default propagation value.
Definition: options.hpp:203
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
Definition: count.cpp:40
const int kval[]
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:995
CrowdedChess(CrowdedChess &e)
Constructor for cloning e.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:666
TupleSet bishops
Set of valid positions for the bishops.
Less or equal ( )
Definition: int.hh:928
Conjunction.
Definition: int.hh:951
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:46
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:41
Integer variable array.
Definition: int.hh:763
IntVarArray rooks
Row of rook in column x.
void ipl(IntPropLevel i)
Set default integer propagation level.
Definition: options.hpp:216
Computation spaces.
Definition: core.hpp:1701
Parametric base-class for scripts.
Definition: driver.hh:729
void init(int a)
Initialize an uninitialized tuple set.
Definition: tuple-set.cpp:269
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:232
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
Definition: val.hpp:135
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Equality ( )
Definition: int.hh:926
Options opt
The options.
Definition: test.cpp:97
Gecode::IntSet d2(v2, 9)
Gecode::IntArgs i({1, 2, 3, 4})
Propagate bishops placement extensionally.
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl)
Select variable with smallest min.
Definition: var.hpp:186
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.
int main(int argc, char *argv[])
Main function.
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:55
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
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:46
Gecode::IntSet d3(-8, 8)
Passing integer variables.
Definition: int.hh:656
Passing integer arguments.
Definition: int.hh:628
Passing Boolean variables.
Definition: int.hh:712
BoolVar expr(Home home, const BoolExpr &e, IntPropLevel ipl)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:627
Boolean variable array.
Definition: int.hh:808
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
Class represeting a set of tuples.
Definition: int.hh:2190
void knight_constraints(void)
Post knight-constraints.
virtual Space * copy(void)
Copy during cloning.
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
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:389
virtual void print(std::ostream &os) const
Print solution.
Slice< A > row(int r) const
Access row r.
Definition: matrix.hpp:177
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
Domain propagation Options: basic versus advanced propagation.
Definition: int.hh:979
Post propagator for SetVar x
Definition: set.hh:767
Matrix-interface for arrays.
Definition: minimodel.hh:2048
IntVarArray s
The board.
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
Definition: tuple-set.hpp:142
Gecode toplevel namespace
Disequality ( )
Definition: int.hh:927
Depth-first search engine.
Definition: search.hh:1036
void element(Home home, IntSharedArray c, IntVar x0, IntVar x1, IntPropLevel)
Post domain consistent propagator for .
Definition: element.cpp:39
const int n
Board-size.