this repo has no description
dekker.one
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
40using namespace Gecode;
41
42/** The maximum number of knights placeable
43 *
44 * \relates QueensArmies
45 */
46const int kval[] = {
47 0, 0, 0, 0, 5,
48 9, 15, 21, 29, 37,
49 47, 57, 69, 81, 94,
50 109
51};
52
53namespace {
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;
65 bool valid_pos(int i, int j) {
66 return (i >= 0 && i < n) && (j >= 0 && j < n);
67 }
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 }
93 Bishops(Bishops& s) : Space(s), n(s.n) {
94 k.update(*this, s.k);
95 }
96 virtual Space* copy(void) {
97 return new Bishops(*this);
98 }
99 };
100 /** \brief Initialize bishops
101 * \relates CrowdedChess
102 */
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*/
185class CrowdedChess : public Script {
186protected:
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?
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
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
229public:
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
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
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*
353 copy(void) {
354 return new CrowdedChess(*this);
355 }
356
357 /// Print solution
358 virtual void
359 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 */
400int
401main(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