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 #include <gecode/driver.hh>
00037 #include <gecode/int.hh>
00038 #include <gecode/minimodel.hh>
00039
00040 using namespace Gecode;
00041
00046 const int kval[] = {
00047 0, 0, 0, 0, 5,
00048 9, 15, 21, 29, 37,
00049 47, 57, 69, 81, 94,
00050 109
00051 };
00052
00053 namespace {
00057 TupleSet bishops;
00061 class Bishops : public Space {
00062 public:
00063 const int n;
00064 BoolVarArray k;
00065 bool valid_pos(int i, int j) {
00066 return (i >= 0 && i < n) && (j >= 0 && j < n);
00067 }
00068 Bishops(int size)
00069 : n(size), k(*this,n*n,0,1) {
00070 Matrix<BoolVarArray> kb(k, n, n);
00071 for (int l = n; l--; ) {
00072 const int il = (n-1) - l;
00073 BoolVarArgs d1(l+1), d2(l+1), d3(l+1), d4(l+1);
00074 for (int i = 0; i <= l; ++i) {
00075 d1[i] = kb(i+il, i);
00076 d2[i] = kb(i, i+il);
00077 d3[i] = kb((n-1)-i-il, i);
00078 d4[i] = kb((n-1)-i, i+il);
00079 }
00080
00081 linear(*this, d1, IRT_LQ, 1);
00082 linear(*this, d2, IRT_LQ, 1);
00083 linear(*this, d3, IRT_LQ, 1);
00084 linear(*this, d4, IRT_LQ, 1);
00085 }
00086
00087 linear(*this, k, IRT_EQ, 2*n - 2);
00088
00089 rel(*this, kb(n-1, 0), IRT_EQ, 1);
00090 rel(*this, kb(n-1, n-1), IRT_EQ, 1);
00091 branch(*this, k, BOOL_VAR_DEGREE_MAX(), BOOL_VAL_MAX());
00092 }
00093 Bishops(Bishops& s) : Space(s), n(s.n) {
00094 k.update(*this, s.k);
00095 }
00096 virtual Space* copy(void) {
00097 return new Bishops(*this);
00098 }
00099 };
00103 void init_bishops(int size) {
00104 Bishops* prob = new Bishops(size);
00105 DFS<Bishops> e(prob);
00106 IntArgs ia(size*size);
00107 delete prob;
00108
00109 bishops.init(size*size);
00110
00111 while (Bishops* s = e.next()) {
00112 for (int i = size*size; i--; )
00113 ia[i] = s->k[i].val();
00114 bishops.add(ia);
00115 delete s;
00116 }
00117
00118 bishops.finalize();
00119 }
00120 }
00185 class CrowdedChess : public Script {
00186 protected:
00187 const int n;
00188 IntVarArray s;
00189 IntVarArray queens,
00190 rooks;
00191 BoolVarArray knights;
00192
00196 enum
00197 {Q,
00198 R,
00199 B,
00200 K,
00201 E,
00202 PMAX
00203 } piece;
00204
00205
00206 bool valid_pos(int i, int j) {
00207 return (i >= 0 && i < n) &&
00208 (j >= 0 && j < n);
00209 }
00210
00212 void knight_constraints(void) {
00213 static const int kmoves[4][2] = {
00214 {-1,2}, {1,2}, {2,-1}, {2,1}
00215 };
00216 Matrix<BoolVarArray> kb(knights, n, n);
00217 for (int x = n; x--; )
00218 for (int y = n; y--; )
00219 for (int i = 4; i--; )
00220 if (valid_pos(x+kmoves[i][0], y+kmoves[i][1]))
00221 rel(*this,
00222 kb(x, y),
00223 BOT_AND,
00224 kb(x+kmoves[i][0], y+kmoves[i][1]),
00225 0);
00226 }
00227
00228
00229 public:
00230 enum {
00231 PROP_TUPLE_SET,
00232 PROP_DECOMPOSE
00233 };
00234
00236 CrowdedChess(const SizeOptions& opt)
00237 : Script(opt),
00238 n(opt.size()),
00239 s(*this, n*n, 0, PMAX-1),
00240 queens(*this, n, 0, n-1),
00241 rooks(*this, n, 0, n-1),
00242 knights(*this, n*n, 0, 1) {
00243 const int nkval = sizeof(kval)/sizeof(int);
00244 const int nn = n*n, q = n, r = n, b = (2*n)-2,
00245 k = n <= nkval ? kval[n-1] : kval[nkval-1];
00246 const int e = nn - (q + r + b + k);
00247
00248 assert(nn == (e + q + r + b + k));
00249
00250 Matrix<IntVarArray> m(s, n);
00251
00252
00253
00254
00255
00256 count(*this, s, E, IRT_EQ, e, opt.ipl());
00257 count(*this, s, Q, IRT_EQ, q, opt.ipl());
00258 count(*this, s, R, IRT_EQ, r, opt.ipl());
00259 count(*this, s, B, IRT_EQ, b, opt.ipl());
00260 count(*this, s, K, IRT_EQ, k, opt.ipl());
00261
00262
00263 for (int i = 0; i < n; ++i) {
00264 IntVarArgs aa = m.row(i), bb = m.col(i);
00265
00266 count(*this, aa, Q, IRT_EQ, 1, opt.ipl());
00267 count(*this, bb, Q, IRT_EQ, 1, opt.ipl());
00268 count(*this, aa, R, IRT_EQ, 1, opt.ipl());
00269 count(*this, bb, R, IRT_EQ, 1, opt.ipl());
00270
00271
00272 element(*this, aa, queens[i], Q, IPL_DOM);
00273 element(*this, aa, rooks[i], R, IPL_DOM);
00274 }
00275
00276
00277 distinct(*this, queens, IPL_DOM);
00278 distinct(*this, IntArgs::create(n,0,1), queens, IPL_DOM);
00279 distinct(*this, IntArgs::create(n,0,-1), queens, IPL_DOM);
00280
00281
00282 distinct(*this, rooks, IPL_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.ipl());
00296 count(*this, d2, Q, IRT_LQ, 1, opt.ipl());
00297 count(*this, d3, Q, IRT_LQ, 1, opt.ipl());
00298 count(*this, d4, Q, IRT_LQ, 1, opt.ipl());
00299 if (opt.propagation() == PROP_DECOMPOSE) {
00300 count(*this, d1, B, IRT_LQ, 1, opt.ipl());
00301 count(*this, d2, B, IRT_LQ, 1, opt.ipl());
00302 count(*this, d3, B, IRT_LQ, 1, opt.ipl());
00303 count(*this, d4, B, IRT_LQ, 1, opt.ipl());
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, expr(*this, (s[i] == B)));
00310 extensional(*this, b, bishops, opt.ipl());
00311 }
00312
00313
00314
00315 for(int i = n*n; i--; )
00316 knights[i] = expr(*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 rel(*this, m(n-1, 0), IRT_EQ, B);
00332 rel(*this, m(n-1, n-1), IRT_EQ, B);
00333
00334
00335
00336
00337
00338
00339 branch(*this, s, INT_VAR_MIN_MIN(), INT_VAL_MIN());
00340 }
00341
00343 CrowdedChess(CrowdedChess& e)
00344 : Script(e), n(e.n) {
00345 s.update(*this, e.s);
00346 queens.update(*this, e.queens);
00347 rooks.update(*this, e.rooks);
00348 knights.update(*this, e.knights);
00349 }
00350
00352 virtual Space*
00353 copy(void) {
00354 return new CrowdedChess(*this);
00355 }
00356
00358 virtual void
00359 print(std::ostream& os) const {
00360 Matrix<IntVarArray> m(s, n);
00361 char names[PMAX];
00362 names[E] = '.'; names[Q] = 'Q'; names[R] = 'R';
00363 names[B] = 'B'; names[K] = 'K';
00364 const char* sep = n < 8 ? "\t\t" : "\t";
00365
00366 for (int r = 0; r < n; ++r){
00367
00368 os << '\t';
00369 for (int c = 0; c < n; ++c) {
00370 if (m(r, c).assigned()) {
00371 os << names[m(r, c).val()];
00372 } else {
00373 os << " ";
00374 }
00375 }
00376
00377 for (int p = 0; p < PMAX; ++p) {
00378 if (p == E) continue;
00379 os << sep;
00380 for (int c = 0; c < n; ++c) {
00381 if (m(r, c).assigned()) {
00382 if (m(r, c).val() == p)
00383 os << names[p];
00384 else
00385 os << names[E];
00386 } else {
00387 os << " ";
00388 }
00389 }
00390 }
00391 os << std::endl;
00392 }
00393 os << std::endl;
00394 }
00395 };
00396
00400 int
00401 main(int argc, char* argv[]) {
00402 SizeOptions opt("CrowdedChess");
00403 opt.propagation(CrowdedChess::PROP_TUPLE_SET);
00404 opt.propagation(CrowdedChess::PROP_TUPLE_SET,
00405 "extensional",
00406 "Use extensional propagation for bishops-placement");
00407 opt.propagation(CrowdedChess::PROP_DECOMPOSE,
00408 "decompose",
00409 "Use decomposed propagation for bishops-placement");
00410 opt.ipl(IPL_DOM);
00411 opt.size(8);
00412 opt.parse(argc,argv);
00413 if (opt.size() < 5) {
00414 std::cerr << "Error: size must be at least 5" << std::endl;
00415 return 1;
00416 }
00417 init_bishops(opt.size());
00418 Script::run<CrowdedChess,DFS,SizeOptions>(opt);
00419 return 0;
00420 }
00421
00422
00423