Generated on for Gecode by doxygen 1.17.0

Example: Nonogram More...

Public Types

enum  { BRANCH_NONE , BRANCH_AFC }

Public Member Functions

 Nonogram (const InstanceOptions &opt)
 Construction of the model.
 Nonogram (Nonogram &s)
 Constructor for cloning s.
virtual Space * copy (void)
 Copy space during cloning.
virtual void print (std::ostream &os) const
 Print solution.
Public Member Functions inherited from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > >
 ScriptBase (const Options &opt)
 Constructor.
 ScriptBase (ScriptBase &e)
 Constructor used for cloning.
virtual void compare (const Space &home, std::ostream &os) const
 Compare with s.
Public Member Functions inherited from Gecode::Driver::IgnoreStepOption< BaseSpace >
 IgnoreStepOption (const Options &)
 Constructor.
 IgnoreStepOption (BaseSpace &e)
 Constructor used for cloning.

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

IntSharedArray file
 Specification read from a file.
const int * spec
 Specification to be used.
BoolVarArray b
 Fields of board.

(Note that these are not member symbols.)

const char * instance_spec
 Reader spec for nonogram files.
int main (int argc, char *argv[])
 Main-function.

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.

Additional Inherited Members

Static Public Member Functions inherited from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > >
static std::ostream & select_ostream (const char *sn, std::ofstream &ofs)
 Choose output stream according to sn.
static void run (const Options &opt, Script *s=nullptr)

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

The instance is either the number of a built-in specification or a file in the .non format exported by webpbn.com.

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

Definition at line 135 of file nonogram.cpp.

Member Enumeration Documentation

◆ anonymous enum

anonymous enum
Enumerator
BRANCH_NONE 

Branch on rows/columns in order.

BRANCH_AFC 

Use AFC for branching.

Definition at line 171 of file nonogram.cpp.

Constructor & Destructor Documentation

◆ Nonogram() [1/2]

Nonogram::Nonogram ( const InstanceOptions & opt)
inline

Construction of the model.

Definition at line 177 of file nonogram.cpp.

◆ Nonogram() [2/2]

Nonogram::Nonogram ( Nonogram & s)
inline

Constructor for cloning s.

Definition at line 240 of file nonogram.cpp.

Member Function Documentation

◆ width()

int Nonogram::width ( void ) const
inlineprotected

Return width of board.

Definition at line 145 of file nonogram.cpp.

◆ height()

int Nonogram::height ( void ) const
inlineprotected

Return height of board.

Definition at line 149 of file nonogram.cpp.

◆ line()

DFA Nonogram::line ( int & spos)
inlineprotected

Returns next regular expression for line starting from spos.

Definition at line 154 of file nonogram.cpp.

◆ copy()

virtual Space * Nonogram::copy ( void )
inlinevirtual

Copy space during cloning.

Definition at line 246 of file nonogram.cpp.

◆ print()

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

Print solution.

Reimplemented from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > >.

Definition at line 252 of file nonogram.cpp.

◆ instance_spec

const char* instance_spec
related
Initial value:
= R"(format nonogram
separators ","
sections skip other {
"width {width:1..}"
"height {height:1..}"
"rows" { repeat height { list row: 0.. until eol } }
"columns" { repeat width { list col: 0.. until eol } }
}
check height <= 1000000 / width "the board must have at most a million fields"
check size(row) == height && size(col) == width "the numbers of rows and columns differ from the board size"
check count(row) <= 1 || min(row) > 0 "a 0 must be the only clue of its row"
check count(col) <= 1 || min(col) > 0 "a 0 must be the only clue of its column"
check sum(row) + count(row) - 1 <= width "the clues of a row do not fit into the width of the board"
check sum(col) + count(col) - 1 <= height "the clues of a column do not fit into the height of the board"
)"

Reader spec for nonogram files.

The .non format exported by webpbn.com: keyword lines such as width 20 and height 15, then rows and columns, each followed by one line of comma-separated clues per row or column, where 0 stands for an empty line. Other keywords (title, by, copyright, goal, ...) are ignored. See Instance::Spec for the spec language.

Definition at line 61 of file nonogram.cpp.

◆ heart

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

◆ bear

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

◆ crocodile

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

◆ unknown

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

◆ pinwheel

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

◆ difficult

const int difficult[]
related

Specification for a more difficult picture.

Definition at line 436 of file nonogram.cpp.

◆ non_unique

const int non_unique[]
related

Specification for a non-unique picture.

Definition at line 473 of file nonogram.cpp.

◆ dragonfly

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

◆ castle

const int castle[]
related

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

Definition at line 557 of file nonogram.cpp.

◆ p200

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

◆ webpbn436

const int webpbn436[]
related

Petro.

Definition at line 725 of file nonogram.cpp.

◆ webpbn21

const int webpbn21[]
related

Skid.

Definition at line 807 of file nonogram.cpp.

◆ webpbn27

const int webpbn27[]
related

Bucks.

Definition at line 853 of file nonogram.cpp.

◆ webpbn1

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

◆ webpbn6

const int webpbn6[]
related

Cat.

Definition at line 932 of file nonogram.cpp.

◆ webpbn23

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

◆ webpbn16

const int webpbn16[]
related

Knot.

Definition at line 1007 of file nonogram.cpp.

◆ webpbn529

const int webpbn529[]
related

Swing.

Definition at line 1082 of file nonogram.cpp.

◆ webpbn65

const int webpbn65[]
related

Mum.

Definition at line 1180 of file nonogram.cpp.

◆ specs

const int* specs[]
related
Initial value:
}
const int webpbn6[]
Cat.
Definition nonogram.cpp:932
const int webpbn65[]
Mum.
const int difficult[]
Specification for a more difficult picture.
Definition nonogram.cpp:436
const int heart[]
Specification for a heart-shaped picture.
Definition nonogram.cpp:306
const int webpbn1[]
Dancer.
Definition nonogram.cpp:910
const int p200[]
Specification for a picture of cupid.
Definition nonogram.cpp:664
const int webpbn27[]
Bucks.
Definition nonogram.cpp:853
const int bear[]
Specification for a bear/bunny-shaped picture.
Definition nonogram.cpp:331
const int dragonfly[]
Specification for a dragonfly-picture.
Definition nonogram.cpp:510
const int crocodile[]
Specification for a crocodile-shaped picture.
Definition nonogram.cpp:359
const int pinwheel[]
Specification for a pinwheel-picture.
Definition nonogram.cpp:417
const int webpbn436[]
Petro.
Definition nonogram.cpp:725
const int castle[]
From http://www.cs.kuleuven.be/~bmd/nonogram.pl.
Definition nonogram.cpp:557
const int unknown[]
Specification for an unknown picture.
Definition nonogram.cpp:390
const int non_unique[]
Specification for a non-unique picture.
Definition nonogram.cpp:473
const int webpbn16[]
Knot.
const int webpbn23[]
Edge.
Definition nonogram.cpp:979
const int webpbn21[]
Skid.
Definition nonogram.cpp:807
const int webpbn529[]
Swing.

Specification for a heart-shaped picture.

Definition at line 1261 of file nonogram.cpp.

◆ n_examples

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

Specification for a heart-shaped picture.

Definition at line 1275 of file nonogram.cpp.

◆ main()

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

Main-function.

Definition at line 269 of file nonogram.cpp.

Member Data Documentation

◆ file

IntSharedArray Nonogram::file
protected

Specification read from a file.

Definition at line 138 of file nonogram.cpp.

◆ spec

const int* Nonogram::spec
protected

Specification to be used.

Definition at line 140 of file nonogram.cpp.

◆ b

BoolVarArray Nonogram::b
protected

Fields of board.

Definition at line 142 of file nonogram.cpp.


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