Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0

Example: Nonogram More...

Public Types

enum  { BRANCH_NONE , BRANCH_AFC }
 

Public Member Functions

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

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.
 

Related Symbols

(Note that these are not member symbols.)

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< BaseSpace >
static std::ostream & select_ostream (const char *sn, std::ofstream &ofs)
 Choose output stream according to sn.
 
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 67 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 101 of file nonogram.cpp.

Constructor & Destructor Documentation

◆ Nonogram() [1/2]

Nonogram::Nonogram ( const SizeOptions & opt)
inline

Construction of the model.

Definition at line 107 of file nonogram.cpp.

◆ Nonogram() [2/2]

Nonogram::Nonogram ( Nonogram & s)
inline

Constructor for cloning s.

Definition at line 170 of file nonogram.cpp.

Member Function Documentation

◆ width()

int Nonogram::width ( void ) const
inlineprotected

Return width of board.

Definition at line 75 of file nonogram.cpp.

◆ height()

int Nonogram::height ( void ) const
inlineprotected

Return height of board.

Definition at line 79 of file nonogram.cpp.

◆ line()

DFA Nonogram::line ( int & spos)
inlineprotected

Returns next regular expression for line starting from spos.

Definition at line 84 of file nonogram.cpp.

◆ copy()

virtual Space * Nonogram::copy ( void )
inlinevirtual

Copy space during cloning.

Definition at line 176 of file nonogram.cpp.

◆ print()

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

Print solution.

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

Definition at line 182 of file nonogram.cpp.

Friends And Related Symbol Documentation

◆ 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 231 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 256 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 284 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 315 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 342 of file nonogram.cpp.

◆ difficult

const int difficult[]
related

Specification for a more difficult picture.

Definition at line 361 of file nonogram.cpp.

◆ non_unique

const int non_unique[]
related

Specification for a non-unique picture.

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

◆ castle

const int castle[]
related

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

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

◆ webpbn436

const int webpbn436[]
related

Petro.

Definition at line 650 of file nonogram.cpp.

◆ webpbn21

const int webpbn21[]
related

Skid.

Definition at line 732 of file nonogram.cpp.

◆ webpbn27

const int webpbn27[]
related

Bucks.

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

◆ webpbn6

const int webpbn6[]
related

Cat.

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

◆ webpbn16

const int webpbn16[]
related

Knot.

Definition at line 932 of file nonogram.cpp.

◆ webpbn529

const int webpbn529[]
related

Swing.

Definition at line 1007 of file nonogram.cpp.

◆ webpbn65

const int webpbn65[]
related

Mum.

Definition at line 1105 of file nonogram.cpp.

◆ specs

const int* specs[]
related
Initial value:
}
const int webpbn6[]
Cat.
Definition nonogram.cpp:857
const int webpbn65[]
Mum.
const int difficult[]
Specification for a more difficult picture.
Definition nonogram.cpp:361
const int heart[]
Specification for a heart-shaped picture.
Definition nonogram.cpp:231
const int webpbn1[]
Dancer.
Definition nonogram.cpp:835
const int p200[]
Specification for a picture of cupid.
Definition nonogram.cpp:589
const int webpbn27[]
Bucks.
Definition nonogram.cpp:778
const int bear[]
Specification for a bear/bunny-shaped picture.
Definition nonogram.cpp:256
const int dragonfly[]
Specification for a dragonfly-picture.
Definition nonogram.cpp:435
const int crocodile[]
Specification for a crocodile-shaped picture.
Definition nonogram.cpp:284
const int pinwheel[]
Specification for a pinwheel-picture.
Definition nonogram.cpp:342
const int webpbn436[]
Petro.
Definition nonogram.cpp:650
const int castle[]
From http://www.cs.kuleuven.be/~bmd/nonogram.pl.
Definition nonogram.cpp:482
const int unknown[]
Specification for an unknown picture.
Definition nonogram.cpp:315
const int non_unique[]
Specification for a non-unique picture.
Definition nonogram.cpp:398
const int webpbn16[]
Knot.
Definition nonogram.cpp:932
const int webpbn23[]
Edge.
Definition nonogram.cpp:904
const int webpbn21[]
Skid.
Definition nonogram.cpp:732
const int webpbn529[]
Swing.

Specification for a heart-shaped picture.

Definition at line 1186 of file nonogram.cpp.

◆ n_examples

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

Specification for a heart-shaped picture.

Definition at line 1200 of file nonogram.cpp.

◆ main()

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

Main-function.

Definition at line 199 of file nonogram.cpp.

Member Data Documentation

◆ spec

const int* Nonogram::spec
protected

Specification to be used.

Definition at line 70 of file nonogram.cpp.

◆ b

BoolVarArray Nonogram::b
protected

Fields of board.

Definition at line 72 of file nonogram.cpp.


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