Generated on Sat Nov 11 01:12:18 2006 for Gecode by doxygen 1.5.1

PicturePuzzle Class Reference
[Example scripts (models)]

Inherits Example.

List of all members.

Detailed Description

Example: Picture puzzles

This example solves picture-puzzles. A picture-puzzle 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.

Picture puzzles are also called Nonograms.

Problem 12 at http://www.csplib.org/.

Definition at line 44 of file picture-puzzle.cc.

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.

static const int heart []
 Specification for a heart-shaped picture.
static const int bear []
 Specification for a bear/bunny-shaped picture.
static const int crocodile []
 Specification for a crocodile-shaped picture.
static const int unknown []
 Specification for an unknown picture.
static const int pinwheel []
 Specification for a pinwheel-picture.
static const int difficult []
 Specification for a more difficult picture.
static const int non_unique []
 Specification for a non-unique picture.
static const int dragonfly []
 Specification for a dragonfly-picture.
static const int p200 []
 Specification for a picture of a flower.
const int * specs []
 List of specifications.
const unsigned n_examples = sizeof(specs)/sizeof(int*)
 Number of specifications.

Public Member Functions

 PicturePuzzle (const Options &o)
 Construction of the model.
 PicturePuzzle (bool share, PicturePuzzle &s)
 Constructor for cloning s.
virtual Space * copy (bool share)
 Copy space during cloning.
virtual void print (void)
 Print solution.

Constructor & Destructor Documentation

PicturePuzzle::PicturePuzzle ( const Options &  o  )  [inline]

Construction of the model.

Definition at line 76 of file picture-puzzle.cc.

PicturePuzzle::PicturePuzzle ( bool  share,
PicturePuzzle &  s 
) [inline]

Constructor for cloning s.

Definition at line 103 of file picture-puzzle.cc.

Member Function Documentation

virtual Space* PicturePuzzle::copy ( bool  share  )  [inline, virtual]

Copy space during cloning.

Implements Gecode::Space.

Definition at line 110 of file picture-puzzle.cc.

virtual void PicturePuzzle::print ( void   )  [inline, virtual]

Print solution.

Reimplemented from Example.

Definition at line 116 of file picture-puzzle.cc.

Friends And Related Function Documentation

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 163 of file picture-puzzle.cc.

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 188 of file picture-puzzle.cc.

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 216 of file picture-puzzle.cc.

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 247 of file picture-puzzle.cc.

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 274 of file picture-puzzle.cc.

const int difficult[] [related]

Specification for a more difficult picture.

Definition at line 293 of file picture-puzzle.cc.

const int non_unique[] [related]

Specification for a non-unique picture.

Definition at line 330 of file picture-puzzle.cc.

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 367 of file picture-puzzle.cc.

const int p200[] [related]

Specification for a picture of a flower.

From http://www.icparc.ic.ac.uk/eclipse/examples/nono.ecl.txt, the hardest instance.

Definition at line 418 of file picture-puzzle.cc.

const int* specs[] [related]

Initial value:

 {heart, bear, crocodile, unknown,
                      pinwheel, difficult, non_unique, dragonfly, p200}
List of specifications.

Definition at line 475 of file picture-puzzle.cc.

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

Number of specifications.

Definition at line 478 of file picture-puzzle.cc.

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