65 class Bishops :
public Space {
69 bool valid_pos(
int i,
int j) {
70 return (i >= 0 && i < n) && (j >= 0 && j <
n);
73 :
n(size), k(*
this,n*n,0,1) {
75 for (
int l = n;
l--; ) {
76 const int il = (n-1) -
l;
78 for (
int i = 0; i <=
l; ++
i) {
81 d3[
i] = kb((n-1)-i-il, i);
82 d4[
i] = kb((n-1)-i, i+il);
98 Bishops(
bool share, Bishops& s) :
Space(share,s),
n(s.n) {
99 k.
update(*
this, share, s.k);
101 virtual Space* copy(
bool share) {
102 return new Bishops(share,*
this);
109 Bishops* prob =
new Bishops(size);
113 while (Bishops* s = e.
next()) {
114 for (
int i = size*size;
i--; )
115 ia[
i] = s->k[
i].val();
209 return (i >= 0 && i < n) &&
215 static const int kmoves[4][2] = {
216 {-1,2}, {1,2}, {2,-1}, {2,1}
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]))
226 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,
246 k = n <= nkval ?
kval[n-1] :
kval[nkval-1];
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) {
292 d3[
i] = m((n-1)-
i-il,
i);
293 d4[
i] = m((n-1)-
i,
i+il);
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--; )
345 :
Script(share,e), n(e.n) {
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");
413 opt.
parse(argc,argv);
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);
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
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatNum c)
Post propagator for .
void finalize(void)
Finalize tuple set.
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Propagate bishops placement with decomposition.
void propagation(int v)
Set default propagation value.
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.
IntVarArray queens
Row of queen in column x.
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl)
Select variable with smallest domain size.
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl)
Select variable with smallest min.
IntVarArray rooks
Row of rook in column x.
Parametric base-class for scripts.
Propagate bishops placement extensionally.
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Gecode::FloatVal c(-8, 8)
bool valid_pos(int i, int j)
virtual Space * copy(bool share)
Copy during cloning.
int p
Number of positive literals for node type.
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
IntVarBranch INT_VAR_DEGREE_MAX(BranchTbl tbl)
Select variable with largest degree.
CrowdedChess(const SizeOptions &opt)
The model of the problem.
CrowdedChess(bool share, CrowdedChess &e)
Constructor for cloning e.
int main(int argc, char *argv[])
Main function.
IntValBranch INT_VAL_MIN(void)
Select smallest value.
unsigned int size(I &i)
Size of all ranges of range iterator i.
Slice< A > row(int r) const
Access row r.
void element(Home home, IntSharedArray c, IntVar x0, IntVar x1, IntConLevel)
Post domain consistent propagator for .
Passing integer variables.
Passing integer arguments.
Passing Boolean variables.
virtual void print(std::ostream &os) const
Print solution.
Class represeting a set of tuples.
void knight_constraints(void)
Post knight-constraints.
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntConLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
IntValBranch INT_VAL_MAX(void)
Select largest value.
BoolVar expr(Home home, const BoolExpr &e, IntConLevel icl)
Post Boolean expression and return its value.
BoolVarArray knights
True iff the corresponding place has a knight.
Node * x
Pointer to corresponding Boolean expression node.
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntConLevel)
Post propagator for .
bool assigned(View x, int v)
Whether x is assigned to value v.
T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
void distinct(Home home, const IntVarArgs &x, IntConLevel icl)
Post propagator for for all .
Matrix-interface for arrays.
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
Slice< A > col(int c) const
Access column c.
BrancherHandle 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 add(const IntArgs &tuple)
Add tuple to tuple set.
int size(void) const
Return size of array (number of elements)
void icl(IntConLevel i)
Set default integer consistency level.
Domain propagation or consistency.
Depth-first search engine.