00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #include "examples/support.hh"
00025 #include "minimodel.hh"
00026
00028 const int kval[] = {
00029 0, 0, 0, 0, 5,
00030 9, 15, 21, 29, 37,
00031 47, 57, 69, 81, 94,
00032 109
00033 };
00034 const int nkval = 16;
00035
00103 class CrowdedChess : public Example {
00104 protected:
00105 const int n;
00106 IntVarArray s;
00107 IntVarArray queens,
00108 rooks;
00109 BoolVarArray knights;
00110
00114 enum
00115 {B,
00116 K,
00117 E,
00118 Q,
00119 R,
00120 PMAX
00121 } piece;
00122
00123
00124 bool valid_pos(int i, int j) {
00125 return (i >= 0 && i < n) &&
00126 (j >= 0 && j < n);
00127 }
00128
00130 void knight_constraints() {
00131 static const int kmoves[4][2] = {
00132 {-1,2}, {1,2}, {2,-1}, {2,1}
00133 };
00134 MiniModel::Matrix<BoolVarArray> kb(knights, n, n);
00135 for (int x = n; x--; )
00136 for (int y = n; y--; )
00137 for (int i = 4; i--; )
00138 if (valid_pos(x+kmoves[i][0], y+kmoves[i][1])) {
00139 IntVarArgs places(2);
00140 places[0] = kb(x, y);
00141 places[1] = kb(x+kmoves[i][0], y+kmoves[i][1]);
00142 linear(this, places, IRT_LQ, 1);
00143 }
00144 }
00145
00146
00150 void connect(IntVarArgs& e, IntVar& p, int piece) {
00151 IntArgs idx(n);
00152 BoolVarArgs b(n);
00153 for (int i = n; i--; ) {
00154 idx[i] = i;
00155 b[i] = post(this, ~(e[i] == piece));
00156 }
00157 linear(this, b, IRT_EQ, 1);
00158 linear(this, idx, b, IRT_EQ, p);
00159 }
00160
00161 public:
00163 CrowdedChess(const Options& o)
00164 : n(o.size), s(this, n*n, 0, PMAX-1), queens(this, n, 0, n-1),
00165 rooks(this, n, 0, n-1), knights(this, n*n, 0, 1) {
00166 const int nn = n*n, q = n, r = n, b = (2*n)-2,
00167 k = n <= nkval ? kval[n-1] : kval[nkval-1];
00168 const int e = nn - (q + r + b + k);
00169
00170 assert(nn == (e + q + r + b + k));
00171
00172 MiniModel::Matrix<IntVarArray> m(s, n);
00173
00174
00175
00176
00177
00178 count(this, s, E, IRT_EQ, e, o.icl);
00179 count(this, s, Q, IRT_EQ, q, o.icl);
00180 count(this, s, R, IRT_EQ, r, o.icl);
00181 count(this, s, B, IRT_EQ, b, o.icl);
00182 count(this, s, K, IRT_EQ, k, o.icl);
00183
00184
00185
00186
00187
00188 for (int i = 0; i < n; ++i) {
00189 IntVarArgs aa = m.row(i), bb = m.col(i);
00190
00191 count(this, aa, Q, IRT_EQ, 1, o.icl);
00192 count(this, bb, Q, IRT_EQ, 1, o.icl);
00193 count(this, aa, R, IRT_EQ, 1, o.icl);
00194 count(this, bb, R, IRT_EQ, 1, o.icl);
00195
00196
00197
00198
00199 connect(aa, queens[i], Q);
00200 connect(aa, rooks[i], R);
00201 }
00202
00203
00204 distinct(this, queens, ICL_DOM);
00205 IntArgs koff(n);
00206 for (int i = n; i--; ) koff[i] = i;
00207 distinct(this, koff, queens, ICL_DOM);
00208 for (int i = n; i--; ) koff[i] = -i;
00209 distinct(this, koff, queens, ICL_DOM);
00210
00211
00212 distinct(this, rooks, ICL_DOM);
00213
00214
00215 for (int l = n; l--; ) {
00216 const int il = (n-1) - l;
00217 IntVarArgs d1(l+1), d2(l+1), d3(l+1), d4(l+1);
00218 for (int i = 0; i <= l; ++i) {
00219 d1[i] = m(i+il, i);
00220 d2[i] = m(i, i+il);
00221 d3[i] = m((n-1)-i-il, i);
00222 d4[i] = m((n-1)-i, i+il);
00223 }
00224
00225 count(this, d1, Q, IRT_LQ, 1, o.icl);
00226 count(this, d2, Q, IRT_LQ, 1, o.icl);
00227 count(this, d3, Q, IRT_LQ, 1, o.icl);
00228 count(this, d4, Q, IRT_LQ, 1, o.icl);
00229 count(this, d1, B, IRT_LQ, 1, o.icl);
00230 count(this, d2, B, IRT_LQ, 1, o.icl);
00231 count(this, d3, B, IRT_LQ, 1, o.icl);
00232 count(this, d4, B, IRT_LQ, 1, o.icl);
00233 }
00234
00235
00236
00237 for(int i = n*n; i--; )
00238 knights[i] = post(this, ~(s[i] == K));
00239 knight_constraints();
00240
00241
00242
00243
00244
00245
00246
00247
00248 for (int i = n; i--; ) {
00249 rel(this, queens[i], IRT_NQ, rooks[i]);
00250 }
00251
00252
00253
00254 rel(this, m(n-1, 0), IRT_EQ, B);
00255 rel(this, m(n-1, n-1), IRT_EQ, B);
00256
00257
00258
00259
00260
00261
00262 branch(this, queens, BVAR_SIZE_MIN, BVAL_MIN);
00263
00264 branch(this, rooks, BVAR_SIZE_MIN, BVAL_MAX);
00265
00266 branch(this, s, BVAR_MIN_MIN, BVAL_MIN);
00267 }
00268
00270 CrowdedChess(bool share, CrowdedChess& e)
00271 : Example(share,e), n(e.n) {
00272 s.update(this, share, e.s);
00273 queens.update(this, share, e.queens);
00274 rooks.update(this, share, e.rooks);
00275 knights.update(this, share, e.knights);
00276 }
00277
00279 virtual Space*
00280 copy(bool share) {
00281 return new CrowdedChess(share,*this);
00282 }
00283
00285 virtual void
00286 print(void) {
00287 MiniModel::Matrix<IntVarArray> m(s, n);
00288 char *names = static_cast<char*>(Memory::malloc(PMAX));
00289 const char *sep = n < 8 ? "\t\t" : "\t";
00290 names[E] = '.'; names[Q] = 'Q'; names[R] = 'R';
00291 names[B] = 'B'; names[K] = 'K';
00292
00293 for (int r = 0; r < n; ++r){
00294
00295 std::cout << '\t';
00296 for (int c = 0; c < n; ++c) {
00297 std::cout << names[m(r, c).val()];
00298 }
00299
00300 for (int p = 0; p < PMAX; ++p) {
00301 if (p == E) continue;
00302 std::cout << sep;
00303 for (int c = 0; c < n; ++c) {
00304 if (m(r, c).val() == p) std::cout << names[p];
00305 else std::cout << names[E];
00306 }
00307 }
00308 std::cout << std::endl;
00309 }
00310 std::cout << std::endl;
00311 }
00312 };
00313
00317 int
00318 main(int argc, char** argv) {
00319 Options o("CrowdedChess");
00320 o.c_d = 2;
00321 o.icl = ICL_DOM;
00322 o.size = 7;
00323 o.parse(argc,argv);
00324 if(o.size < 5) {
00325 std::cerr << "Error: Size must be at least 5" << std::endl;
00326 return 1;
00327 }
00328 Example::run<CrowdedChess,DFS>(o);
00329 return 0;
00330 }
00331
00332
00333