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,
00096 tiebreak(INT_VAR_DEGREE_MAX,INT_VAR_SIZE_MIN), INT_VAL_MAX);
00097 }
00098 Bishops(bool share, Bishops& s) : Space(share,s), n(s.n) {
00099 k.update(*this, share, s.k);
00100 }
00101 virtual Space* copy(bool share) {
00102 return new Bishops(share,*this);
00103 }
00104 };
00108 void init_bishops(int size) {
00109 Bishops* prob = new Bishops(size);
00110 DFS<Bishops> e(prob); IntArgs ia(size*size);
00111 delete prob;
00112
00113 while (Bishops* s = e.next()) {
00114 for (int i = size*size; i--; )
00115 ia[i] = s->k[i].val();
00116 bishops.add(ia);
00117 delete s;
00118 }
00119
00120 bishops.finalize();
00121 }
00122 }
00187 class CrowdedChess : public Script {
00188 protected:
00189 const int n;
00190 IntVarArray s;
00191 IntVarArray queens,
00192 rooks;
00193 BoolVarArray knights;
00194
00198 enum
00199 {Q,
00200 R,
00201 B,
00202 K,
00203 E,
00204 PMAX
00205 } piece;
00206
00207
00208 bool valid_pos(int i, int j) {
00209 return (i >= 0 && i < n) &&
00210 (j >= 0 && j < n);
00211 }
00212
00214 void knight_constraints(void) {
00215 static const int kmoves[4][2] = {
00216 {-1,2}, {1,2}, {2,-1}, {2,1}
00217 };
00218 Matrix<BoolVarArray> kb(knights, n, n);
00219 for (int x = n; x--; )
00220 for (int y = n; y--; )
00221 for (int i = 4; i--; )
00222 if (valid_pos(x+kmoves[i][0], y+kmoves[i][1]))
00223 rel(*this,
00224 kb(x, y),
00225 BOT_AND,
00226 kb(x+kmoves[i][0], y+kmoves[i][1]),
00227 0);
00228 }
00229
00230
00231 public:
00232 enum {
00233 PROP_TUPLE_SET,
00234 PROP_DECOMPOSE
00235 };
00236
00238 CrowdedChess(const SizeOptions& 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.icl());
00258 count(*this, s, Q, IRT_EQ, q, opt.icl());
00259 count(*this, s, R, IRT_EQ, r, opt.icl());
00260 count(*this, s, B, IRT_EQ, b, opt.icl());
00261 count(*this, s, K, IRT_EQ, k, opt.icl());
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.icl());
00268 count(*this, bb, Q, IRT_EQ, 1, opt.icl());
00269 count(*this, aa, R, IRT_EQ, 1, opt.icl());
00270 count(*this, bb, R, IRT_EQ, 1, opt.icl());
00271
00272
00273 element(*this, aa, queens[i], Q, ICL_DOM);
00274 element(*this, aa, rooks[i], R, ICL_DOM);
00275 }
00276
00277
00278 distinct(*this, queens, ICL_DOM);
00279 IntArgs koff(n);
00280 for (int i = n; i--; ) koff[i] = i;
00281 distinct(*this, koff, queens, ICL_DOM);
00282 for (int i = n; i--; ) koff[i] = -i;
00283 distinct(*this, koff, queens, ICL_DOM);
00284
00285
00286 distinct(*this, rooks, ICL_DOM);
00287
00288
00289 for (int l = n; l--; ) {
00290 const int il = (n-1) - l;
00291 IntVarArgs d1(l+1), d2(l+1), d3(l+1), d4(l+1);
00292 for (int i = 0; i <= l; ++i) {
00293 d1[i] = m(i+il, i);
00294 d2[i] = m(i, i+il);
00295 d3[i] = m((n-1)-i-il, i);
00296 d4[i] = m((n-1)-i, i+il);
00297 }
00298
00299 count(*this, d1, Q, IRT_LQ, 1, opt.icl());
00300 count(*this, d2, Q, IRT_LQ, 1, opt.icl());
00301 count(*this, d3, Q, IRT_LQ, 1, opt.icl());
00302 count(*this, d4, Q, IRT_LQ, 1, opt.icl());
00303 if (opt.propagation() == PROP_DECOMPOSE) {
00304 count(*this, d1, B, IRT_LQ, 1, opt.icl());
00305 count(*this, d2, B, IRT_LQ, 1, opt.icl());
00306 count(*this, d3, B, IRT_LQ, 1, opt.icl());
00307 count(*this, d4, B, IRT_LQ, 1, opt.icl());
00308 }
00309 }
00310 if (opt.propagation() == PROP_TUPLE_SET) {
00311 IntVarArgs b(s.size());
00312 for (int i = s.size(); i--; )
00313 b[i] = channel(*this, post(*this, ~(s[i] == B)));
00314 extensional(*this, b, bishops, EPK_DEF, opt.icl());
00315 }
00316
00317
00318
00319 for(int i = n*n; i--; )
00320 knights[i] = post(*this, ~(s[i] == K));
00321 knight_constraints();
00322
00323
00324
00325
00326
00327
00328
00329
00330 for (int i = n; i--; )
00331 rel(*this, queens[i], IRT_NQ, rooks[i]);
00332
00333
00334
00335 rel(*this, m(n-1, 0), IRT_EQ, B);
00336 rel(*this, m(n-1, n-1), IRT_EQ, B);
00337
00338
00339
00340
00341
00342
00343 branch(*this, s, INT_VAR_MIN_MIN, INT_VAL_MIN);
00344 }
00345
00347 CrowdedChess(bool share, CrowdedChess& e)
00348 : Script(share,e), n(e.n) {
00349 s.update(*this, share, e.s);
00350 queens.update(*this, share, e.queens);
00351 rooks.update(*this, share, e.rooks);
00352 knights.update(*this, share, e.knights);
00353 }
00354
00356 virtual Space*
00357 copy(bool share) {
00358 return new CrowdedChess(share,*this);
00359 }
00360
00362 virtual void
00363 print(std::ostream& os) const {
00364 Matrix<IntVarArray> m(s, n);
00365 char names[PMAX];
00366 names[E] = '.'; names[Q] = 'Q'; names[R] = 'R';
00367 names[B] = 'B'; names[K] = 'K';
00368 const char* sep = n < 8 ? "\t\t" : "\t";
00369
00370 for (int r = 0; r < n; ++r){
00371
00372 os << '\t';
00373 for (int c = 0; c < n; ++c) {
00374 if (m(r, c).assigned()) {
00375 os << names[m(r, c).val()];
00376 } else {
00377 os << " ";
00378 }
00379 }
00380
00381 for (int p = 0; p < PMAX; ++p) {
00382 if (p == E) continue;
00383 os << sep;
00384 for (int c = 0; c < n; ++c) {
00385 if (m(r, c).assigned()) {
00386 if (m(r, c).val() == p)
00387 os << names[p];
00388 else
00389 os << names[E];
00390 } else {
00391 os << " ";
00392 }
00393 }
00394 }
00395 os << std::endl;
00396 }
00397 os << std::endl;
00398 }
00399 };
00400
00404 int
00405 main(int argc, char* argv[]) {
00406 SizeOptions opt("CrowdedChess");
00407 opt.propagation(CrowdedChess::PROP_TUPLE_SET);
00408 opt.propagation(CrowdedChess::PROP_TUPLE_SET,
00409 "extensional",
00410 "Use extensional propagation for bishops-placement");
00411 opt.propagation(CrowdedChess::PROP_DECOMPOSE,
00412 "decompose",
00413 "Use decomposed propagation for bishops-placement");
00414 opt.icl(ICL_DOM);
00415 opt.size(8);
00416 opt.parse(argc,argv);
00417 if (opt.size() < 5) {
00418 std::cerr << "Error: size must be at least 5" << std::endl;
00419 return 1;
00420 }
00421 init_bishops(opt.size());
00422 Script::run<CrowdedChess,DFS,SizeOptions>(opt);
00423 return 0;
00424 }
00425
00426
00427