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. | |
![]() | |
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 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) |
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.
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.
Return width of board.
Definition at line 75 of file nonogram.cpp.
Return height of board.
Definition at line 79 of file nonogram.cpp.
Returns next regular expression for line starting from spos.
Definition at line 84 of file nonogram.cpp.
Copy space during cloning.
Definition at line 176 of file nonogram.cpp.
Print solution.
Reimplemented from Gecode::Driver::ScriptBase< BaseSpace >.
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.
Specification to be used.
Definition at line 70 of file nonogram.cpp.
|
protected |
Fields of board.
Definition at line 72 of file nonogram.cpp.