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 <gecode/driver.hh>
00041 #include <gecode/int.hh>
00042 #include <gecode/minimodel.hh>
00043
00044 using namespace Gecode;
00045
00050 const int kval[] = {
00051 0, 0, 0, 0, 5,
00052 9, 15, 21, 29, 37,
00053 47, 57, 69, 81, 94,
00054 109
00055 };
00056
00057 namespace {
00061 TupleSet bishops;
00065 class Bishops : public Space {
00066 public:
00067 const int n;
00068 BoolVarArray k;
00069 bool valid_pos(int i, int j) {
00070 return (i >= 0 && i < n) && (j >= 0 && j < n);
00071 }
00072 Bishops(int size)
00073 : n(size), k(*this,n*n,0,1) {
00074 Matrix<BoolVarArray> kb(k, n, n);
00075 for (int l = n; l--; ) {
00076 const int il = (n-1) - l;
00077 BoolVarArgs d1(l+1), d2(l+1), d3(l+1), d4(l+1);
00078 for (int i = 0; i <= l; ++i) {
00079 d1[i] = kb(i+il, i);
00080 d2[i] = kb(i, i+il);
00081 d3[i] = kb((n-1)-i-il, i);
00082 d4[i] = kb((n-1)-i, i+il);
00083 }
00084
00085 linear(*this, d1, IRT_LQ, 1);
00086 linear(*this, d2, IRT_LQ, 1);
00087 linear(*this, d3, IRT_LQ, 1);
00088 linear(*this, d4, IRT_LQ, 1);
00089 }
00090
00091 linear(*this, k, IRT_EQ, 2*n - 2);
00092
00093 rel(*this, kb(n-1, 0), IRT_EQ, 1);
00094 rel(*this, kb(n-1, n-1), IRT_EQ, 1);
00095 branch(*this, k, BOOL_VAR_DEGREE_MAX(), BOOL_VAL_MAX());
00096 }
00097 Bishops(bool share, Bishops& s) : Space(share,s), n(s.n) {
00098 k.update(*this, share, s.k);
00099 }
00100 virtual Space* copy(bool share) {
00101 return new Bishops(share,*this);
00102 }
00103 };
00107 void init_bishops(int size) {
00108 Bishops* prob = new Bishops(size);
00109 DFS<Bishops> e(prob); IntArgs ia(size*size);
00110 delete prob;
00111
00112 while (Bishops* s = e.next()) {
00113 for (int i = size*size; i--; )
00114 ia[i] = s->k[i].val();
00115 bishops.add(ia);
00116 delete s;
00117 }
00118
00119 bishops.finalize();
00120 }
00121 }
00186 class CrowdedChess : public Script {
00187 protected:
00188 const int n;
00189 IntVarArray s;
00190 IntVarArray queens,
00191 rooks;
00192 BoolVarArray knights;
00193
00197 enum
00198 {Q,
00199 R,
00200 B,
00201 K,
00202 E,
00203 PMAX
00204 } piece;
00205
00206
00207 bool valid_pos(int i, int j) {
00208 return (i >= 0 && i < n) &&
00209 (j >= 0 && j < n);
00210 }
00211
00213 void knight_constraints(void) {
00214 static const int kmoves[4][2] = {
00215 {-1,2}, {1,2}, {2,-1}, {2,1}
00216 };
00217 Matrix<BoolVarArray> kb(knights, n, n);
00218 for (int x = n; x--; )
00219 for (int y = n; y--; )
00220 for (int i = 4; i--; )
00221 if (valid_pos(x+kmoves[i][0], y+kmoves[i][1]))
00222 rel(*this,
00223 kb(x, y),
00224 BOT_AND,
00225 kb(x+kmoves[i][0], y+kmoves[i][1]),
00226 0);
00227 }
00228
00229
00230 public:
00231 enum {
00232 PROP_TUPLE_SET,
00233 PROP_DECOMPOSE
00234 };
00235
00237 CrowdedChess(const SizeOptions& opt)
00238 : Script(opt),
00239 n(opt.size()),
00240 s(*this, n*n, 0, PMAX-1),
00241 queens(*this, n, 0, n-1),
00242 rooks(*this, n, 0, n-1),
00243 knights(*this, n*n, 0, 1) {
00244 const int nkval = sizeof(kval)/sizeof(int);
00245 const int nn = n*n, q = n, r = n, b = (2*n)-2,
00246 k = n <= nkval ? kval[n-1] : kval[nkval-1];
00247 const int e = nn - (q + r + b + k);
00248
00249 assert(nn == (e + q + r + b + k));
00250
00251 Matrix<IntVarArray> m(s, n);
00252
00253
00254
00255
00256
00257 count(*this, s, E, IRT_EQ, e, opt.ipl());
00258 count(*this, s, Q, IRT_EQ, q, opt.ipl());
00259 count(*this, s, R, IRT_EQ, r, opt.ipl());
00260 count(*this, s, B, IRT_EQ, b, opt.ipl());
00261 count(*this, s, K, IRT_EQ, k, opt.ipl());
00262
00263
00264 for (int i = 0; i < n; ++i) {
00265 IntVarArgs aa = m.row(i), bb = m.col(i);
00266
00267 count(*this, aa, Q, IRT_EQ, 1, opt.ipl());
00268 count(*this, bb, Q, IRT_EQ, 1, opt.ipl());
00269 count(*this, aa, R, IRT_EQ, 1, opt.ipl());
00270 count(*this, bb, R, IRT_EQ, 1, opt.ipl());
00271
00272
00273 element(*this, aa, queens[i], Q, IPL_DOM);
00274 element(*this, aa, rooks[i], R, IPL_DOM);
00275 }
00276
00277
00278 distinct(*this, queens, IPL_DOM);
00279 distinct(*this, IntArgs::create(n,0,1), queens, IPL_DOM);
00280 distinct(*this, IntArgs::create(n,0,-1), queens, IPL_DOM);
00281
00282
00283 distinct(*this, rooks, IPL_DOM);
00284
00285
00286 for (int l = n; l--; ) {
00287 const int il = (n-1) - l;
00288 IntVarArgs d1(l+1), d2(l+1), d3(l+1), d4(l+1);
00289 for (int i = 0; i <= l; ++i) {
00290 d1[i] = m(i+il, i);
00291 d2[i] = m(i, i+il);
00292 d3[i] = m((n-1)-i-il, i);
00293 d4[i] = m((n-1)-i, i+il);
00294 }
00295
00296 count(*this, d1, Q, IRT_LQ, 1, opt.ipl());
00297 count(*this, d2, Q, IRT_LQ, 1, opt.ipl());
00298 count(*this, d3, Q, IRT_LQ, 1, opt.ipl());
00299 count(*this, d4, Q, IRT_LQ, 1, opt.ipl());
00300 if (opt.propagation() == PROP_DECOMPOSE) {
00301 count(*this, d1, B, IRT_LQ, 1, opt.ipl());
00302 count(*this, d2, B, IRT_LQ, 1, opt.ipl());
00303 count(*this, d3, B, IRT_LQ, 1, opt.ipl());
00304 count(*this, d4, B, IRT_LQ, 1, opt.ipl());
00305 }
00306 }
00307 if (opt.propagation() == PROP_TUPLE_SET) {
00308 IntVarArgs b(s.size());
00309 for (int i = s.size(); i--; )
00310 b[i] = channel(*this, expr(*this, (s[i] == B)));
00311 extensional(*this, b, bishops, opt.ipl());
00312 }
00313
00314
00315
00316 for(int i = n*n; i--; )
00317 knights[i] = expr(*this, (s[i] == K));
00318 knight_constraints();
00319
00320
00321
00322
00323
00324
00325
00326
00327 for (int i = n; i--; )
00328 rel(*this, queens[i], IRT_NQ, rooks[i]);
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 : Script(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) const {
00361 Matrix<IntVarArray> m(s, n);
00362 char names[PMAX];
00363 names[E] = '.'; names[Q] = 'Q'; names[R] = 'R';
00364 names[B] = 'B'; names[K] = 'K';
00365 const char* sep = n < 8 ? "\t\t" : "\t";
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.ipl(IPL_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 Script::run<CrowdedChess,DFS,SizeOptions>(opt);
00420 return 0;
00421 }
00422
00423
00424