main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Oct 22 2013 00:48:58 for Gecode by
doxygen
1.8.4
examples
crowded-chess.cpp
Go to the documentation of this file.
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
* Last modified:
12
* $Date: 2013-07-08 14:22:40 +0200 (Mon, 08 Jul 2013) $ by $Author: schulte $
13
* $Revision: 13820 $
14
*
15
* This file is part of Gecode, the generic constraint
16
* development environment:
17
* http://www.gecode.org
18
*
19
* Permission is hereby granted, free of charge, to any person obtaining
20
* a copy of this software and associated documentation files (the
21
* "Software"), to deal in the Software without restriction, including
22
* without limitation the rights to use, copy, modify, merge, publish,
23
* distribute, sublicense, and/or sell copies of the Software, and to
24
* permit persons to whom the Software is furnished to do so, subject to
25
* the following conditions:
26
*
27
* The above copyright notice and this permission notice shall be
28
* included in all copies or substantial portions of the Software.
29
*
30
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37
*
38
*/
39
40
#include <
gecode/driver.hh
>
41
#include <
gecode/int.hh
>
42
#include <
gecode/minimodel.hh
>
43
44
using namespace
Gecode;
45
50
const
int
kval
[] = {
51
0, 0, 0, 0, 5,
52
9, 15, 21, 29, 37,
53
47, 57, 69, 81, 94,
54
109
55
};
56
57
namespace
{
61
TupleSet
bishops
;
65
class
Bishops :
public
Space
{
66
public
:
67
const
int
n
;
68
BoolVarArray
k;
69
bool
valid_pos(
int
i
,
int
j) {
70
return
(i >= 0 && i <
n
) && (j >= 0 && j <
n
);
71
}
72
Bishops(
int
size
)
73
:
n
(size), k(*
this
,
n
*
n
,0,1) {
74
Matrix<BoolVarArray>
kb(k, n, n);
75
for
(
int
l
= n;
l
--; ) {
76
const
int
il = (n-1) -
l
;
77
BoolVarArgs
d1
(
l
+1),
d2
(
l
+1),
d3
(
l
+1), d4(
l
+1);
78
for
(
int
i = 0; i <=
l
; ++
i
) {
79
d1
[
i
] = kb(i+il, i);
80
d2
[
i
] = kb(i, i+il);
81
d3
[
i
] = kb((n-1)-i-il, i);
82
d4[
i
] = kb((n-1)-i, i+il);
83
}
84
85
linear
(*
this
,
d1
,
IRT_LQ
, 1);
86
linear
(*
this
,
d2
,
IRT_LQ
, 1);
87
linear
(*
this
,
d3
,
IRT_LQ
, 1);
88
linear
(*
this
, d4,
IRT_LQ
, 1);
89
}
90
91
linear
(*
this
, k,
IRT_EQ
, 2*n - 2);
92
// Forced bishop placement from crowded chess model
93
rel
(*
this
, kb(n-1, 0),
IRT_EQ
, 1);
94
rel
(*
this
, kb(n-1, n-1),
IRT_EQ
, 1);
95
branch
(*
this
, k,
96
tiebreak
(
INT_VAR_DEGREE_MAX
(),
INT_VAR_SIZE_MIN
()),
INT_VAL_MAX
());
97
}
98
Bishops(
bool
share, Bishops& s) :
Space
(share,s),
n
(s.n) {
99
k.update(*
this
, share, s.k);
100
}
101
virtual
Space
* copy(
bool
share) {
102
return
new
Bishops(share,*
this
);
103
}
104
};
108
void
init_bishops
(
int
size
) {
109
Bishops* prob =
new
Bishops(size);
110
DFS<Bishops>
e(prob);
IntArgs
ia(size*size);
111
delete
prob;
112
113
while
(Bishops* s = e.
next
()) {
114
for
(
int
i
= size*size;
i
--; )
115
ia[
i
] = s->k[
i
].val();
116
bishops.
add
(ia);
117
delete
s;
118
}
119
120
bishops.
finalize
();
121
}
122
}
187
class
CrowdedChess
:
public
Script
{
188
protected
:
189
const
int
n
;
190
IntVarArray
s
;
191
IntVarArray
queens,
192
rooks
;
193
BoolVarArray
knights
;
194
198
enum
199
{
Q
,
200
R
,
201
B
,
202
K
,
203
E
,
204
PMAX
205
} piece;
206
207
// Is (i,j) a valid position on the board?
208
bool
valid_pos
(
int
i
,
int
j) {
209
return
(i >= 0 && i <
n
) &&
210
(j >= 0 && j <
n
);
211
}
212
214
void
knight_constraints
(
void
) {
215
static
const
int
kmoves[4][2] = {
216
{-1,2}, {1,2}, {2,-1}, {2,1}
217
};
218
Matrix<BoolVarArray>
kb(knights,
n
,
n
);
219
for
(
int
x
=
n
;
x
--; )
220
for
(
int
y =
n
; y--; )
221
for
(
int
i
= 4;
i
--; )
222
if
(valid_pos(
x
+kmoves[
i
][0], y+kmoves[i][1]))
223
rel
(*
this
,
224
kb(
x
, y),
225
BOT_AND
,
226
kb(
x
+kmoves[i][0], y+kmoves[i][1]),
227
0);
228
}
229
230
231
public
:
232
enum
{
233
PROP_TUPLE_SET
,
234
PROP_DECOMPOSE
235
};
236
238
CrowdedChess
(
const
SizeOptions
&
opt
)
239
:
n
(opt.
size
()),
240
s(*this,
n
*
n
, 0, PMAX-1),
241
queens(*this,
n
, 0,
n
-1),
242
rooks(*this,
n
, 0,
n
-1),
243
knights(*this,
n
*
n
, 0, 1) {
244
const
int
nkval =
sizeof
(
kval
)/
sizeof
(
int
);
245
const
int
nn =
n
*
n
, q =
n
,
r
=
n
,
b
= (2*
n
)-2,
246
k = n <= nkval ?
kval
[n-1] :
kval
[nkval-1];
247
const
int
e = nn - (q + r + b + k);
248
249
assert(nn == (e + q + r + b + k));
250
251
Matrix<IntVarArray>
m(s, n);
252
253
// ***********************
254
// Basic model
255
// ***********************
256
257
count
(*
this
, s, E,
IRT_EQ
, e, opt.
icl
());
258
count
(*
this
, s, Q,
IRT_EQ
, q, opt.
icl
());
259
count
(*
this
, s, R,
IRT_EQ
, r, opt.
icl
());
260
count
(*
this
, s, B,
IRT_EQ
, b, opt.
icl
());
261
count
(*
this
, s, K,
IRT_EQ
, k, opt.
icl
());
262
263
// Collect rows and columns for handling rooks and queens
264
for
(
int
i
= 0;
i
<
n
; ++
i
) {
265
IntVarArgs
aa = m.
row
(
i
), bb = m.
col
(
i
);
266
267
count
(*
this
, aa, Q,
IRT_EQ
, 1, opt.
icl
());
268
count
(*
this
, bb, Q,
IRT_EQ
, 1, opt.
icl
());
269
count
(*
this
, aa, R,
IRT_EQ
, 1, opt.
icl
());
270
count
(*
this
, bb, R,
IRT_EQ
, 1, opt.
icl
());
271
272
// Connect (queens|rooks)[i] to the row it is in
273
element
(*
this
, aa, queens[
i
], Q,
ICL_DOM
);
274
element
(*
this
, aa, rooks[i], R,
ICL_DOM
);
275
}
276
277
// N-queens constraints
278
distinct
(*
this
, queens,
ICL_DOM
);
279
distinct
(*
this
,
IntArgs::create
(n,0,1), queens,
ICL_DOM
);
280
distinct
(*
this
,
IntArgs::create
(n,0,-1), queens,
ICL_DOM
);
281
282
// N-rooks constraints
283
distinct
(*
this
, rooks,
ICL_DOM
);
284
285
// Collect diagonals for handling queens and bishops
286
for
(
int
l
= n;
l
--; ) {
287
const
int
il = (n-1) -
l
;
288
IntVarArgs
d1
(
l
+1),
d2
(
l
+1),
d3
(
l
+1), d4(
l
+1);
289
for
(
int
i
= 0;
i
<=
l
; ++
i
) {
290
d1
[
i
] = m(
i
+il,
i
);
291
d2
[
i
] = m(
i
,
i
+il);
292
d3
[
i
] = m((n-1)-
i
-il,
i
);
293
d4[
i
] = m((n-1)-
i
,
i
+il);
294
}
295
296
count
(*
this
,
d1
, Q,
IRT_LQ
, 1, opt.
icl
());
297
count
(*
this
,
d2
, Q,
IRT_LQ
, 1, opt.
icl
());
298
count
(*
this
,
d3
, Q,
IRT_LQ
, 1, opt.
icl
());
299
count
(*
this
, d4, Q,
IRT_LQ
, 1, opt.
icl
());
300
if
(opt.
propagation
() == PROP_DECOMPOSE) {
301
count
(*
this
,
d1
, B,
IRT_LQ
, 1, opt.
icl
());
302
count
(*
this
,
d2
, B,
IRT_LQ
, 1, opt.
icl
());
303
count
(*
this
,
d3
, B,
IRT_LQ
, 1, opt.
icl
());
304
count
(*
this
, d4, B,
IRT_LQ
, 1, opt.
icl
());
305
}
306
}
307
if
(opt.
propagation
() == PROP_TUPLE_SET) {
308
IntVarArgs
b
(s.size());
309
for
(
int
i
= s.
size
();
i
--; )
310
b[
i
] =
channel
(*
this
,
expr
(*
this
, (s[
i
] == B)));
311
extensional
(*
this
, b, bishops,
EPK_DEF
, opt.
icl
());
312
}
313
314
// Handle knigths
315
// Connect knigths to board
316
for
(
int
i
= n*n;
i
--; )
317
knights[
i
] =
expr
(*
this
, (s[
i
] == K));
318
knight_constraints();
319
320
321
// ***********************
322
// Redundant constraints
323
// ***********************
324
325
// Queens and rooks not in the same place
326
// Faster than going through the channelled board-connection
327
for
(
int
i
= n;
i
--; )
328
rel
(*
this
, queens[
i
],
IRT_NQ
, rooks[i]);
329
330
// Place bishops in two corners (from Schimpf and Hansens solution)
331
// Avoids some symmetries of the problem
332
rel
(*
this
, m(n-1, 0),
IRT_EQ
, B);
333
rel
(*
this
, m(n-1, n-1),
IRT_EQ
, B);
334
335
336
// ***********************
337
// Branching
338
// ***********************
339
// Place each piece in turn
340
branch
(*
this
, s,
INT_VAR_MIN_MIN
(),
INT_VAL_MIN
());
341
}
342
344
CrowdedChess
(
bool
share,
CrowdedChess
& e)
345
:
Script
(share,e),
n
(e.
n
) {
346
s.update(*
this
, share, e.
s
);
347
queens.update(*
this
, share, e.
queens
);
348
rooks.update(*
this
, share, e.
rooks
);
349
knights.update(*
this
, share, e.
knights
);
350
}
351
353
virtual
Space
*
354
copy
(
bool
share) {
355
return
new
CrowdedChess
(share,*
this
);
356
}
357
359
virtual
void
360
print
(std::ostream& os)
const
{
361
Matrix<IntVarArray>
m(s,
n
);
362
char
names[PMAX];
363
names[E] =
'.'
; names[Q] =
'Q'
; names[R] =
'R'
;
364
names[B] =
'B'
; names[K] =
'K'
;
365
const
char
* sep =
n
< 8 ?
"\t\t"
:
"\t"
;
366
367
for
(
int
r
= 0;
r
<
n
; ++
r
){
368
// Print main board
369
os <<
'\t'
;
370
for
(
int
c
= 0;
c
<
n
; ++
c
) {
371
if
(m(
r
,
c
).
assigned
()) {
372
os << names[m(
r
,
c
).val()];
373
}
else
{
374
os <<
" "
;
375
}
376
}
377
// Print each piece on its own
378
for
(
int
p
= 0;
p
< PMAX; ++
p
) {
379
if
(
p
== E)
continue
;
380
os << sep;
381
for
(
int
c
= 0;
c
<
n
; ++
c
) {
382
if
(m(
r
,
c
).
assigned
()) {
383
if
(m(
r
,
c
).val() ==
p
)
384
os << names[
p
];
385
else
386
os << names[E];
387
}
else
{
388
os <<
" "
;
389
}
390
}
391
}
392
os << std::endl;
393
}
394
os << std::endl;
395
}
396
};
397
401
int
402
main
(
int
argc,
char
* argv[]) {
403
SizeOptions
opt
(
"CrowdedChess"
);
404
opt.
propagation
(
CrowdedChess::PROP_TUPLE_SET
);
405
opt.
propagation
(
CrowdedChess::PROP_TUPLE_SET
,
406
"extensional"
,
407
"Use extensional propagation for bishops-placement"
);
408
opt.
propagation
(
CrowdedChess::PROP_DECOMPOSE
,
409
"decompose"
,
410
"Use decomposed propagation for bishops-placement"
);
411
opt.
icl
(
ICL_DOM
);
412
opt.
size
(8);
413
opt.
parse
(argc,argv);
414
if
(opt.
size
() < 5) {
415
std::cerr <<
"Error: size must be at least 5"
<< std::endl;
416
return
1;
417
}
418
init_bishops(opt.
size
());
419
Script::run<CrowdedChess,DFS,SizeOptions>(
opt
);
420
return
0;
421
}
422
423
// STATISTICS: example-any
424