Example: Peaceable co-existing armies of queens More...
Classes | |
class | QueenBranch |
Custom brancher for Peacable queens. More... | |
Public Types | |
enum | { BRANCH_NAIVE, BRANCH_SPECIFIC } |
Branching to use for model. More... | |
Public Member Functions | |
QueenArmies (const SizeOptions &opt) | |
Constructor. More... | |
QueenArmies (bool share, QueenArmies &s) | |
Constructor for cloning. More... | |
virtual Space * | copy (bool share) |
Return copy during cloning. More... | |
virtual IntVar | cost (void) const |
Return solution cost. More... | |
virtual void | print (std::ostream &os) const |
Print solution. More... | |
![]() | |
ScriptBase (void) | |
Default constructor. More... | |
ScriptBase (bool share, ScriptBase &e) | |
Constructor used for cloning. More... | |
virtual void | compare (const Space &, std::ostream &os) const |
Compare with s. More... | |
Public Attributes | |
const int | n |
SetVar | U |
Set of un-attacked squares. More... | |
SetVar | W |
Set of squares occupied by white queens. More... | |
BoolVarArray | w |
The placement of the white queens. More... | |
BoolVarArray | b |
The placement of the black queens. More... | |
IntVar | q |
The number of white queens placed. More... | |
Constant sets for attacking queens. | |
IntSet * | A |
Position of a piece in a square board. More... | |
int | pos (int i, int j, int n) |
Position of a piece in a square board. More... | |
int | main (int argc, char *argv[]) |
Main-function. More... | |
Additional Inherited Members | |
![]() | |
static std::ostream & | select_ostream (const char *name, std::ofstream &ofs) |
Choose output stream according to name. More... | |
template<class Script , template< class > class Engine, class Options > | |
static void | run (const Options &opt, Script *s=NULL) |
Example: Peaceable co-existing armies of queens
The goal of this problem is to place as many white and black queens on a chess-board without any two queens of different color attacking each other. The number of black queens should be greater than or equal to the number of white queens.
This model is based on the one presented in "Models and Symmetry Breaking for 'Peaceable Armies of Queens'", by Barbara M. Smith, Karen E. Petrie, and Ian P. Gent.
The smart version uses a custom brancher implementing a heuristic from the above paper, that helps speeding up the proof of optimality.
Definition at line 71 of file queen-armies.cpp.
|
inline |
Constructor.
Definition at line 87 of file queen-armies.cpp.
|
inline |
Constructor for cloning.
Definition at line 123 of file queen-armies.cpp.
|
inlinevirtual |
Return copy during cloning.
Definition at line 133 of file queen-armies.cpp.
|
inlinevirtual |
Return solution cost.
Definition at line 137 of file queen-armies.cpp.
|
inlinevirtual |
Print solution.
Reimplemented from Gecode::Driver::ScriptBase< BaseSpace >.
Definition at line 142 of file queen-armies.cpp.
|
related |
Position of a piece in a square board.
Definition at line 50 of file queen-armies.cpp.
|
related |
Position of a piece in a square board.
Definition at line 273 of file queen-armies.cpp.
|
related |
Main-function.
Definition at line 281 of file queen-armies.cpp.
const int QueenArmies::n |
Definition at line 73 of file queen-armies.cpp.
SetVar QueenArmies::U |
Set of un-attacked squares.
Definition at line 74 of file queen-armies.cpp.
SetVar QueenArmies::W |
Set of squares occupied by white queens.
Definition at line 74 of file queen-armies.cpp.
BoolVarArray QueenArmies::w |
The placement of the white queens.
Definition at line 76 of file queen-armies.cpp.
BoolVarArray QueenArmies::b |
The placement of the black queens.
Definition at line 76 of file queen-armies.cpp.
IntVar QueenArmies::q |
The number of white queens placed.
Definition at line 78 of file queen-armies.cpp.