Generated on Sat Feb 7 2015 02:01:38 for Gecode by doxygen 1.8.9.1
Nonogram Class Reference

Example: Nonogram More...

Public Types

enum  { BRANCH_NONE, BRANCH_AFC }
 

Public Member Functions

 Nonogram (const SizeOptions &opt)
 Construction of the model. More...
 
 Nonogram (bool share, Nonogram &s)
 Constructor for cloning s. More...
 
virtual Spacecopy (bool share)
 Copy space during cloning. More...
 
virtual void print (std::ostream &os) const
 Print solution. More...
 
- Public Member Functions inherited from Gecode::Driver::ScriptBase< BaseSpace >
 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...
 

Protected Member Functions

int width (void) const
 Return width of board. More...
 
int height (void) const
 Return height of board. More...
 
DFA line (int &spos)
 Returns next regular expression for line starting from spos. More...
 

Protected Attributes

const int * spec
 Specification to be used. More...
 
BoolVarArray b
 Fields of board. More...
 

Related Functions

(Note that these are not member functions.)

int main (int argc, char *argv[])
 Main-function. More...
 

Picture specifications

A specification is given by a list of integers. The first two integers (w and h) specify the number of columns and rows respectively. Then w + h groups of integers follows. Each group is started by the number of integers it contains (n), followed by n integers specifying the sizes of the stretches of markers in that row/column.

const int heart []
 Specification for a heart-shaped picture. More...
 
const int bear []
 Specification for a bear/bunny-shaped picture. More...
 
const int crocodile []
 Specification for a crocodile-shaped picture. More...
 
const int unknown []
 Specification for an unknown picture. More...
 
const int pinwheel []
 Specification for a pinwheel-picture. More...
 
const int difficult []
 Specification for a more difficult picture. More...
 
const int non_unique []
 Specification for a non-unique picture. More...
 
const int dragonfly []
 Specification for a dragonfly-picture. More...
 
const int castle []
 From http://www.cs.kuleuven.be/~bmd/nonogram.pl. More...
 
const int p200 []
 Specification for a picture of cupid. More...
 
const int webpbn436 []
 Petro. More...
 
const int webpbn21 []
 Skid. More...
 
const int webpbn27 []
 Bucks. More...
 
const int webpbn1 []
 Dancer. More...
 
const int webpbn6 []
 Cat. More...
 
const int webpbn23 []
 Edge. More...
 
const int webpbn16 []
 Knot. More...
 
const int webpbn529 []
 Swing. More...
 
const int webpbn65 []
 Mum. More...
 
const int * specs []
 Specification for a heart-shaped picture. More...
 
const unsigned n_examples = sizeof(specs)/sizeof(int*)
 Specification for a heart-shaped picture. More...
 

Additional Inherited Members

- Static Public Member Functions inherited from Gecode::Driver::ScriptBase< BaseSpace >
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)
 

Detailed Description

Example: Nonogram

This example solves nonograms. A nonogram is composed of a matrix of markers. For each row/column there is a specification on how many groups of markers (separated by one or more unmarked spots) and their length. The objective is to find a valid assignment, which incidentally may also produce a pretty picture.

See problem 12 at http://www.csplib.org/.

Note that "Modeling and Programming with Gecode" uses this example as a case study.

Definition at line 71 of file nonogram.cpp.

Constructor & Destructor Documentation

Nonogram::Nonogram ( const SizeOptions opt)
inline

Construction of the model.

Definition at line 111 of file nonogram.cpp.

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

Constructor for cloning s.

Definition at line 174 of file nonogram.cpp.

Member Function Documentation

int Nonogram::width ( void  ) const
inlineprotected

Return width of board.

Definition at line 79 of file nonogram.cpp.

int Nonogram::height ( void  ) const
inlineprotected

Return height of board.

Definition at line 83 of file nonogram.cpp.

DFA Nonogram::line ( int &  spos)
inlineprotected

Returns next regular expression for line starting from spos.

Definition at line 88 of file nonogram.cpp.

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

Copy space during cloning.

Definition at line 180 of file nonogram.cpp.

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

Print solution.

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

Definition at line 186 of file nonogram.cpp.

Friends And Related Function Documentation

const int heart[]
related
Initial value:
=
{ 9, 9,
1, 3,
2, 2, 3,
2, 2, 2,
2, 2, 2,
2, 2, 2,
2, 2, 2,
2, 2, 2,
2, 2, 3,
1, 3,
2, 2, 2,
2, 4, 4,
3, 1, 3, 1,
3, 2, 1, 2,
2, 1, 1,
2, 2, 2,
2, 2, 2,
1, 3,
1, 1
}

Specification for a heart-shaped picture.

Definition at line 235 of file nonogram.cpp.

const int bear[]
related
Initial value:
=
{ 13, 8,
1, 2,
2, 2, 1,
2, 3, 2,
1, 6,
2, 1, 4,
1, 3,
1, 4,
1, 4,
1, 4,
1, 5,
1, 4,
2, 1, 3,
1, 2,
1, 1,
1, 2,
2, 4, 4,
1, 12,
1, 8,
1, 9,
2, 3, 4,
2, 2, 2
}

Specification for a bear/bunny-shaped picture.

Definition at line 260 of file nonogram.cpp.

const int crocodile[]
related
Initial value:
=
{ 15, 9,
1, 3,
1, 4,
2, 2, 2,
2, 3, 1,
2, 2, 3,
2, 3, 2,
2, 2, 3,
2, 4, 2,
2, 3, 2,
1, 6,
2, 1, 3,
2, 1, 3,
2, 1, 4,
1, 5,
1, 5,
1, 3,
3, 2, 3, 2,
2, 10, 3,
1, 15,
5, 1, 1, 1, 1, 6,
2, 1, 7,
2, 1, 4,
2, 1, 4,
1, 4
}

Specification for a crocodile-shaped picture.

Definition at line 288 of file nonogram.cpp.

const int unknown[]
related
Initial value:
=
{ 10, 10,
1, 3,
2, 2, 1,
2, 2, 2,
2, 2, 1,
3, 1, 2, 1,
2, 1, 1,
3, 1, 4, 1,
3, 1, 1, 2,
2, 3, 1,
1, 4,
1, 3,
2, 2, 1,
2, 1, 1,
2, 1, 4,
4, 1, 1, 1, 1,
4, 2, 1, 1, 1,
3, 2, 1, 1,
2, 1, 2,
2, 2, 3,
1, 3
}

Specification for an unknown picture.

Definition at line 319 of file nonogram.cpp.

const int pinwheel[]
related
Initial value:
=
{ 6, 6,
2, 1, 2,
1, 1,
1, 2,
1, 2,
1, 1,
2, 2, 1,
2, 2, 1,
1, 1,
1, 2,
1, 2,
1, 1,
2, 1, 2
}

Specification for a pinwheel-picture.

Definition at line 346 of file nonogram.cpp.

const int difficult[]
related

Specification for a more difficult picture.

Definition at line 365 of file nonogram.cpp.

const int non_unique[]
related

Specification for a non-unique picture.

Definition at line 402 of file nonogram.cpp.

const int dragonfly[]
related

Specification for a dragonfly-picture.

From http://www.oberlin.edu/math/faculty/bosch/pbn-page.html, where it is claimed that it is hard.

Definition at line 439 of file nonogram.cpp.

const int castle[]
related

From http://www.cs.kuleuven.be/~bmd/nonogram.pl.

Definition at line 486 of file nonogram.cpp.

const int p200[]
related

Specification for a picture of cupid.

From http://www.icparc.ic.ac.uk/eclipse/examples/nono.ecl.txt, the hardest instance.

Definition at line 593 of file nonogram.cpp.

const int webpbn436[]
related

Petro.

Definition at line 654 of file nonogram.cpp.

const int webpbn21[]
related

Skid.

Definition at line 736 of file nonogram.cpp.

const int webpbn27[]
related

Bucks.

Definition at line 782 of file nonogram.cpp.

const int webpbn1[]
related
Initial value:
=
{ 5, 10,
2, 2, 1,
3, 2, 1, 3,
1, 7,
2, 1, 3,
2, 2, 1,
1, 2,
2, 2, 1,
2, 1, 1,
1, 3,
2, 1, 1,
2, 1, 1,
1, 2,
2, 1, 1,
2, 1, 2,
1, 2,
}

Dancer.

Definition at line 839 of file nonogram.cpp.

const int webpbn6[]
related

Cat.

Definition at line 861 of file nonogram.cpp.

const int webpbn23[]
related
Initial value:
=
{ 10, 11,
1, 1,
1, 3,
1, 1,
2, 2, 2,
1, 2,
1, 4,
1, 1,
1, 3,
1, 3,
1, 1,
1, 1,
1, 3,
1, 1,
1, 2,
1, 1,
1, 3,
1, 3,
1, 1,
1, 2,
1, 2,
1, 4,
}

Edge.

Definition at line 908 of file nonogram.cpp.

const int webpbn16[]
related

Knot.

Definition at line 936 of file nonogram.cpp.

const int webpbn529[]
related

Swing.

Definition at line 1011 of file nonogram.cpp.

const int webpbn65[]
related

Mum.

Definition at line 1109 of file nonogram.cpp.

const int* specs[]
related
Initial value:

Specification for a heart-shaped picture.

Definition at line 1190 of file nonogram.cpp.

const unsigned n_examples = sizeof(specs)/sizeof(int*)
related

Specification for a heart-shaped picture.

Definition at line 1204 of file nonogram.cpp.

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

Main-function.

Definition at line 203 of file nonogram.cpp.

Member Data Documentation

const int* Nonogram::spec
protected

Specification to be used.

Definition at line 74 of file nonogram.cpp.

BoolVarArray Nonogram::b
protected

Fields of board.

Definition at line 76 of file nonogram.cpp.


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