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 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 | |
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< 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=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 67 of file nonogram.cpp.
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.
|
inline |
Construction of the model.
Definition at line 107 of file nonogram.cpp.
|
inline |
Constructor for cloning s.
Definition at line 170 of file nonogram.cpp.
|
inlineprotected |
Return width of board.
Definition at line 75 of file nonogram.cpp.
|
inlineprotected |
Return height of board.
Definition at line 79 of file nonogram.cpp.
|
inlineprotected |
Returns next regular expression for line starting from spos.
Definition at line 84 of file nonogram.cpp.
|
inlinevirtual |
Copy space during cloning.
Definition at line 176 of file nonogram.cpp.
|
inlinevirtual |
Print solution.
Reimplemented from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > >.
Definition at line 182 of file nonogram.cpp.
|
Specification for a heart-shaped picture.
Definition at line 231 of file nonogram.cpp.
|
Specification for a bear/bunny-shaped picture.
Definition at line 256 of file nonogram.cpp.
|
Specification for a crocodile-shaped picture.
Definition at line 284 of file nonogram.cpp.
|
Specification for an unknown picture.
Definition at line 315 of file nonogram.cpp.
|
Specification for a pinwheel-picture.
Definition at line 342 of file nonogram.cpp.
|
Specification for a more difficult picture.
Definition at line 361 of file nonogram.cpp.
|
Specification for a non-unique picture.
Definition at line 398 of file nonogram.cpp.
|
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.
|
From http://www.cs.kuleuven.be/~bmd/nonogram.pl.
Definition at line 482 of file nonogram.cpp.
|
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.
|
Petro.
Definition at line 650 of file nonogram.cpp.
|
Skid.
Definition at line 732 of file nonogram.cpp.
|
Bucks.
Definition at line 778 of file nonogram.cpp.
|
Dancer.
Definition at line 835 of file nonogram.cpp.
|
Cat.
Definition at line 857 of file nonogram.cpp.
|
Edge.
Definition at line 904 of file nonogram.cpp.
|
Knot.
Definition at line 932 of file nonogram.cpp.
|
Swing.
Definition at line 1007 of file nonogram.cpp.
|
Mum.
Definition at line 1105 of file nonogram.cpp.
|
Specification for a heart-shaped picture.
Definition at line 1186 of file nonogram.cpp.
|
Specification for a heart-shaped picture.
Definition at line 1200 of file nonogram.cpp.
|
Main-function.
Definition at line 199 of file nonogram.cpp.
|
protected |
Specification to be used.
Definition at line 70 of file nonogram.cpp.
|
protected |
Fields of board.
Definition at line 72 of file nonogram.cpp.