Generated on Wed Jan 4 17:49:07 2006 for Gecode by doxygen 1.4.6

crowded-chess.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2001
00008  *     Mikael Lagerkvist, 2005
00009  *
00010  *  Last modified:
00011  *     $Date: 2005-11-04 22:52:06 +0100 (Fri, 04 Nov 2005) $ by $Author: schulte $
00012  *     $Revision: 2507 $
00013  *
00014  *  This file is part of Gecode, the generic constraint
00015  *  development environment:
00016  *     http://www.gecode.org
00017  *
00018  *  See the file "LICENSE" for information on usage and
00019  *  redistribution of this file, and for a
00020  *     DISCLAIMER OF ALL WARRANTIES.
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   // Is (i,j) a valid position on the board?
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     // Basic model
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     // Integer variables for use with the element constraint
00185     //IntVar queen(this, Q, Q), rook(this, R, R);
00186 
00187     // Collect rows and columns for handling rooks and queens.
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       //Connect (queens|rooks)[i] to the row it is in
00197       //element(this, aa, queens[i], queen, ICL_BND);
00198       //element(this, aa,  rooks[i],  rook, ICL_BND);
00199       connect(aa, queens[i], Q);
00200       connect(aa,  rooks[i], R);
00201     }
00202     
00203     // N-queens constraints 
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     // N-rooks constraints
00212     distinct(this,  rooks, ICL_DOM);
00213     
00214     // Collect diagonals for handling queens and bishops
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     // Handle knigths
00236     //Connect knigths to board
00237     for(int i = n*n; i--; )
00238       knights[i] = post(this, ~(s[i] == K));
00239     knight_constraints();
00240 
00241 
00242     // ***********************
00243     // Redundant constraints
00244     // ***********************
00245 
00246     // Queens and rooks not in the same place
00247     // Faster than going through the channeled board-connection
00248     for (int i = n; i--; ) {
00249       rel(this, queens[i], IRT_NQ, rooks[i]);
00250     }
00251 
00252     // Place bishops in two corners (from Schimpf and Hansens solution)
00253     // Avoids some symmetries of the problem
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     // Branchings
00260     // ***********************
00261     //First-fail for queens, with placement as far up as possible
00262     branch(this, queens, BVAR_SIZE_MIN, BVAL_MIN);
00263     //First-fail for rooks, with placement as far down as possible
00264     branch(this,  rooks, BVAR_SIZE_MIN, BVAL_MAX);
00265     //Place each piece in turn
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       // Print main board
00295       std::cout << '\t';
00296       for (int c = 0; c < n; ++c) {
00297         std::cout << names[m(r, c).val()];
00298       }
00299       // Print each piece on its own
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 // STATISTICS: example-any
00333