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 Space * | copy (bool share) |
Copy space during cloning. More... | |
virtual void | print (std::ostream &os) const |
Print solution. More... | |
![]() | |
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 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) |
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.
|
inline |
Construction of the model.
Definition at line 111 of file nonogram.cpp.
|
inline |
Constructor for cloning s.
Definition at line 174 of file nonogram.cpp.
|
inlineprotected |
Return width of board.
Definition at line 79 of file nonogram.cpp.
|
inlineprotected |
Return height of board.
Definition at line 83 of file nonogram.cpp.
|
inlineprotected |
Returns next regular expression for line starting from spos.
Definition at line 88 of file nonogram.cpp.
|
inlinevirtual |
Copy space during cloning.
Definition at line 180 of file nonogram.cpp.
|
inlinevirtual |
Print solution.
Reimplemented from Gecode::Driver::ScriptBase< BaseSpace >.
Definition at line 186 of file nonogram.cpp.
|
related |
Specification for a heart-shaped picture.
Definition at line 235 of file nonogram.cpp.
|
related |
Specification for a bear/bunny-shaped picture.
Definition at line 260 of file nonogram.cpp.
|
related |
Specification for a crocodile-shaped picture.
Definition at line 288 of file nonogram.cpp.
|
related |
Specification for an unknown picture.
Definition at line 319 of file nonogram.cpp.
|
related |
Specification for a pinwheel-picture.
Definition at line 346 of file nonogram.cpp.
|
related |
Specification for a more difficult picture.
Definition at line 365 of file nonogram.cpp.
|
related |
Specification for a non-unique picture.
Definition at line 402 of file nonogram.cpp.
|
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.
|
related |
From http://www.cs.kuleuven.be/~bmd/nonogram.pl.
Definition at line 486 of file nonogram.cpp.
|
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.
|
related |
Petro.
Definition at line 654 of file nonogram.cpp.
|
related |
Skid.
Definition at line 736 of file nonogram.cpp.
|
related |
Bucks.
Definition at line 782 of file nonogram.cpp.
|
related |
Dancer.
Definition at line 839 of file nonogram.cpp.
|
related |
Cat.
Definition at line 861 of file nonogram.cpp.
|
related |
Edge.
Definition at line 908 of file nonogram.cpp.
|
related |
Knot.
Definition at line 936 of file nonogram.cpp.
|
related |
Swing.
Definition at line 1011 of file nonogram.cpp.
|
related |
Mum.
Definition at line 1109 of file nonogram.cpp.
|
related |
|
related |
Specification for a heart-shaped picture.
Definition at line 1204 of file nonogram.cpp.
|
related |
Main-function.
Definition at line 203 of file nonogram.cpp.
|
protected |
Specification to be used.
Definition at line 74 of file nonogram.cpp.
|
protected |
Fields of board.
Definition at line 76 of file nonogram.cpp.