5.324. polyomino
| DESCRIPTION | LINKS | GRAPH |
- Origin
Inspired by [Golomb65].
- Constraint
- Argument
- Restrictions
- Purpose
Enforce all cells of the collection to be connected and to form a single block. Each cell is defined by the following attributes:
The attribute of the cell, which is an integer between 1 and the total number of cells, is unique for each cell.
The attribute that is the index of the cell located immediately to the right of that cell (or 0 if no such cell exists).
The attribute that is the index of the cell located immediately to the left of that cell (or 0 if no such cell exists).
The attribute that is the index of the cell located immediately on top of that cell (or 0 if no such cell exists).
The attribute that is the index of the cell located immediately above that cell (or 0 if no such cell exists).
This corresponds to a polyominoΒ [Golomb65].
- Example
-
The constraint holds since all the cells corresponding to the items of the collection form one single group of connected cells: the () cell is connected to the cell. FigureΒ 5.324.1 shows the corresponding polyomino.
Figure 5.324.1. Polyomino corresponding to the Example slot where each cell contains the index of the corresponding item within the collection
- Symmetries
Items of are permutable.
Attributes of are permutable w.r.t. permutation (permutation applied to all items).
Attributes of are permutable w.r.t. permutation (permutation applied to all items).
Attributes of are permutable w.r.t. permutation (permutation applied to all items).
- Usage
Enumeration of polyominoes.
- Keywords
combinatorial object: pentomino.
final graph structure: strongly connected component.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
The graph constraint models the fact that all the cells are connected. We use the arc generator in order to only consider connections between two distinct cells. The first graph property avoid the case isolated cells, while the second graph property enforces to have a single group of connected cells.
PartsΒ (A) andΒ (B) of FigureΒ 5.324.2 respectively show the initial and final graph associated with the Example slot. Since we use the graph property the vertices of the final graph are stressed in bold. Since we also use the graph property we show the unique connected component of the final graph. An arc between two vertices indicates that two cells are directly connected.
Figure 5.324.2. Initial and final graph of the constraint
(a) (b) - Signature
From the graph property and from the restriction we have that the final graph is not empty. Therefore it contains at least one connected component. So we can rewrite to and simplify to .