61 class Bishops :
public Space {
65 bool valid_pos(
int i,
int j) {
66 return (i >= 0 && i < n) && (j >= 0 && j <
n);
69 :
n(size), k(*
this,n*n,0,1) {
71 for (
int l = n;
l--; ) {
72 const int il = (n-1) -
l;
74 for (
int i = 0; i <=
l; ++
i) {
77 d3[
i] = kb((n-1)-i-il, 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);
109 bishops.
init(size*size);
111 while (Bishops* s = e.
next()) {
112 for (
int i = size*size;
i--; )
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,
245 k = n <= nkval ?
kval[n-1] :
kval[nkval-1];
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) {
291 d3[
i] = m((n-1)-
i-il,
i);
292 d4[
i] = m((n-1)-
i,
i+il);
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--; )
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");
412 opt.
parse(argc,argv);
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);
void size(unsigned int s)
Set default size.
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
Options for scripts with additional size parameter
Example: Crowded chessboard
Slice< A > col(int c) const
Access column c.
void finalize(void)
Finalize tuple set.
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.
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
int size(void) const
Return size of array (number of elements)
void propagation(int v)
Set default propagation value.
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
CrowdedChess(CrowdedChess &e)
Constructor for cloning e.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
TupleSet bishops
Set of valid positions for the bishops.
void init_bishops(int size)
Initialize bishops.
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
IntVarArray queens
Row of queen in column x.
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
IntVarArray rooks
Row of rook in column x.
void ipl(IntPropLevel i)
Set default integer propagation level.
Parametric base-class for scripts.
void init(int a)
Initialize an uninitialized tuple set.
Gecode::FloatVal c(-8, 8)
bool valid_pos(int i, int j)
int p
Number of positive literals for node type.
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
int n
Number of negative literals for node type.
Gecode::IntArgs i({1, 2, 3, 4})
Propagate bishops placement extensionally.
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl)
Select variable with smallest min.
Propagate bishops placement with decomposition.
CrowdedChess(const SizeOptions &opt)
The model of the problem.
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntPropLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
int main(int argc, char *argv[])
Main function.
IntValBranch INT_VAL_MIN(void)
Select smallest value.
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
unsigned int size(I &i)
Size of all ranges of range iterator i.
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl)
Post propagator for for all .
Passing integer variables.
Passing integer arguments.
Passing Boolean variables.
BoolVar expr(Home home, const BoolExpr &e, IntPropLevel ipl)
Post Boolean expression and return its value.
Post propagator for SetVar SetOpType SetVar SetRelType r
Class represeting a set of tuples.
void knight_constraints(void)
Post knight-constraints.
virtual Space * copy(void)
Copy during cloning.
Post propagator for SetVar SetOpType SetVar y
BoolVarArray knights
True iff the corresponding place has a knight.
BoolVarBranch BOOL_VAR_DEGREE_MAX(BranchTbl tbl)
Select variable with largest degree.
virtual void print(std::ostream &os) const
Print solution.
Slice< A > row(int r) const
Access row r.
bool assigned(View x, int v)
Whether x is assigned to value v.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Domain propagation Options: basic versus advanced propagation.
Post propagator for SetVar x
Matrix-interface for arrays.
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
Gecode toplevel namespace
Depth-first search engine.
void element(Home home, IntSharedArray c, IntVar x0, IntVar x1, IntPropLevel)
Post domain consistent propagator for .