Go to the documentation of this file.
65 class Bishops :
public Space {
69 bool valid_pos(
int i,
int j) {
70 return (
i >= 0 &&
i <
n) && (j >= 0 && j <
n);
75 for (
int l =
n;
l--; ) {
76 const int il = (
n-1) -
l;
78 for (
int i = 0;
i <=
l; ++
i) {
82 d4[
i] = kb((
n-1)-
i,
i+il);
97 Bishops(
bool share, Bishops& s) :
Space(share,s),
n(s.n) {
98 k.
update(*
this, share, s.k);
100 virtual Space* copy(
bool share) {
101 return new Bishops(share,*
this);
108 Bishops* prob =
new Bishops(
size);
112 while (Bishops* s = e.
next()) {
114 ia[
i] = s->k[
i].val();
208 return (
i >= 0 &&
i <
n) &&
214 static const int kmoves[4][2] = {
215 {-1,2}, {1,2}, {2,-1}, {2,1}
218 for (
int x =
n;
x--; )
219 for (
int y =
n;
y--; )
220 for (
int i = 4;
i--; )
221 if (valid_pos(
x+kmoves[
i][0],
y+kmoves[
i][1]))
225 kb(
x+kmoves[
i][0],
y+kmoves[
i][1]),
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,
247 const int e = nn - (q +
r +
b + k);
249 assert(nn == (e + q +
r +
b + k));
264 for (
int i = 0;
i <
n; ++
i) {
286 for (
int l =
n;
l--; ) {
287 const int il = (
n-1) -
l;
289 for (
int i = 0;
i <=
l; ++
i) {
293 d4[
i] = m((
n-1)-
i,
i+il);
300 if (
opt.propagation() == PROP_DECOMPOSE) {
307 if (
opt.propagation() == PROP_TUPLE_SET) {
309 for (
int i = s.
size();
i--; )
316 for(
int i =
n*
n;
i--; )
317 knights[
i] =
expr(*
this, (s[
i] == K));
318 knight_constraints();
327 for (
int i =
n;
i--; )
348 rooks.update(*
this, share, e.
rooks);
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";
367 for (
int r = 0;
r <
n; ++
r){
370 for (
int c = 0;
c <
n; ++
c) {
372 os << names[m(
r,
c).val()];
378 for (
int p = 0;
p < PMAX; ++
p) {
379 if (
p == E)
continue;
381 for (
int c = 0;
c <
n; ++
c) {
383 if (m(
r,
c).val() ==
p)
407 "Use extensional propagation for bishops-placement");
410 "Use decomposed propagation for bishops-placement");
414 if (
opt.size() < 5) {
415 std::cerr <<
"Error: size must be at least 5" << std::endl;
418 init_bishops(
opt.size());
419 Script::run<CrowdedChess,DFS,SizeOptions>(
opt);
Post propagator for SetVar x
Post propagator for SetVar SetOpType SetVar y
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
void propagation(int v)
Set default propagation value.
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
void knight_constraints(void)
Post knight-constraints.
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl)
Select variable with smallest min.
Passing integer variables.
BoolVar expr(Home home, const BoolExpr &e, IntPropLevel ipl)
Post Boolean expression and return its value.
void element(Home home, IntSharedArray c, IntVar x0, IntVar x1, IntPropLevel)
Post domain consistent propagator for .
unsigned int size(I &i)
Size of all ranges of range iterator i.
Slice< A > row(int r) const
Access row r.
bool assigned(View x, int v)
Whether x is assigned to value v.
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Gecode::IntArgs i(4, 1, 2, 3, 4)
void ipl(IntPropLevel i)
Set default integer propagation level.
BoolVarArray knights
True iff the corresponding place has a knight.
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Depth-first search engine.
int size(void) const
Return size of array (number of elements)
Gecode toplevel namespace
void add(const IntArgs &tuple)
Add tuple to tuple set.
@ PROP_TUPLE_SET
Propagate bishops placement extensionally.
void finalize(void)
Finalize tuple set.
Passing Boolean variables.
Parametric base-class for scripts.
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
virtual void print(std::ostream &os) const
Print solution.
BoolVarBranch BOOL_VAR_DEGREE_MAX(BranchTbl tbl)
Select variable with largest degree.
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntPropLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
Post propagator for SetVar SetOpType SetVar SetRelType r
@ IPL_DOM
Domain propagation Preferences: prefer speed or memory.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
bool valid_pos(int i, int j)
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
virtual Space * copy(bool share)
Copy during cloning.
Class represeting a set of tuples.
TupleSet bishops
Set of valid positions for the bishops.
CrowdedChess(const SizeOptions &opt)
The model of the problem.
CrowdedChess(bool share, CrowdedChess &e)
Constructor for cloning e.
Matrix-interface for arrays.
IntVarArray rooks
Row of rook in column x.
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
Slice< A > col(int c) const
Access column c.
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
IntVarArray queens
Row of queen in column x.
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl)
Post propagator for for all .
@ PROP_DECOMPOSE
Propagate bishops placement with decomposition.
Gecode::FloatVal c(-8, 8)
int n
Number of negative literals for node type.
Passing integer arguments.
Example: Crowded chessboard
int p
Number of positive literals for node type.
int main(int argc, char *argv[])
Main function.
@ IRT_LQ
Less or equal ( )
Options for scripts with additional size parameter
void init_bishops(int size)
Initialize bishops.