Pentominoes Class Reference
[Scripts for problems]
Inherits Example.
Detailed Description
Example: Pentominoes
The Problem
This example places pieces of a puzzle, where each piece is composed of a collection of squares, onto a grid. The pieces may all be rotated and flipped freely. The goal is to place all the pieces on the grid, without any overlaps. An example piece to be placed looks likeXXX X XXX
The most famous instance of such a puzzle is the Pentominoes puzzle, where the pieces are all pieces formed by 5 fourconnected squares.
The Variables
The variables for the model is the grid of squares that the pieces are placed on, where each of the variables for the squares takes the value of the number of the piece which is placed overonto it.Placing one piece
The constraint for each piece placement uses regular expressions (and consequently the extensional constraint) for expressing placement of (rotated) pieces on the grid. Consider the simple example of placing the pieceXX X X
0123 4567 89AB CDEF
Let the variables 0F be 0/1variables indicating if the piece is placed on that position or not. First consider placing the piece on some location, say covering 1,2,6, and A. Then, writing the sequence of values for the variables 0F out, we get the string 0110001000100000. This string and all other strings corresponding to placing the above piece in that particular rotation can be described using the regular expression . The expression indicates that first comes some number of zeroes, then two ones in a row (covering places 1 and 2 in our example placement), then comes exactly three 0's (not covering places 3, 4, and 5), and so on. The variable number of 0's at the beginning and at the end makes the expression match any placement of the piece on the board.
There is one problem with the above constraint, since it allows placing the piece covering places 3, 4, 8, and C. That is, the piece may wrap around the board. To prohibit this, we add a new dummycolumn to the board, so that it looks like
0123G 4567H 89ABI CDEFJ
Rotating pieces
To handle rotations of the piece, we can use disjunctions of regular expressions for all the relevant rotations. Consider the rotated version of the above piece, depicted below.X XXX
There are 8 symmetries for the pieces in general. The 8 disjuncts for a particular piece might, however, contain less than 8 distinct expressions (for example, any square has only one distinct disjunct). This is removed when then automaton for the expression is computed, since it is minimized.
Placing several pieces
To generalize the above model to several pieces, we let the variables range from 0 to n, where n is the number of pieces to place. Given that we place three pieces, and that the above shown piece is number one, we will replace each expression with the expression . Thus, the second regular expression becomes . Additionaly, the end of line marker gets its own value.This generalization suffers from the fact that the automata become much more complex. This problem can be solved by instead projecting out each component, which gives a new board of 0/1variables for each piece to place.
The Branching
This model does not use any advanced heuristic for the branching. The variables selection is simply in order, and the value selection is minimum value first.The static value selection allows us to order the pieces in the specification of the problem. The pieces are approximately ordered by largness or hardness to place.
Removing board symmetries
Especially when searching for all solutions of a puzzle instance, we might want to remove the symmetrical boards from the solutionsspace. This is done using the same symmetry functions as for the piece symmetries and lexicographical order constraints.Definition at line 260 of file pentominoes.cc.
Puzzle specifications  
const TileSpec *  examples [] 
Board specifications.  
const int  examples_size [] 
Board specification sizes.  
static const TileSpec  puzzle0 [] 
Small specification.  
static const TileSpec  puzzle1 [] 
Standard specification.  
static const TileSpec  square2 [] 
Board specifications.  
static const TileSpec  square3 [] 
Board specifications.  
static const TileSpec  pentomino6x10 [] 
Board specifications.  
static const TileSpec  pentomino5x12 [] 
Board specifications.  
static const TileSpec  pentomino4x15 [] 
Board specifications.  
static const TileSpec  pentomino3x20 [] 
Board specifications.  
const unsigned  n_examples = sizeof(examples)/sizeof(TileSpec*) 
Number of specifications.  
const TileSpec *  examples [] 
List of specifications.  
const int  examples_size [] 
Board specifications.  
Symmetry functions  
These functions implement the 8 symmetries of 2D planes. The functions are templatized so that they can be used both for the pieces (defined using Cstrings) and for arrays of variables.  
typedef void(*  tsymmfunc )(const char *, int, int, char *, int &, int &) 
Type for tile symmetry functions.  
typedef void(*  bsymmfunc )(const IntVarArgs, int, int, IntVarArgs &, int &, int &) 
Type for board symmetry functions.  
int  pos (int h, int w, int h1, int w1) 
template<class CArray, class Array>  
void  id (CArray t1, int w1, int h1, Array t2, int &w2, int &h2) 
Identity symmetry.  
template<class CArray, class Array>  
void  rot90 (CArray t1, int w1, int h1, Array t2, int &w2, int &h2) 
Rotate 90 degrees.  
template<class CArray, class Array>  
void  rot180 (CArray t1, int w1, int h1, Array t2, int &w2, int &h2) 
Rotate 180 degrees.  
template<class CArray, class Array>  
void  rot270 (CArray t1, int w1, int h1, Array t2, int &w2, int &h2) 
Rotate 270 degrees.  
template<class CArray, class Array>  
void  flipx (CArray t1, int w1, int h1, Array t2, int &w2, int &h2) 
Flip xwise.  
template<class CArray, class Array>  
void  flipy (CArray t1, int w1, int h1, Array t2, int &w2, int &h2) 
Flip ywise.  
template<class CArray, class Array>  
void  flipd1 (CArray t1, int w1, int h1, Array t2, int &w2, int &h2) 
Flip diagonal 1.  
template<class CArray, class Array>  
void  flipd2 (CArray t1, int w1, int h1, Array t2, int &w2, int &h2) 
Flip diagonal 2.  
Public Types  
enum  { PROPAGATION_INT, PROPAGATION_BOOLEAN } 
Choice of propagators. More...  
enum  { MODEL_NONE, MODEL_SYMMETRY } 
Choice of symmetry breaking. More...  
Public Member Functions  
Pentominoes (const SizeOptions &opt)  
Construction of the model.  
Pentominoes (bool share, Pentominoes &s)  
Constructor for cloning s.  
virtual Space *  copy (bool share) 
Copy space during cloning.  
virtual void  print (std::ostream &os) 
Print solution.  
Related Functions  
(Note that these are not member functions.)  
const unsigned int  n_examples 
Number of board specifications. 
Member Enumeration Documentation
anonymous enum 
anonymous enum 
Choice of symmetry breaking.
 Enumerator:

MODEL_NONE Do not remove symmetric solutions. MODEL_SYMMETRY Remove symmetric solutions.
Definition at line 268 of file pentominoes.cc.
Constructor & Destructor Documentation
Pentominoes::Pentominoes  (  const SizeOptions &  opt  )  [inline] 
Pentominoes::Pentominoes  (  bool  share,  
Pentominoes &  s  
)  [inline] 
Member Function Documentation
virtual Space* Pentominoes::copy  (  bool  share  )  [inline, virtual] 
virtual void Pentominoes::print  (  std::ostream &  os  )  [inline, virtual] 
Friends And Related Function Documentation
Initial value:
Board specifications.List of specifications.
Each board specification repurposes the first two TileSpecs to record width and height of the board (TileSpec 0) as well as the number of tiles and whether the board is filled (TileSpec 1).
Definition at line 67 of file pentominoes.cc.
const int examples_size[] [related] 
Initial value:
{sizeof(puzzle0)/sizeof(TileSpec), sizeof(puzzle1)/sizeof(TileSpec), sizeof(square2)/sizeof(TileSpec), sizeof(square3)/sizeof(TileSpec), sizeof(pentomino6x10)/sizeof(TileSpec), sizeof(pentomino5x12)/sizeof(TileSpec), sizeof(pentomino4x15)/sizeof(TileSpec), sizeof(pentomino3x20)/sizeof(TileSpec)}
Definition at line 72 of file pentominoes.cc.
const unsigned int n_examples [related] 
typedef void(* tsymmfunc)(const char *, int, int, char *, int &, int &) [related] 
typedef void(* bsymmfunc)(const IntVarArgs, int, int, IntVarArgs &, int &, int &) [related] 
Initial value:
{ {4, 4, true, ""}, {2, 3, 1, "XX" "X " "X "}, {2, 1, 1, "XX"}, {3, 3, 1, " XX" " X" "XXX"}, {1, 1, 1, "X"}, {3, 1, 1, "XXX"} }
Definition at line 506 of file pentominoes.cc.
Initial value:
{ {10, 10, true, ""}, {6, 6, 1, "XXXXXX" "XXXXXX" "XXXXXX" "XXXXXX" "XXXXXX" "XXXXXX" }, {4, 4, 3, "XXXX" "XXXX" "XXXX" "XXXX"}, {2, 2, 4, "XX" "XX"} }
List of specifications.
Each board specification repurposes the first two TileSpecs to record width and height of the board (TileSpec 0) as well as the number of tiles and whether the board is filled (TileSpec 1).
Definition at line 576 of file pentominoes.cc.
Board specifications.
List of specifications.
Each board specification repurposes the first two TileSpecs to record width and height of the board (TileSpec 0) as well as the number of tiles and whether the board is filled (TileSpec 1).
Definition at line 599 of file pentominoes.cc.
const TileSpec pentomino6x10[] [related] 
Board specifications.
List of specifications.
Each board specification repurposes the first two TileSpecs to record width and height of the board (TileSpec 0) as well as the number of tiles and whether the board is filled (TileSpec 1).
Definition at line 656 of file pentominoes.cc.
const TileSpec pentomino5x12[] [related] 
Board specifications.
List of specifications.
Each board specification repurposes the first two TileSpecs to record width and height of the board (TileSpec 0) as well as the number of tiles and whether the board is filled (TileSpec 1).
Definition at line 708 of file pentominoes.cc.
const TileSpec pentomino4x15[] [related] 
Board specifications.
List of specifications.
Each board specification repurposes the first two TileSpecs to record width and height of the board (TileSpec 0) as well as the number of tiles and whether the board is filled (TileSpec 1).
Definition at line 760 of file pentominoes.cc.
const TileSpec pentomino3x20[] [related] 
Board specifications.
List of specifications.
Each board specification repurposes the first two TileSpecs to record width and height of the board (TileSpec 0) as well as the number of tiles and whether the board is filled (TileSpec 1).
Definition at line 812 of file pentominoes.cc.
const unsigned n_examples = sizeof(examples)/sizeof(TileSpec*) [related] 
int pos  (  int  h,  
int  w,  
int  h1,  
int  w1  
)  [related] 
Return index of (h, w) in the rowmajor layout of a matrix with width w1 and height h1.
Definition at line 883 of file pentominoes.cc.
void id  (  CArray  t1,  
int  w1,  
int  h1,  
Array  t2,  
int &  w2,  
int &  h2  
)  [related] 
void rot90  (  CArray  t1,  
int  w1,  
int  h1,  
Array  t2,  
int &  w2,  
int &  h2  
)  [related] 
void rot180  (  CArray  t1,  
int  w1,  
int  h1,  
Array  t2,  
int &  w2,  
int &  h2  
)  [related] 
void rot270  (  CArray  t1,  
int  w1,  
int  h1,  
Array  t2,  
int &  w2,  
int &  h2  
)  [related] 
void flipx  (  CArray  t1,  
int  w1,  
int  h1,  
Array  t2,  
int &  w2,  
int &  h2  
)  [related] 
void flipy  (  CArray  t1,  
int  w1,  
int  h1,  
Array  t2,  
int &  w2,  
int &  h2  
)  [related] 
void flipd1  (  CArray  t1,  
int  w1,  
int  h1,  
Array  t2,  
int &  w2,  
int &  h2  
)  [related] 
void flipd2  (  CArray  t1,  
int  w1,  
int  h1,  
Array  t2,  
int &  w2,  
int &  h2  
)  [related] 
const int examples_size  (  )  [related] 
Board specifications.
List of specifications.
Each board specification repurposes the first two TileSpecs to record width and height of the board (TileSpec 0) as well as the number of tiles and whether the board is filled (TileSpec 1).
Definition at line 868 of file pentominoes.cc.
The documentation for this class was generated from the following file:
 examples/pentominoes.cc (Revision: 5861)