Generated on Fri Oct 19 11:24:48 2018 for Gecode by doxygen 1.6.3

crowded-chess.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Christian Schulte, 2001
00009  *     Mikael Lagerkvist, 2005
00010  *
00011  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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       // Forced bishop placement from crowded chess model
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   // Is (i,j) a valid position on the board?
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     // Basic model
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     // Collect rows and columns for handling rooks and queens
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       // Connect (queens|rooks)[i] to the row it is in
00272       element(*this, aa, queens[i], Q, IPL_DOM);
00273       element(*this, aa,  rooks[i], R, IPL_DOM);
00274     }
00275 
00276     // N-queens constraints
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     // N-rooks constraints
00282     distinct(*this,  rooks, IPL_DOM);
00283 
00284     // Collect diagonals for handling queens and bishops
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     // Handle knigths
00314     // Connect knigths to board
00315     for(int i = n*n; i--; )
00316       knights[i] = expr(*this, (s[i] == K));
00317     knight_constraints();
00318 
00319 
00320     // ***********************
00321     // Redundant constraints
00322     // ***********************
00323 
00324     // Queens and rooks not in the same place
00325     // Faster than going through the channelled board-connection
00326     for (int i = n; i--; )
00327       rel(*this, queens[i], IRT_NQ, rooks[i]);
00328 
00329     // Place bishops in two corners (from Schimpf and Hansens solution)
00330     // Avoids some symmetries of the problem
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     // Branching
00337     // ***********************
00338     // Place each piece in turn
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       // Print main board
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       // Print each piece on its own
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 // STATISTICS: example-any
00423