Generated on Sat Feb 7 2015 02:01:11 for Gecode by doxygen 1.8.9.1
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: 2013-07-08 14:22:40 +0200 (Mon, 08 Jul 2013) $ by $Author: schulte $
13  * $Revision: 13820 $
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,
97  }
98  Bishops(bool share, Bishops& s) : Space(share,s), n(s.n) {
99  k.update(*this, share, s.k);
100  }
101  virtual Space* copy(bool share) {
102  return new Bishops(share,*this);
103  }
104  };
108  void init_bishops(int size) {
109  Bishops* prob = new Bishops(size);
110  DFS<Bishops> e(prob); IntArgs ia(size*size);
111  delete prob;
112 
113  while (Bishops* s = e.next()) {
114  for (int i = size*size; i--; )
115  ia[i] = s->k[i].val();
116  bishops.add(ia);
117  delete s;
118  }
119 
120  bishops.finalize();
121  }
122 }
187 class CrowdedChess : public Script {
188 protected:
189  const int n;
191  IntVarArray queens,
192  rooks;
194 
198  enum
199  {Q,
200  R,
201  B,
202  K,
203  E,
204  PMAX
205  } piece;
206 
207  // Is (i,j) a valid position on the board?
208  bool valid_pos(int i, int j) {
209  return (i >= 0 && i < n) &&
210  (j >= 0 && j < n);
211  }
212 
214  void knight_constraints(void) {
215  static const int kmoves[4][2] = {
216  {-1,2}, {1,2}, {2,-1}, {2,1}
217  };
218  Matrix<BoolVarArray> kb(knights, n, n);
219  for (int x = n; x--; )
220  for (int y = n; y--; )
221  for (int i = 4; i--; )
222  if (valid_pos(x+kmoves[i][0], y+kmoves[i][1]))
223  rel(*this,
224  kb(x, y),
225  BOT_AND,
226  kb(x+kmoves[i][0], y+kmoves[i][1]),
227  0);
228  }
229 
230 
231 public:
232  enum {
234  PROP_DECOMPOSE
235  };
236 
239  : n(opt.size()),
240  s(*this, n*n, 0, PMAX-1),
241  queens(*this, n, 0, n-1),
242  rooks(*this, n, 0, n-1),
243  knights(*this, n*n, 0, 1) {
244  const int nkval = sizeof(kval)/sizeof(int);
245  const int nn = n*n, q = n, r = n, b = (2*n)-2,
246  k = n <= nkval ? kval[n-1] : kval[nkval-1];
247  const int e = nn - (q + r + b + k);
248 
249  assert(nn == (e + q + r + b + k));
250 
251  Matrix<IntVarArray> m(s, n);
252 
253  // ***********************
254  // Basic model
255  // ***********************
256 
257  count(*this, s, E, IRT_EQ, e, opt.icl());
258  count(*this, s, Q, IRT_EQ, q, opt.icl());
259  count(*this, s, R, IRT_EQ, r, opt.icl());
260  count(*this, s, B, IRT_EQ, b, opt.icl());
261  count(*this, s, K, IRT_EQ, k, opt.icl());
262 
263  // Collect rows and columns for handling rooks and queens
264  for (int i = 0; i < n; ++i) {
265  IntVarArgs aa = m.row(i), bb = m.col(i);
266 
267  count(*this, aa, Q, IRT_EQ, 1, opt.icl());
268  count(*this, bb, Q, IRT_EQ, 1, opt.icl());
269  count(*this, aa, R, IRT_EQ, 1, opt.icl());
270  count(*this, bb, R, IRT_EQ, 1, opt.icl());
271 
272  // Connect (queens|rooks)[i] to the row it is in
273  element(*this, aa, queens[i], Q, ICL_DOM);
274  element(*this, aa, rooks[i], R, ICL_DOM);
275  }
276 
277  // N-queens constraints
278  distinct(*this, queens, ICL_DOM);
279  distinct(*this, IntArgs::create(n,0,1), queens, ICL_DOM);
280  distinct(*this, IntArgs::create(n,0,-1), queens, ICL_DOM);
281 
282  // N-rooks constraints
283  distinct(*this, rooks, ICL_DOM);
284 
285  // Collect diagonals for handling queens and bishops
286  for (int l = n; l--; ) {
287  const int il = (n-1) - l;
288  IntVarArgs d1(l+1), d2(l+1), d3(l+1), d4(l+1);
289  for (int i = 0; i <= l; ++i) {
290  d1[i] = m(i+il, i);
291  d2[i] = m(i, i+il);
292  d3[i] = m((n-1)-i-il, i);
293  d4[i] = m((n-1)-i, i+il);
294  }
295 
296  count(*this, d1, Q, IRT_LQ, 1, opt.icl());
297  count(*this, d2, Q, IRT_LQ, 1, opt.icl());
298  count(*this, d3, Q, IRT_LQ, 1, opt.icl());
299  count(*this, d4, Q, IRT_LQ, 1, opt.icl());
300  if (opt.propagation() == PROP_DECOMPOSE) {
301  count(*this, d1, B, IRT_LQ, 1, opt.icl());
302  count(*this, d2, B, IRT_LQ, 1, opt.icl());
303  count(*this, d3, B, IRT_LQ, 1, opt.icl());
304  count(*this, d4, B, IRT_LQ, 1, opt.icl());
305  }
306  }
307  if (opt.propagation() == PROP_TUPLE_SET) {
308  IntVarArgs b(s.size());
309  for (int i = s.size(); i--; )
310  b[i] = channel(*this, expr(*this, (s[i] == B)));
311  extensional(*this, b, bishops, EPK_DEF, opt.icl());
312  }
313 
314  // Handle knigths
315  // Connect knigths to board
316  for(int i = n*n; i--; )
317  knights[i] = expr(*this, (s[i] == K));
318  knight_constraints();
319 
320 
321  // ***********************
322  // Redundant constraints
323  // ***********************
324 
325  // Queens and rooks not in the same place
326  // Faster than going through the channelled board-connection
327  for (int i = n; i--; )
328  rel(*this, queens[i], IRT_NQ, rooks[i]);
329 
330  // Place bishops in two corners (from Schimpf and Hansens solution)
331  // Avoids some symmetries of the problem
332  rel(*this, m(n-1, 0), IRT_EQ, B);
333  rel(*this, m(n-1, n-1), IRT_EQ, B);
334 
335 
336  // ***********************
337  // Branching
338  // ***********************
339  // Place each piece in turn
340  branch(*this, s, INT_VAR_MIN_MIN(), INT_VAL_MIN());
341  }
342 
344  CrowdedChess(bool share, CrowdedChess& e)
345  : Script(share,e), n(e.n) {
346  s.update(*this, share, e.s);
347  queens.update(*this, share, e.queens);
348  rooks.update(*this, share, e.rooks);
349  knights.update(*this, share, e.knights);
350  }
351 
353  virtual Space*
354  copy(bool share) {
355  return new CrowdedChess(share,*this);
356  }
357 
359  virtual void
360  print(std::ostream& os) const {
361  Matrix<IntVarArray> m(s, n);
362  char names[PMAX];
363  names[E] = '.'; names[Q] = 'Q'; names[R] = 'R';
364  names[B] = 'B'; names[K] = 'K';
365  const char* sep = n < 8 ? "\t\t" : "\t";
366 
367  for (int r = 0; r < n; ++r){
368  // Print main board
369  os << '\t';
370  for (int c = 0; c < n; ++c) {
371  if (m(r, c).assigned()) {
372  os << names[m(r, c).val()];
373  } else {
374  os << " ";
375  }
376  }
377  // Print each piece on its own
378  for (int p = 0; p < PMAX; ++p) {
379  if (p == E) continue;
380  os << sep;
381  for (int c = 0; c < n; ++c) {
382  if (m(r, c).assigned()) {
383  if (m(r, c).val() == p)
384  os << names[p];
385  else
386  os << names[E];
387  } else {
388  os << " ";
389  }
390  }
391  }
392  os << std::endl;
393  }
394  os << std::endl;
395  }
396 };
397 
401 int
402 main(int argc, char* argv[]) {
403  SizeOptions opt("CrowdedChess");
406  "extensional",
407  "Use extensional propagation for bishops-placement");
409  "decompose",
410  "Use decomposed propagation for bishops-placement");
411  opt.icl(ICL_DOM);
412  opt.size(8);
413  opt.parse(argc,argv);
414  if (opt.size() < 5) {
415  std::cerr << "Error: size must be at least 5" << std::endl;
416  return 1;
417  }
418  init_bishops(opt.size());
419  Script::run<CrowdedChess,DFS,SizeOptions>(opt);
420  return 0;
421 }
422 
423 // STATISTICS: example-any
424 
void size(unsigned int s)
Set default size.
Definition: options.hpp:467
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:567
Example: Crowded chessboard
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatNum c)
Post propagator for .
Definition: linear.cpp:45
void finalize(void)
Finalize tuple set.
Definition: tuple-set.hpp:111
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition: arithmetic.cpp:218
Propagate bishops placement with decomposition.
void propagation(int v)
Set default propagation value.
Definition: options.hpp:181
const int kval[]
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:435
TupleSet bishops
Set of valid positions for the bishops.
Less or equal ( )
Definition: int.hh:906
Make a default decision.
Definition: int.hh:1983
Conjunction.
Definition: int.hh:917
void init_bishops(int size)
Initialize bishops.
IntVarArray queens
Row of queen in column x.
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl)
Select variable with smallest domain size.
Definition: var.hpp:212
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl)
Select variable with smallest min.
Definition: var.hpp:192
Integer variable array.
Definition: int.hh:741
IntVarArray rooks
Row of rook in column x.
Computation spaces.
Definition: core.hpp:1362
Parametric base-class for scripts.
Definition: driver.hh:622
Propagate bishops placement extensionally.
Gecode::IntSet d1(v1, 7)
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1072
Gecode::FloatVal c(-8, 8)
bool valid_pos(int i, int j)
virtual Space * copy(bool share)
Copy during cloning.
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Equality ( )
Definition: int.hh:904
IntVarBranch INT_VAR_DEGREE_MAX(BranchTbl tbl)
Select variable with largest degree.
Definition: var.hpp:147
Options opt
The options.
Definition: test.cpp:101
Gecode::IntSet d2(v2, 9)
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
CrowdedChess(const SizeOptions &opt)
The model of the problem.
CrowdedChess(bool share, CrowdedChess &e)
Constructor for cloning e.
int main(int argc, char *argv[])
Main function.
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:68
unsigned int size(I &i)
Size of all ranges of range iterator i.
Gecode::IntSet d3(-8, 8)
Slice< A > row(int r) const
Access row r.
Definition: matrix.hpp:181
void element(Home home, IntSharedArray c, IntVar x0, IntVar x1, IntConLevel)
Post domain consistent propagator for .
Definition: element.cpp:43
Passing integer variables.
Definition: int.hh:636
Passing integer arguments.
Definition: int.hh:607
Passing Boolean variables.
Definition: int.hh:690
virtual void print(std::ostream &os) const
Print solution.
Boolean variable array.
Definition: int.hh:786
Class represeting a set of tuples.
Definition: int.hh:2022
void knight_constraints(void)
Post knight-constraints.
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntConLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
Definition: extensional.cpp:45
IntValBranch INT_VAL_MAX(void)
Select largest value.
Definition: val.hpp:78
BoolVar expr(Home home, const BoolExpr &e, IntConLevel icl)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:632
BoolVarArray knights
True iff the corresponding place has a knight.
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntConLevel)
Post propagator for .
Definition: count.cpp:44
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: dfs.hpp:52
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
Empty square.
void distinct(Home home, const IntVarArgs &x, IntConLevel icl)
Post propagator for for all .
Definition: distinct.cpp:47
Matrix-interface for arrays.
Definition: minimodel.hh:1924
IntVarArray s
The board.
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
Disequality ( )
Definition: int.hh:905
Slice< A > col(int c) const
Access column c.
Definition: matrix.hpp:187
BrancherHandle 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 add(const IntArgs &tuple)
Add tuple to tuple set.
Definition: tuple-set.hpp:98
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:985
void icl(IntConLevel i)
Set default integer consistency level.
Definition: options.hpp:194
Domain propagation or consistency.
Definition: int.hh:940
Depth-first search engine.
Definition: search.hh:494
const int n
Board-size.