QueenArmies Class Reference
[Scripts for problems]

Inherits Example.

List of all members.

---

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 branching implementing a heuristic from the above paper, that helps speeding up the proof of optimality.

Definition at line 69 of file queen-armies.cc.

Constant sets for attacking queens.
IntSet *	A
	Position of a piece in a square board.
int	pos (int i, int j, int n)
	Position of a piece in a square board.
Public Types
enum	{ BRANCH_NAIVE, BRANCH_SPECIFIC }
	Branching to use for model. More...
Public Member Functions
	QueenArmies (const SizeOptions &opt)
	Constructor.
	QueenArmies (bool share, QueenArmies &s)
	Constructor for cloning.
virtual Space *	copy (bool share)
	Copying member function.
void	constrain (Space *s)
virtual void	print (std::ostream &os)
	Print a solution to os.
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.
Classes
class	QueenBranch
	Custom branching for Peacaeble queens. More...

---

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 79 of file queen-armies.cc.

---

Constructor & Destructor Documentation

QueenArmies::QueenArmies

(

const SizeOptions &

opt

)

[inline]

Constructor.

Definition at line 84 of file queen-armies.cc.

QueenArmies::QueenArmies	(	bool	share,
		QueenArmies &	s
	)			[inline]

Constructor for cloning.

Definition at line 121 of file queen-armies.cc.

---

Member Function Documentation

virtual Space* QueenArmies::copy

(

bool

share

)

[inline, virtual]

Copying member function.

Must create a new object using the constructor for cloning.

Implements Gecode::Space.

Definition at line 132 of file queen-armies.cc.

void QueenArmies::constrain

(

Space *

s

)

[inline]

Definition at line 137 of file queen-armies.cc.

virtual void QueenArmies::print

(

std::ostream &

os

)

[inline, virtual]

Print a solution to os.

Reimplemented from Example.

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

---

Friends And Related Function Documentation

IntSet* A [related]

Position of a piece in a square board.

Definition at line 48 of file queen-armies.cc.

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

Position of a piece in a square board.

Definition at line 229 of file queen-armies.cc.

---

Member Data Documentation

const int QueenArmies::n

Definition at line 71 of file queen-armies.cc.

SetVar QueenArmies::U

Set of un-attacked squares.

Definition at line 72 of file queen-armies.cc.

SetVar QueenArmies::W

Set of squares occupied by white queens.

Definition at line 72 of file queen-armies.cc.

BoolVarArray QueenArmies::w

The placement of the white queens.

Definition at line 74 of file queen-armies.cc.

BoolVarArray QueenArmies::b

The placement of the black queens.

Definition at line 74 of file queen-armies.cc.

IntVar QueenArmies::q

The number of white queens placed.

Definition at line 76 of file queen-armies.cc.

---

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

• examples/queen-armies.cc (Revision: 6053)