Generated on Thu Mar 22 10:39:51 2012 for Gecode by doxygen 1.6.3

Nonogram Class Reference
[Example scripts (models)]

Example: Nonogram More...

List of all members.

Public Types

enum  { BRANCH_NONE, BRANCH_AFC }

Public Member Functions

 Nonogram (const SizeOptions &opt)
 Construction of the model.
 Nonogram (bool share, Nonogram &s)
 Constructor for cloning s.
virtual Spacecopy (bool share)
 Copy space during cloning.
virtual void print (std::ostream &os) const
 Print solution.

Protected Member Functions

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

Protected Attributes

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

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

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 77 of file nonogram.cpp.


Member Enumeration Documentation

anonymous enum
Enumerator:
BRANCH_NONE 

Branch on rows/columns in order.

BRANCH_AFC 

Use AFC for branching.

Definition at line 111 of file nonogram.cpp.


Constructor & Destructor Documentation

Nonogram::Nonogram ( const SizeOptions opt  )  [inline]

Construction of the model.

Definition at line 117 of file nonogram.cpp.

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

Constructor for cloning s.

Definition at line 180 of file nonogram.cpp.


Member Function Documentation

int Nonogram::width ( void   )  const [inline, protected]

Return width of board.

Definition at line 85 of file nonogram.cpp.

int Nonogram::height ( void   )  const [inline, protected]

Return height of board.

Definition at line 89 of file nonogram.cpp.

DFA Nonogram::line ( int &  spos  )  [inline, protected]

Returns next regular expression for line starting from spos.

Definition at line 94 of file nonogram.cpp.

virtual Space* Nonogram::copy ( bool  share  )  [inline, virtual]

Copy space during cloning.

Definition at line 186 of file nonogram.cpp.

virtual void Nonogram::print ( std::ostream &  os  )  const [inline, virtual]

Print solution.

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

Definition at line 192 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 241 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 266 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 294 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 325 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 352 of file nonogram.cpp.

const int difficult[] [related]

Specification for a more difficult picture.

Definition at line 371 of file nonogram.cpp.

const int non_unique[] [related]

Specification for a non-unique picture.

Definition at line 408 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 445 of file nonogram.cpp.

const int castle[] [related]
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 599 of file nonogram.cpp.

const int webpbn436[] [related]

Petro.

Definition at line 660 of file nonogram.cpp.

const int webpbn21[] [related]

Skid.

Definition at line 742 of file nonogram.cpp.

const int webpbn27[] [related]

Bucks.

Definition at line 788 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 845 of file nonogram.cpp.

const int webpbn6[] [related]

Cat.

Definition at line 867 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 914 of file nonogram.cpp.

const int webpbn16[] [related]

Knot.

Definition at line 942 of file nonogram.cpp.

const int webpbn529[] [related]

Swing.

Definition at line 1017 of file nonogram.cpp.

const int webpbn65[] [related]

Mum.

Definition at line 1115 of file nonogram.cpp.

const int* specs[] [related]
Initial value:

Specification for a heart-shaped picture.

Definition at line 1196 of file nonogram.cpp.

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

Specification for a heart-shaped picture.

Definition at line 1210 of file nonogram.cpp.


Member Data Documentation

const int* Nonogram::spec [protected]

Specification to be used.

Definition at line 80 of file nonogram.cpp.

Fields of board.

Definition at line 82 of file nonogram.cpp.


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