1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  *  Main authors:
4  *     Christian Schulte <schulte@gecode.org>
5  *     Mikael Lagerkvist <lagerkvist@gecode.org>
6  *
7  *  Copyright:
8  *     Christian Schulte, 2001
9  *     Mikael Lagerkvist, 2005
10  *
11  *  This file is part of Gecode, the generic constraint
12  *  development environment:
13  *     http://www.gecode.org
14  *
15  *  Permission is hereby granted, free of charge, to any person obtaining
16  *  a copy of this software and associated documentation files (the
17  *  "Software"), to deal in the Software without restriction, including
18  *  without limitation the rights to use, copy, modify, merge, publish,
19  *  distribute, sublicense, and/or sell copies of the Software, and to
20  *  permit persons to whom the Software is furnished to do so, subject to
21  *  the following conditions:
22  *
23  *  The above copyright notice and this permission notice shall be
24  *  included in all copies or substantial portions of the Software.
25  *
26  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33  *
34  */
35 
36 #include <gecode/driver.hh>
37 #include <gecode/int.hh>
38 #include <gecode/minimodel.hh>
39 
40 using namespace Gecode;
41 
42 /** The maximum number of knights placeable
43  *
44  * \relates QueensArmies
45  */
46 const int kval[] = {
47   0,   0,  0,  0,  5,
48   9,  15, 21, 29, 37,
49   47, 57, 69, 81, 94,
50   109
51 };
52 
53 namespace {
54   /** \brief Set of valid positions for the bishops
55    * \relates CrowdedChess
56    */
57   TupleSet bishops;
58   /** \brief Class for solving the bishops sub-problem
59    * \relates CrowdedChess
60    */
61   class Bishops : public Space {
62   public:
63     const int n;
64     BoolVarArray k;
valid_pos(int i,int j)65     bool valid_pos(int i, int j) {
66       return (i >= 0 && i < n) && (j >= 0 && j < n);
67     }
Bishops(int size)68     Bishops(int size)
69       : n(size), k(*this,n*n,0,1) {
70       Matrix<BoolVarArray> kb(k, n, n);
71       for (int l = n; l--; ) {
72         const int il = (n-1) - l;
73         BoolVarArgs d1(l+1), d2(l+1), d3(l+1), d4(l+1);
74         for (int i = 0; i <= l; ++i) {
75           d1[i] = kb(i+il, i);
76           d2[i] = kb(i, i+il);
77           d3[i] = kb((n-1)-i-il, i);
78           d4[i] = kb((n-1)-i, i+il);
79         }
80 
81         linear(*this, d1, IRT_LQ, 1);
82         linear(*this, d2, IRT_LQ, 1);
83         linear(*this, d3, IRT_LQ, 1);
84         linear(*this, d4, IRT_LQ, 1);
85       }
86 
87       linear(*this, k, IRT_EQ, 2*n - 2);
88       // Forced bishop placement from crowded chess model
89       rel(*this, kb(n-1,   0), IRT_EQ, 1);
90       rel(*this, kb(n-1, n-1), IRT_EQ, 1);
91       branch(*this, k, BOOL_VAR_DEGREE_MAX(), BOOL_VAL_MAX());
92     }
Bishops(Bishops & s)93     Bishops(Bishops& s) : Space(s), n(s.n) {
94       k.update(*this, s.k);
95     }
copy(void)96     virtual Space* copy(void) {
97       return new Bishops(*this);
98     }
99   };
100   /** \brief Initialize bishops
101    * \relates CrowdedChess
102    */
init_bishops(int size)103   void init_bishops(int size) {
104     Bishops* prob = new Bishops(size);
105     DFS<Bishops> e(prob);
106     IntArgs ia(size*size);
107     delete prob;
108 
109     bishops.init(size*size);
110 
111     while (Bishops* s = e.next()) {
112       for (int i = size*size; i--; )
113         ia[i] = s->k[i].val();
114       bishops.add(ia);
115       delete s;
116     }
117 
118     bishops.finalize();
119   }
120 }
121 /**
122    \brief %Example: Crowded chessboard
123 
124    You are given a chessboard together with 8 queens, 8 rooks, 14
125    bishops, and 21 knights. The puzzle is to arrange the 51 pieces on
126    the chessboard so that no queen shall attack another queen, no rook
127    attack another rook, no bishop attack another bishop, and no knight
128    attack another knight. No notice is to be taken of the intervention
129    of pieces of another type from that under consideration - that is,
130    two queens will be considered to attack one another although there
131    may be, say, a rook, a bishop, and a knight between them. It is not
132    difficult to dispose of each type of piece separately; the
133    difficulty comes in when you have to find room for all the
134    arrangements on the board simultaneously.
135    <em>Dudeney, H.E., (1917), Amusements in Mathematics,
136    Thomas Nelson and Sons.</em>
137 
138    This puzzle can be generalized to chess-boards of size \f$n\f$, where the
139    number of pieces to place are:
140      - \f$ n \f$ queens
141      - \f$ n \f$ rooks
142      - \f$ 2n-1 \f$ bishops
143      - \f$ k \f$ knights
144    where k is a number to maximize.
145 
146    The maximum k for some different values of \f$ n \f$ are presented
147    below (from Jesper Hansen and Joachim Schimpf, <a
148    href="http://www.icparc.ic.ac.uk/eclipse/examples/crowded_chess.ecl.txt">
149    ECLiPSe solution</a>
150    <TABLE>
151    <TR> <TD> n </TD> <TD> k </TD> </TR>
152    <TR> <TD> 8 </TD> <TD> 21 </TD> </TR>
153    <TR> <TD> 9 </TD> <TD> 29 </TD> </TR>
154    <TR> <TD> 10 </TD> <TD> 37 </TD> </TR>
155    <TR> <TD> 11 </TD> <TD> 47 </TD> </TR>
156    <TR> <TD> 12 </TD> <TD> 57 </TD> </TR>
157    <TR> <TD> 13 </TD> <TD> 69 </TD> </TR>
158    <TR> <TD> 14 </TD> <TD> 81 </TD> </TR>
159    <TR> <TD> 15 </TD> <TD> 94 </TD> </TR>
160    <TR> <TD> 16 </TD> <TD> 109 </TD> </TR>
161    </TABLE>
162 
163    A solution for n = 8 is:
164    <TABLE>
165    <TR><TD>Q</TD><TD>B</TD><TD>K</TD><TD>.</TD>
166    <TD>K</TD><TD>B</TD><TD>K</TD><TD>R</TD></TR>
167    <TR><TD>.</TD><TD>K</TD><TD>.</TD><TD>K</TD>
168    <TD>Q</TD><TD>K</TD><TD>R</TD><TD>B</TD></TR>
169    <TR><TD>B</TD><TD>.</TD><TD>K</TD><TD>R</TD>
170    <TD>K</TD><TD>.</TD><TD>K</TD><TD>Q</TD></TR>
171    <TR><TD>B</TD><TD>K</TD><TD>R</TD><TD>K</TD>
172    <TD>.</TD><TD>Q</TD><TD>.</TD><TD>B</TD></TR>
173    <TR><TD>B</TD><TD>R</TD><TD>Q</TD><TD>.</TD>
174    <TD>K</TD><TD>.</TD><TD>K</TD><TD>B</TD></TR>
175    <TR><TD>R</TD><TD>K</TD><TD>.</TD><TD>K</TD>
176    <TD>.</TD><TD>K</TD><TD>Q</TD><TD>B</TD></TR>
177    <TR><TD>B</TD><TD>Q</TD><TD>K</TD><TD>.</TD>
178    <TD>K</TD><TD>R</TD><TD>K</TD><TD>.</TD></TR>
179    <TR><TD>B</TD><TD>K</TD><TD>B</TD><TD>Q</TD>
180    <TD>R</TD><TD>K</TD><TD>B</TD><TD>B</TD></TR>
181  </TABLE>
182 
183    \ingroup Example
184 */
185 class CrowdedChess : public Script {
186 protected:
187   const int n;          ///< Board-size
188   IntVarArray s;        ///< The board
189   IntVarArray queens,   ///< Row of queen in column x
190     rooks;              ///< Row of rook in column x
191   BoolVarArray knights; ///< True iff the corresponding place has a knight
192 
193   /** Symbolic names of pieces. The order determines which piece will
194    * be placed first.
195    */
196   enum
197     {Q,   ///< Queen
198      R,   ///< Rook
199      B,   ///< Bishop
200      K,   ///< Knight
201      E,   ///< Empty square
202      PMAX ///< Number of pieces (including empty squares)
203     } piece;
204 
205   // Is (i,j) a valid position on the board?
valid_pos(int i,int j)206   bool valid_pos(int i, int j) {
207     return (i >= 0 && i < n) &&
208       (j >= 0 && j < n);
209   }
210 
211   /// Post knight-constraints
knight_constraints(void)212   void knight_constraints(void) {
213     static const int kmoves[4][2] = {
214       {-1,2}, {1,2}, {2,-1}, {2,1}
215     };
216     Matrix<BoolVarArray> kb(knights, n, n);
217     for (int x = n; x--; )
218       for (int y = n; y--; )
219         for (int i = 4; i--; )
220           if (valid_pos(x+kmoves[i][0], y+kmoves[i][1]))
221             rel(*this,
222                 kb(x, y),
223                 BOT_AND,
224                 kb(x+kmoves[i][0], y+kmoves[i][1]),
225                 0);
226   }
227 
228 
229 public:
230   enum {
231     PROP_TUPLE_SET, ///< Propagate bishops placement extensionally
232     PROP_DECOMPOSE  ///< Propagate bishops placement with decomposition
233   };
234 
235   /// The model of the problem
CrowdedChess(const SizeOptions & opt)236   CrowdedChess(const SizeOptions& opt)
237     : Script(opt),
238       n(opt.size()),
239       s(*this, n*n, 0, PMAX-1),
240       queens(*this, n, 0, n-1),
241       rooks(*this, n, 0, n-1),
242       knights(*this, n*n, 0, 1) {
243     const int nkval = sizeof(kval)/sizeof(int);
244     const int nn = n*n, q = n, r = n, b = (2*n)-2,
245       k = n <= nkval ? kval[n-1] : kval[nkval-1];
246     const int e = nn - (q + r + b + k);
247 
248     assert(nn == (e + q + r + b + k));
249 
250     Matrix<IntVarArray> m(s, n);
251 
252     // ***********************
253     // Basic model
254     // ***********************
255 
256     count(*this, s, E, IRT_EQ, e, opt.ipl());
257     count(*this, s, Q, IRT_EQ, q, opt.ipl());
258     count(*this, s, R, IRT_EQ, r, opt.ipl());
259     count(*this, s, B, IRT_EQ, b, opt.ipl());
260     count(*this, s, K, IRT_EQ, k, opt.ipl());
261 
262     // Collect rows and columns for handling rooks and queens
263     for (int i = 0; i < n; ++i) {
264       IntVarArgs aa = m.row(i), bb = m.col(i);
265 
266       count(*this, aa, Q, IRT_EQ, 1, opt.ipl());
267       count(*this, bb, Q, IRT_EQ, 1, opt.ipl());
268       count(*this, aa, R, IRT_EQ, 1, opt.ipl());
269       count(*this, bb, R, IRT_EQ, 1, opt.ipl());
270 
271       // Connect (queens|rooks)[i] to the row it is in
272       element(*this, aa, queens[i], Q, IPL_DOM);
273       element(*this, aa,  rooks[i], R, IPL_DOM);
274     }
275 
276     // N-queens constraints
277     distinct(*this, queens, IPL_DOM);
278     distinct(*this, IntArgs::create(n,0,1), queens, IPL_DOM);
279     distinct(*this, IntArgs::create(n,0,-1), queens, IPL_DOM);
280 
281     // N-rooks constraints
282     distinct(*this,  rooks, IPL_DOM);
283 
284     // Collect diagonals for handling queens and bishops
285     for (int l = n; l--; ) {
286       const int il = (n-1) - l;
287       IntVarArgs d1(l+1), d2(l+1), d3(l+1), d4(l+1);
288       for (int i = 0; i <= l; ++i) {
289         d1[i] = m(i+il, i);
290         d2[i] = m(i, i+il);
291         d3[i] = m((n-1)-i-il, i);
292         d4[i] = m((n-1)-i, i+il);
293       }
294 
295       count(*this, d1, Q, IRT_LQ, 1, opt.ipl());
296       count(*this, d2, Q, IRT_LQ, 1, opt.ipl());
297       count(*this, d3, Q, IRT_LQ, 1, opt.ipl());
298       count(*this, d4, Q, IRT_LQ, 1, opt.ipl());
299       if (opt.propagation() == PROP_DECOMPOSE) {
300         count(*this, d1, B, IRT_LQ, 1, opt.ipl());
301         count(*this, d2, B, IRT_LQ, 1, opt.ipl());
302         count(*this, d3, B, IRT_LQ, 1, opt.ipl());
303         count(*this, d4, B, IRT_LQ, 1, opt.ipl());
304       }
305     }
306     if (opt.propagation() == PROP_TUPLE_SET) {
307       IntVarArgs b(s.size());
308       for (int i = s.size(); i--; )
309         b[i] = channel(*this, expr(*this, (s[i] == B)));
310       extensional(*this, b, bishops, opt.ipl());
311     }
312 
313     // Handle knigths
314     // Connect knigths to board
315     for(int i = n*n; i--; )
316       knights[i] = expr(*this, (s[i] == K));
317     knight_constraints();
318 
319 
320     // ***********************
321     // Redundant constraints
322     // ***********************
323 
324     // Queens and rooks not in the same place
325     // Faster than going through the channelled board-connection
326     for (int i = n; i--; )
327       rel(*this, queens[i], IRT_NQ, rooks[i]);
328 
329     // Place bishops in two corners (from Schimpf and Hansens solution)
330     // Avoids some symmetries of the problem
331     rel(*this, m(n-1,   0), IRT_EQ, B);
332     rel(*this, m(n-1, n-1), IRT_EQ, B);
333 
334 
335     // ***********************
336     // Branching
337     // ***********************
338     // Place each piece in turn
339     branch(*this, s, INT_VAR_MIN_MIN(), INT_VAL_MIN());
340   }
341 
342   /// Constructor for cloning e
CrowdedChess(CrowdedChess & e)343   CrowdedChess(CrowdedChess& e)
344     : Script(e), n(e.n) {
345     s.update(*this, e.s);
346     queens.update(*this, e.queens);
347     rooks.update(*this, e.rooks);
348     knights.update(*this, e.knights);
349   }
350 
351   /// Copy during cloning
352   virtual Space*
copy(void)353   copy(void) {
354     return new CrowdedChess(*this);
355   }
356 
357   /// Print solution
358   virtual void
print(std::ostream & os) const359   print(std::ostream& os) const {
360     Matrix<IntVarArray> m(s, n);
361     char names[PMAX];
362     names[E] = '.'; names[Q] = 'Q'; names[R] = 'R';
363     names[B] = 'B'; names[K] = 'K';
364     const char* sep   = n < 8 ? "\t\t" : "\t";
365 
366     for (int r = 0; r < n; ++r){
367       // Print main board
368       os << '\t';
369       for (int c = 0; c < n; ++c) {
370         if (m(r, c).assigned()) {
371           os << names[m(r, c).val()];
372         } else {
373           os << " ";
374         }
375       }
376       // Print each piece on its own
377       for (int p = 0; p < PMAX; ++p) {
378         if (p == E) continue;
379         os << sep;
380         for (int c = 0; c < n; ++c) {
381           if (m(r, c).assigned()) {
382             if (m(r, c).val() == p)
383               os << names[p];
384             else
385               os << names[E];
386           } else {
387             os << " ";
388           }
389         }
390       }
391       os << std::endl;
392     }
393     os << std::endl;
394   }
395 };
396 
397 /** \brief Main function
398  * \relates CrowdedChess
399  */
400 int
main(int argc,char * argv[])401 main(int argc, char* argv[]) {
402   SizeOptions opt("CrowdedChess");
403   opt.propagation(CrowdedChess::PROP_TUPLE_SET);
404   opt.propagation(CrowdedChess::PROP_TUPLE_SET,
405                   "extensional",
406                   "Use extensional propagation for bishops-placement");
407   opt.propagation(CrowdedChess::PROP_DECOMPOSE,
408                   "decompose",
409                   "Use decomposed propagation for bishops-placement");
410   opt.ipl(IPL_DOM);
411   opt.size(8);
412   opt.parse(argc,argv);
413   if (opt.size() < 5) {
414     std::cerr << "Error: size must be at least 5" << std::endl;
415     return 1;
416   }
417   init_bishops(opt.size());
418   Script::run<CrowdedChess,DFS,SizeOptions>(opt);
419   return 0;
420 }
421 
422 // STATISTICS: example-any
423 
424