00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040 #include "examples/support.hh"
00041 #include "gecode/minimodel.hh"
00042
00047 const int kval[] = {
00048 0, 0, 0, 0, 5,
00049 9, 15, 21, 29, 37,
00050 47, 57, 69, 81, 94,
00051 109
00052 };
00053
00054 namespace {
00058 TupleSet bishops;
00062 class Bishops : public Space {
00063 public:
00064 const int n;
00065 BoolVarArray k;
00066 bool valid_pos(int i, int j) {
00067 return (i >= 0 && i < n) && (j >= 0 && j < n);
00068 }
00069 Bishops(int size)
00070 : n(size), k(this,n*n,0,1) {
00071 MiniModel::Matrix<BoolVarArray> kb(k, n, n);
00072 for (int l = n; l--; ) {
00073 const int il = (n-1) - l;
00074 BoolVarArgs d1(l+1), d2(l+1), d3(l+1), d4(l+1);
00075 for (int i = 0; i <= l; ++i) {
00076 d1[i] = kb(i+il, i);
00077 d2[i] = kb(i, i+il);
00078 d3[i] = kb((n-1)-i-il, i);
00079 d4[i] = kb((n-1)-i, i+il);
00080 }
00081
00082 linear(this, d1, IRT_LQ, 1);
00083 linear(this, d2, IRT_LQ, 1);
00084 linear(this, d3, IRT_LQ, 1);
00085 linear(this, d4, IRT_LQ, 1);
00086 }
00087
00088 linear(this, k, IRT_EQ, 2*n - 2);
00089
00090 rel(this, kb(n-1, 0), IRT_EQ, 1);
00091 rel(this, kb(n-1, n-1), IRT_EQ, 1);
00092 branch(this, k, INT_VAR_DEGREE_MAX, INT_VAL_MAX);
00093 }
00094 Bishops(bool share, Bishops& s) : Space(share,s), n(s.n) {
00095 k.update(this, share, s.k);
00096 }
00097 virtual Space* copy(bool share) {
00098 return new Bishops(share,*this);
00099 }
00100 };
00104 void init_bishops(int size) {
00105 Bishops* prob = new Bishops(size);
00106 DFS<Bishops> e(prob); IntArgs ia(size*size);
00107 delete prob;
00108
00109 while (Bishops* s = e.next()) {
00110 for (int i = size*size; i--; )
00111 ia[i] = s->k[i].val();
00112 bishops.add(ia);
00113 delete s;
00114 }
00115
00116 bishops.finalize();
00117 }
00118 }
00183 class CrowdedChess : public Example {
00184 protected:
00185 const int n;
00186 IntVarArray s;
00187 IntVarArray queens,
00188 rooks;
00189 BoolVarArray knights;
00190
00194 enum
00195 {Q,
00196 R,
00197 B,
00198 K,
00199 E,
00200 PMAX
00201 } piece;
00202
00203
00204 bool valid_pos(int i, int j) {
00205 return (i >= 0 && i < n) &&
00206 (j >= 0 && j < n);
00207 }
00208
00210 void knight_constraints(void) {
00211 static const int kmoves[4][2] = {
00212 {-1,2}, {1,2}, {2,-1}, {2,1}
00213 };
00214 MiniModel::Matrix<BoolVarArray> kb(knights, n, n);
00215 for (int x = n; x--; )
00216 for (int y = n; y--; )
00217 for (int i = 4; i--; )
00218 if (valid_pos(x+kmoves[i][0], y+kmoves[i][1]))
00219 rel(this,
00220 kb(x, y),
00221 BOT_AND,
00222 kb(x+kmoves[i][0], y+kmoves[i][1]),
00223 0);
00224 }
00225
00226
00227 public:
00228 enum {
00229 PROP_TUPLE_SET,
00230 PROP_DECOMPOSE
00231 };
00232
00234 CrowdedChess(const SizeOptions& opt)
00235 : n(opt.size()),
00236 s(this, n*n, 0, PMAX-1),
00237 queens(this, n, 0, n-1),
00238 rooks(this, n, 0, n-1),
00239 knights(this, n*n, 0, 1) {
00240 const int nkval = sizeof(kval)/sizeof(int);
00241 const int nn = n*n, q = n, r = n, b = (2*n)-2,
00242 k = n <= nkval ? kval[n-1] : kval[nkval-1];
00243 const int e = nn - (q + r + b + k);
00244
00245 assert(nn == (e + q + r + b + k));
00246
00247 MiniModel::Matrix<IntVarArray> m(s, n);
00248
00249
00250
00251
00252
00253 count(this, s, E, IRT_EQ, e, opt.icl());
00254 count(this, s, Q, IRT_EQ, q, opt.icl());
00255 count(this, s, R, IRT_EQ, r, opt.icl());
00256 count(this, s, B, IRT_EQ, b, opt.icl());
00257 count(this, s, K, IRT_EQ, k, opt.icl());
00258
00259
00260 for (int i = 0; i < n; ++i) {
00261 IntVarArgs aa = m.row(i), bb = m.col(i);
00262
00263 count(this, aa, Q, IRT_EQ, 1, opt.icl());
00264 count(this, bb, Q, IRT_EQ, 1, opt.icl());
00265 count(this, aa, R, IRT_EQ, 1, opt.icl());
00266 count(this, bb, R, IRT_EQ, 1, opt.icl());
00267
00268
00269 element(this, aa, queens[i], Q, ICL_DOM);
00270 element(this, aa, rooks[i], R, ICL_DOM);
00271 }
00272
00273
00274 distinct(this, queens, ICL_DOM);
00275 IntArgs koff(n);
00276 for (int i = n; i--; ) koff[i] = i;
00277 distinct(this, koff, queens, ICL_DOM);
00278 for (int i = n; i--; ) koff[i] = -i;
00279 distinct(this, koff, queens, ICL_DOM);
00280
00281
00282 distinct(this, rooks, ICL_DOM);
00283
00284
00285 for (int l = n; l--; ) {
00286 const int il = (n-1) - l;
00287 IntVarArgs d1(l+1), d2(l+1), d3(l+1), d4(l+1);
00288 for (int i = 0; i <= l; ++i) {
00289 d1[i] = m(i+il, i);
00290 d2[i] = m(i, i+il);
00291 d3[i] = m((n-1)-i-il, i);
00292 d4[i] = m((n-1)-i, i+il);
00293 }
00294
00295 count(this, d1, Q, IRT_LQ, 1, opt.icl());
00296 count(this, d2, Q, IRT_LQ, 1, opt.icl());
00297 count(this, d3, Q, IRT_LQ, 1, opt.icl());
00298 count(this, d4, Q, IRT_LQ, 1, opt.icl());
00299 if (opt.propagation() == PROP_DECOMPOSE) {
00300 count(this, d1, B, IRT_LQ, 1, opt.icl());
00301 count(this, d2, B, IRT_LQ, 1, opt.icl());
00302 count(this, d3, B, IRT_LQ, 1, opt.icl());
00303 count(this, d4, B, IRT_LQ, 1, opt.icl());
00304 }
00305 }
00306 if (opt.propagation() == PROP_TUPLE_SET) {
00307 IntVarArgs b(s.size());
00308 for (int i = s.size(); i--; )
00309 b[i] = channel(this, post(this, ~(s[i] == B)));
00310 extensional(this, b, bishops, opt.icl(), opt.pk());
00311 }
00312
00313
00314
00315 for(int i = n*n; i--; )
00316 knights[i] = post(this, ~(s[i] == K));
00317 knight_constraints();
00318
00319
00320
00321
00322
00323
00324
00325
00326 for (int i = n; i--; ) {
00327 rel(this, queens[i], IRT_NQ, rooks[i]);
00328 }
00329
00330
00331
00332 rel(this, m(n-1, 0), IRT_EQ, B);
00333 rel(this, m(n-1, n-1), IRT_EQ, B);
00334
00335
00336
00337
00338
00339
00340 branch(this, s, INT_VAR_MIN_MIN, INT_VAL_MIN);
00341 }
00342
00344 CrowdedChess(bool share, CrowdedChess& e)
00345 : Example(share,e), n(e.n) {
00346 s.update(this, share, e.s);
00347 queens.update(this, share, e.queens);
00348 rooks.update(this, share, e.rooks);
00349 knights.update(this, share, e.knights);
00350 }
00351
00353 virtual Space*
00354 copy(bool share) {
00355 return new CrowdedChess(share,*this);
00356 }
00357
00359 virtual void
00360 print(std::ostream& os) {
00361 MiniModel::Matrix<IntVarArray> m(s, n);
00362 char *names = static_cast<char*>(Memory::malloc(PMAX));
00363 const char *sep = n < 8 ? "\t\t" : "\t";
00364 names[E] = '.'; names[Q] = 'Q'; names[R] = 'R';
00365 names[B] = 'B'; names[K] = 'K';
00366
00367 for (int r = 0; r < n; ++r){
00368
00369 os << '\t';
00370 for (int c = 0; c < n; ++c) {
00371 if (m(r, c).assigned()) {
00372 os << names[m(r, c).val()];
00373 } else {
00374 os << " ";
00375 }
00376 }
00377
00378 for (int p = 0; p < PMAX; ++p) {
00379 if (p == E) continue;
00380 os << sep;
00381 for (int c = 0; c < n; ++c) {
00382 if (m(r, c).assigned()) {
00383 if (m(r, c).val() == p)
00384 os << names[p];
00385 else
00386 os << names[E];
00387 } else {
00388 os << " ";
00389 }
00390 }
00391 }
00392 os << std::endl;
00393 }
00394 os << std::endl;
00395 }
00396 };
00397
00401 int
00402 main(int argc, char* argv[]) {
00403 SizeOptions opt("CrowdedChess");
00404 opt.propagation(CrowdedChess::PROP_TUPLE_SET);
00405 opt.propagation(CrowdedChess::PROP_TUPLE_SET,
00406 "extensional",
00407 "Use extensional propagation for bishops-placement");
00408 opt.propagation(CrowdedChess::PROP_DECOMPOSE,
00409 "decompose",
00410 "Use decomposed propagation for bishops-placement");
00411 opt.icl(ICL_DOM);
00412 opt.size(8);
00413 opt.parse(argc,argv);
00414 if (opt.size() < 5) {
00415 std::cerr << "Error: size must be at least 5" << std::endl;
00416 return 1;
00417 }
00418 init_bishops(opt.size());
00419 Example::run<CrowdedChess,DFS,SizeOptions>(opt);
00420 return 0;
00421 }
00422
00423
00424