Generated on Thu Feb 21 2013 23:11:38 for Gecode by doxygen 1.8.3.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: 2010-10-07 20:52:01 +1100 (Thu, 07 Oct 2010) $ by $Author: schulte $
13  * $Revision: 11473 $
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