Generated on Mon Aug 25 11:35:48 2008 for Gecode by doxygen 1.5.6

# Nonogram Class Reference [Scripts for problems]

Inherits Example.

## 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/.

Definition at line 64 of file nonogram.cc.

## 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 p200 []
Specification for a picture of a flower.
const int * specs []
Specification for a heart-shaped picture.
const unsigned n_examples = sizeof(specs)/sizeof(int*)
Specification for a heart-shaped picture.

## 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)
Print solution.

## Protected Member Functions

int width (void) const
Return width of board.
int height (void) const
Return height of board.
BoolVar pos (int h, int w)
Access position (h,w) in matrix.
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.

## Constructor & Destructor Documentation

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

Construction of the model.

Definition at line 101 of file nonogram.cc.

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

Constructor for cloning s.

Definition at line 119 of file nonogram.cc.

## Member Function Documentation

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

Return width of board.

Definition at line 72 of file nonogram.cc.

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

Return height of board.

Definition at line 76 of file nonogram.cc.

 BoolVar Nonogram::pos ( int h, int w ) ` [inline, protected]`

Access position (h,w) in matrix.

Definition at line 81 of file nonogram.cc.

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

Returns next regular expression for line starting from spos.

Definition at line 86 of file nonogram.cc.

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

Copy space during cloning.

Implements Gecode::Space.

Definition at line 125 of file nonogram.cc.

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

Print solution.

Reimplemented from Example.

Definition at line 131 of file nonogram.cc.

## 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 174 of file nonogram.cc.

 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 199 of file nonogram.cc.

 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 227 of file nonogram.cc.

 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 258 of file nonogram.cc.

 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 285 of file nonogram.cc.

 const int difficult[]` [related]`

Specification for a more difficult picture.

Definition at line 304 of file nonogram.cc.

 const int non_unique[]` [related]`

Specification for a non-unique picture.

Definition at line 341 of file nonogram.cc.

 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 378 of file nonogram.cc.

 const int p200[]` [related]`

Specification for a picture of a flower.

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

Definition at line 429 of file nonogram.cc.

 const int* specs[]` [related]`

Initial value:

``` {heart, bear, crocodile, unknown,
pinwheel, difficult, non_unique, dragonfly, p200}
```
Specification for a heart-shaped picture.

Definition at line 485 of file nonogram.cc.

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

Specification for a heart-shaped picture.

Definition at line 487 of file nonogram.cc.

## Member Data Documentation

 const int* Nonogram::spec` [protected]`

Specification to be used.

Definition at line 67 of file nonogram.cc.

 BoolVarArray Nonogram::b` [protected]`

Fields of board.

Definition at line 69 of file nonogram.cc.

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