queen-armies.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Mikael Lagerkvist <lagerkvist@gecode.org>
*
* Copyright:
* Mikael Lagerkvist, 2006
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/minimodel.hh>
#include <gecode/set.hh>
using namespace Gecode;
IntSet* A;
class QueenArmies : public IntMaximizeScript {
public:
const int n;
SetVar U,
W;
BoolVarArray w,
b;
IntVar q;
enum {
BRANCH_NAIVE,
BRANCH_SPECIFIC
};
QueenArmies(const SizeOptions& opt) :
IntMaximizeScript(opt),
n(opt.size()),
U(*this, IntSet::empty, IntSet(0, n*n)),
W(*this, IntSet::empty, IntSet(0, n*n)),
w(*this, n*n, 0, 1),
b(*this, n*n, 0, 1),
q(*this, 0, n*n)
{
// Basic rules of the model
for (int i = n*n; i--; ) {
// w[i] means that no blacks are allowed on A[i]
rel(*this, w[i] == (U || A[i]));
// Make sure blacks and whites are disjoint.
rel(*this, !w[i] || !b[i]);
// If i in U, then b[i] has a piece.
rel(*this, b[i] == (singleton(i) <= U));
}
// Connect optimization variable to number of pieces
linear(*this, w, IRT_EQ, q);
linear(*this, b, IRT_GQ, q);
// Connect cardinality of U to the number of black pieces.
IntVar unknowns = expr(*this, cardinality(U));
rel(*this, q <= unknowns);
linear(*this, b, IRT_EQ, unknowns);
if (opt.branching() == BRANCH_NAIVE) {
branch(*this, w, BOOL_VAR_NONE(), BOOL_VAL_MAX());
branch(*this, b, BOOL_VAR_NONE(), BOOL_VAL_MAX());
} else {
QueenBranch::post(*this);
assign(*this, b, BOOL_ASSIGN_MAX());
}
}
QueenArmies(QueenArmies& s)
: IntMaximizeScript(s), n(s.n) {
U.update(*this, s.U);
W.update(*this, s.W);
w.update(*this, s.w);
b.update(*this, s.b);
q.update(*this, s.q);
}
virtual Space*
copy(void) {
return new QueenArmies(*this);
}
virtual IntVar cost(void) const {
return q;
}
virtual void
print(std::ostream& os) const {
os << '\t';
for (int i = 0; i < n*n; ++i) {
if (w[i].assigned() && w[i].val()) os << "W";
else if (b[i].assigned() && b[i].val()) os << "B";
else if (!w[i].assigned() && !b[i].assigned()) os << " ";
else os << ".";
if ((i+1)%n == 0) os << std::endl << (i!=(n*n-1)?"\t":"");
}
os << "Number of white queens: " << q << std::endl << std::endl;
}
class QueenBranch : public Brancher {
private:
mutable int start;
class Choice : public Gecode::Choice {
public:
int pos;
bool val;
Choice(const Brancher& b, int pos0, bool val0)
: Gecode::Choice(b,2), pos(pos0), val(val0) {}
virtual void archive(Archive& e) const {
Gecode::Choice::archive(e);
e << pos << val;
}
};
QueenBranch(Home home)
: Brancher(home), start(0) {}
QueenBranch(Space& home, QueenBranch& b)
: Brancher(home, b), start(b.start) {}
public:
virtual bool status(const Space& home) const {
const QueenArmies& q = static_cast<const QueenArmies&>(home);
for (int i = start; i < q.n*q.n; ++i)
if (!q.w[i].assigned()) {
start = i;
return true;
}
// No non-assigned orders left
return false;
}
virtual Gecode::Choice* choice(Space& home) {
const QueenArmies& q = static_cast<const QueenArmies&>(home);
int maxsize = -1;
int pos = -1;
for (int i = start; i < q.n*q.n; ++i) {
if (q.w[i].assigned()) continue;
IntSetRanges ai(A[i]);
SetVarUnknownRanges qU(q.U);
Iter::Ranges::Inter<IntSetRanges, SetVarUnknownRanges> r(ai, qU);
int size = Iter::Ranges::size(r);
if (size > maxsize) {
maxsize = size;
pos = i;
}
}
assert(pos != -1);
return new Choice(*this, pos, true);
}
virtual Choice* choice(const Space&, Archive& e) {
int pos, val;
e >> pos >> val;
return new Choice(*this, pos, val);
}
virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
unsigned int a) {
QueenArmies& q = static_cast<QueenArmies&>(home);
const Choice& c = static_cast<const Choice&>(_c);
bool val = (a == 0) ? c.val : !c.val;
return me_failed(Int::BoolView(q.w[c.pos]).eq(q, val))
? ES_FAILED
: ES_OK;
}
virtual void print(const Space&, const Gecode::Choice& _c,
unsigned int a,
std::ostream& o) const {
const Choice& c = static_cast<const Choice&>(_c);
bool val = (a == 0) ? c.val : !c.val;
o << "w[" << c.pos << "] = " << val;
}
virtual Actor* copy(Space& home) {
return new (home) QueenBranch(home, *this);
}
static void post(QueenArmies& home) {
(void) new (home) QueenBranch(home);
}
virtual size_t dispose(Space&) {
return sizeof(*this);
}
};
};
int pos(int i, int j, int n) {
return i*n + j;
}
int
main(int argc, char* argv[]) {
SizeOptions opt("QueenArmies");
opt.size(6);
opt.branching(QueenArmies::BRANCH_SPECIFIC);
opt.branching(QueenArmies::BRANCH_NAIVE, "naive");
opt.branching(QueenArmies::BRANCH_SPECIFIC, "specific");
opt.solutions(0);
opt.parse(argc,argv);
// Set up the A-sets
// A[i] will contain the values attacked by a queen at position i
int n = opt.size();
A = new IntSet[n*n];
int *p = new int[std::max(n*n, 25)];
int pn = 0;
for (int i = n; i--; ) {
for (int j = n; j--; ) {
int dir[][2] = {
{ 0, 1},
{ 1, 1},
{ 1, 0},
{ 0, -1},
{-1, -1},
{-1, 0},
{ 1, -1},
{-1, 1}
};
p[pn++] = pos(i, j, n);
for (int k = 8; k--; ) {
for (int l = 0; l < n
&& 0 <= (i+l*dir[k][0]) && (i+l*dir[k][0]) < n
&& 0 <= (j+l*dir[k][1]) && (j+l*dir[k][1]) < n; ++l) {
p[pn++] = pos(i+l*dir[k][0], j+l*dir[k][1], n);
}
}
A[pos(i, j, n)] = IntSet(p, pn);
pn = 0;
}
}
delete [] p;
IntMaximizeScript::run<QueenArmies,BAB,SizeOptions>(opt);
return 0;
}
// STATISTICS: example-any
Gecode::ActorLink::Actor
friend class Actor
Definition core.hpp:590
Gecode::Actor::Brancher
friend class Brancher
Definition core.hpp:633
Gecode::Archive
Archive representation
Definition archive.hpp:42
Gecode::BoolVarArray
Boolean variable array.
Definition int.hh:808
Gecode::Brancher::Space
friend class Space
Definition core.hpp:1444
Gecode::Brancher::Brancher
Brancher(Home home)
Constructor for creation.
Definition core.hpp:3605
Gecode::Brancher::Choice
friend class Choice
Definition core.hpp:1445
Gecode::Choice
Choice for performing commit
Definition core.hpp:1412
Gecode::Choice::archive
virtual void archive(Archive &e) const
Archive into e.
Definition core.cpp:891
Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< IntMaximizeSpace > >::run
static void run(const Options &opt, Script *s=NULL)
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::IntSetRanges
Range iterator for integer sets.
Definition int.hh:292
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::IntVar
Integer variables.
Definition int.hh:371
Gecode::Int::BoolView
Boolean view for Boolean variables.
Definition view.hpp:1380
Gecode::Int::BoolView::eq
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition bool.hpp:170
Gecode::Iter::Ranges::Inter
Range iterator for computing intersection (binary).
Definition ranges-inter.hpp:44
Gecode::SetVarUnknownRanges
Iterator for the unknown ranges of a set variable.
Definition set.hh:334
Gecode::SetVar
Set variables
Definition set.hh:127
Gecode::SizeOptions
Options for scripts with additional size parameter
Definition driver.hh:675
Gecode::Space
Computation spaces.
Definition core.hpp:1742
QueenArmies::QueenBranch::choice
virtual Gecode::Choice * choice(Space &home)
Return choice.
Definition queen-armies.cpp:201
QueenArmies::QueenBranch::print
virtual void print(const Space &, const Gecode::Choice &_c, unsigned int a, std::ostream &o) const
Print explanation.
Definition queen-armies.cpp:240
QueenArmies::QueenBranch::commit
virtual ExecStatus commit(Space &home, const Gecode::Choice &_c, unsigned int a)
Perform commit for choice _c and alternative a.
Definition queen-armies.cpp:230
QueenArmies::QueenBranch::dispose
virtual size_t dispose(Space &)
Delete brancher and return its size.
Definition queen-armies.cpp:256
QueenArmies::QueenBranch::status
virtual bool status(const Space &home) const
Check status of brancher, return true if alternatives left.
Definition queen-armies.cpp:190
QueenArmies::QueenBranch::post
static void post(QueenArmies &home)
Post brancher.
Definition queen-armies.cpp:252
QueenArmies::QueenBranch::choice
virtual Choice * choice(const Space &, Archive &e)
Return choice.
Definition queen-armies.cpp:222
QueenArmies::QueenBranch::copy
virtual Actor * copy(Space &home)
Copy brancher during cloning.
Definition queen-armies.cpp:248
QueenArmies::QueenArmies
QueenArmies(const SizeOptions &opt)
Constructor.
Definition queen-armies.cpp:83
QueenArmies::main
int main(int argc, char *argv[])
Main-function.
Definition queen-armies.cpp:274
QueenArmies::pos
int pos(int i, int j, int n)
Position of a piece in a square board.
Definition queen-armies.cpp:266
QueenArmies::print
virtual void print(std::ostream &os) const
Print solution.
Definition queen-armies.cpp:139
QueenArmies::w
BoolVarArray w
The placement of the white queens.
Definition queen-armies.cpp:72
QueenArmies::b
BoolVarArray b
The placement of the black queens.
Definition queen-armies.cpp:73
QueenArmies::QueenArmies
QueenArmies(QueenArmies &s)
Constructor for cloning.
Definition queen-armies.cpp:120
QueenArmies::cost
virtual IntVar cost(void) const
Return solution cost.
Definition queen-armies.cpp:134
QueenArmies::q
IntVar q
The number of white queens placed.
Definition queen-armies.cpp:74
QueenArmies::BRANCH_NAIVE
@ BRANCH_NAIVE
Choose variables left to right.
Definition queen-armies.cpp:78
QueenArmies::BRANCH_SPECIFIC
@ BRANCH_SPECIFIC
Choose variable with problem specific strategy.
Definition queen-armies.cpp:79
QueenArmies::W
SetVar W
Set of squares occupied by white queens.
Definition queen-armies.cpp:71
QueenArmies::copy
virtual Space * copy(void)
Return copy during cloning.
Definition queen-armies.cpp:130
QueenArmies::n
const int n
Definition queen-armies.cpp:69
QueenArmies::U
SetVar U
Set of un-attacked squares.
Definition queen-armies.cpp:70
QueenArmies::A
IntSet * A
Position of a piece in a square board.
Definition queen-armies.cpp:46
Test::Options::parse
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
driver.hh
int.hh
set.hh
Gecode::me_failed
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
Gecode::IntMaximizeScript
Driver::ScriptBase< Driver::IgnoreStepOption< IntMaximizeSpace > > IntMaximizeScript
Base-class for scripts for finding solution of highest integer cost.
Definition driver.hh:814
Gecode::assign
void assign(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatAssign vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Assign all x with variable selection vars and value selection vals.
Definition branch.cpp:111
Gecode::branch
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
Gecode::linear
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition linear.cpp:41
Gecode::rel
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
Gecode::IRT_EQ
@ IRT_EQ
Equality ( ).
Definition int.hh:926
Gecode::IRT_GQ
@ IRT_GQ
Greater or equal ( ).
Definition int.hh:930
minimodel.hh
Gecode::Iter::Ranges::size
unsigned int size(I &i)
Size of all ranges of range iterator i.
Definition ranges-operations.hpp:74
Gecode
Gecode toplevel namespace
Gecode::BOOL_ASSIGN_MAX
BoolAssign BOOL_ASSIGN_MAX(void)
Select largest value.
Definition assign.hpp:105
Gecode::expr
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:915
Gecode::BOOL_VAR_NONE
BoolVarBranch BOOL_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:364
Gecode::BOOL_VAL_MAX
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
Definition val.hpp:135
Gecode::singleton
SetExpr singleton(const LinIntExpr &)
Singleton expression.
Definition set-expr.cpp:691
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
Gecode::ES_FAILED
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
Gecode::cardinality
LinIntExpr cardinality(const SetExpr &)
Cardinality of set expression.
Definition set-expr.cpp:817