Generated on Fri Aug 24 2012 04:52:25 for Gecode by doxygen 1.8.1.1
QueenArmies Class Reference

Example: Peaceable co-existing armies of queens More...

List of all members.

Classes

class  QueenBranch
 Custom brancher for Peacable queens. More...

Public Types

enum  { BRANCH_NAIVE, BRANCH_SPECIFIC }
 Branching to use for model. More...
enum  { SEARCH_BAB, SEARCH_RESTART }
 Search variants. More...

Public Member Functions

 QueenArmies (const SizeOptions &opt)
 Constructor.
 QueenArmies (bool share, QueenArmies &s)
 Constructor for cloning.
virtual Spacecopy (bool share)
 Return copy during cloning.
virtual IntVar cost (void) const
 Return solution cost.
virtual void print (std::ostream &os) const
 Print solution.
- Public Member Functions inherited from Gecode::Driver::ScriptBase< BaseSpace >
 ScriptBase (void)
 Default constructor.
 ScriptBase (bool share, ScriptBase &e)
 Constructor used for cloning.
virtual void compare (const Space &, std::ostream &os) const
 Compare with s.

Public Attributes

const int n
SetVar U
 Set of un-attacked squares.
SetVar W
 Set of squares occupied by white queens.
BoolVarArray w
 The placement of the white queens.
BoolVarArray b
 The placement of the black queens.
IntVar q
 The number of white queens placed.

Constant sets for attacking queens.

IntSetA
 Position of a piece in a square board.
int pos (int i, int j, int n)
 Position of a piece in a square board.
int main (int argc, char *argv[])
 Main-function.

Additional Inherited Members

- Static Public Member Functions inherited from Gecode::Driver::ScriptBase< BaseSpace >
template<class Script , template< class > class Engine, class Options >
static void run (const Options &opt)

Detailed Description

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.


Member Enumeration Documentation

anonymous enum

Branching to use for model.

Enumerator:
BRANCH_NAIVE 

Choose variables left to right.

BRANCH_SPECIFIC 

Choose variable with problem specific strategy.

Definition at line 81 of file queen-armies.cpp.

anonymous enum

Search variants.

Enumerator:
SEARCH_BAB 

Use branch and bound to optimize.

SEARCH_RESTART 

Use restart to optimize.

Definition at line 87 of file queen-armies.cpp.


Constructor & Destructor Documentation

QueenArmies::QueenArmies ( const SizeOptions opt)
inline

Constructor.

Definition at line 93 of file queen-armies.cpp.

QueenArmies::QueenArmies ( bool  share,
QueenArmies s 
)
inline

Constructor for cloning.

Definition at line 129 of file queen-armies.cpp.


Member Function Documentation

virtual Space* QueenArmies::copy ( bool  share)
inlinevirtual

Return copy during cloning.

Definition at line 139 of file queen-armies.cpp.

virtual IntVar QueenArmies::cost ( void  ) const
inlinevirtual

Return solution cost.

Definition at line 143 of file queen-armies.cpp.

virtual void QueenArmies::print ( std::ostream &  os) const
inlinevirtual

Print solution.

Reimplemented from Gecode::Driver::ScriptBase< BaseSpace >.

Definition at line 148 of file queen-armies.cpp.


Friends And Related Function Documentation

IntSet* A
related

Position of a piece in a square board.

Definition at line 50 of file queen-armies.cpp.

int pos ( int  i,
int  j,
int  n 
)
related

Position of a piece in a square board.

Definition at line 271 of file queen-armies.cpp.

int main ( int  argc,
char *  argv[] 
)
related

Main-function.

Definition at line 279 of file queen-armies.cpp.


Member Data Documentation

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.


The documentation for this class was generated from the following file: