40 using namespace Gecode;
61 class Bishops :
public Space {
65 bool valid_pos(
int i,
int j) {
66 return (
i >= 0 &&
i <
n) && (j >= 0 && j <
n);
71 for (
int l =
n;
l--; ) {
72 const int il = (
n-1) -
l;
74 for (
int i = 0;
i <=
l; ++
i) {
78 d4[
i] = kb((
n-1)-
i,
i+il);
93 Bishops(Bishops& s) :
Space(s),
n(s.n) {
96 virtual Space* copy(
void) {
97 return new Bishops(*
this);
104 Bishops* prob =
new Bishops(
size);
111 while (Bishops* s = e.
next()) {
113 ia[
i] = s->k[
i].val();
207 return (
i >= 0 &&
i <
n) &&
213 static const int kmoves[4][2] = {
214 {-1,2}, {1,2}, {2,-1}, {2,1}
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]))
224 kb(
x+kmoves[
i][0],
y+kmoves[
i][1]),
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,
246 const int e = nn - (q +
r +
b + k);
248 assert(nn == (e + q +
r +
b + k));
263 for (
int i = 0;
i <
n; ++
i) {
285 for (
int l =
n;
l--; ) {
286 const int il = (
n-1) -
l;
288 for (
int i = 0;
i <=
l; ++
i) {
292 d4[
i] = m((
n-1)-
i,
i+il);
299 if (
opt.propagation() == PROP_DECOMPOSE) {
306 if (
opt.propagation() == PROP_TUPLE_SET) {
308 for (
int i = s.
size();
i--; )
315 for(
int i =
n*
n;
i--; )
316 knights[
i] =
expr(*
this, (s[
i] == K));
317 knight_constraints();
326 for (
int i =
n;
i--; )
347 rooks.update(*
this, e.
rooks);
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";
366 for (
int r = 0;
r <
n; ++
r){
369 for (
int c = 0;
c <
n; ++
c) {
371 os << names[m(
r,
c).val()];
377 for (
int p = 0;
p < PMAX; ++
p) {
378 if (
p == E)
continue;
380 for (
int c = 0;
c <
n; ++
c) {
382 if (m(
r,
c).val() ==
p)
406 "Use extensional propagation for bishops-placement");
409 "Use decomposed propagation for bishops-placement");
413 if (
opt.size() < 5) {
414 std::cerr <<
"Error: size must be at least 5" << std::endl;
417 init_bishops(
opt.size());
418 Script::run<CrowdedChess,DFS,SizeOptions>(
opt);
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
BoolVar expr(Home home, const BoolExpr &e, const IntPropLevels &ipls)
Post Boolean expression and return its value.
int n
Number of negative literals for node type.
Node * x
Pointer to corresponding Boolean expression node.
Example: Crowded chessboard
int main(int argc, char *argv[])
Main function.
void knight_constraints(void)
Post knight-constraints.
CrowdedChess(CrowdedChess &e)
Constructor for cloning e.
void init_bishops(int size)
Initialize bishops.
IntVarArray queens
Row of queen in column x.
@ PROP_DECOMPOSE
Propagate bishops placement with decomposition.
@ PROP_TUPLE_SET
Propagate bishops placement extensionally.
virtual void print(std::ostream &os) const
Print solution.
bool valid_pos(int i, int j)
CrowdedChess(const SizeOptions &opt)
The model of the problem.
IntVarArray rooks
Row of rook in column x.
TupleSet bishops
Set of valid positions for the bishops.
BoolVarArray knights
True iff the corresponding place has a knight.
virtual Space * copy(void)
Copy during cloning.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Passing Boolean variables.
Depth-first search engine.
Parametric base-class for scripts.
Passing integer arguments.
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
Passing integer variables.
Matrix-interface for arrays.
Slice< A > col(int c) const
Access column c.
Slice< A > row(int r) const
Access row r.
void propagation(int v)
Set default propagation value.
void ipl(IntPropLevel i)
Set default integer propagation level.
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Options for scripts with additional size parameter
Class represeting a set of tuples.
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
void finalize(void)
Finalize tuple set.
void init(int a)
Initialize an uninitialized tuple set.
int size(void) const
Return size of array (number of elements)
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl)
Post propagator for for all .
void element(Home home, IntSharedArray c, IntVar x0, IntVar x1, IntPropLevel)
Post domain consistent propagator for .
Post propagator for SetVar SetOpType SetVar y
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 extensional(Home home, const IntVarArgs &x, DFA dfa, IntPropLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
@ IRT_LQ
Less or equal ( )
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
IntValBranch INT_VAL_MIN(void)
Select smallest value.
BoolVarBranch BOOL_VAR_DEGREE_MAX(BranchTbl tbl)
Select variable with largest degree.
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl)
Select variable with smallest min.
bool assigned(View x, int v)
Whether x is assigned to value v.
unsigned int size(I &i)
Size of all ranges of range iterator i.
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})