5.271. polyomino

DESCRIPTIONLINKSGRAPH
Origin

Inspired by [Golomb65].

Constraint

πš™πš˜πš•πš’πš˜πš–πš’πš—πš˜(π™²π™΄π™»π™»πš‚)

Argument
π™²π™΄π™»π™»πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—πš’πš—πšπšŽπš‘-πš’πš—πš,πš›πš’πšπš‘πš-πšπšŸπšŠπš›,πš•πšŽπšπš-πšπšŸπšŠπš›,πšžπš™-πšπšŸπšŠπš›,πšπš˜πš πš—-πšπšŸπšŠπš›
Restrictions
π™²π™΄π™»π™»πš‚.πš’πš—πšπšŽπš‘β‰₯1
π™²π™΄π™»π™»πš‚.πš’πš—πšπšŽπš‘β‰€|π™²π™΄π™»π™»πš‚|
|π™²π™΄π™»π™»πš‚|β‰₯1
πš›πšŽπššπšžπš’πš›πšŽπš(π™²π™΄π™»π™»πš‚,[πš’πš—πšπšŽπš‘,πš›πš’πšπš‘πš,πš•πšŽπšπš,πšžπš™,πšπš˜πš πš—])
πšπš’πšœπšπš’πš—πšŒπš(π™²π™΄π™»π™»πš‚,πš’πš—πšπšŽπš‘)
π™²π™΄π™»π™»πš‚.πš›πš’πšπš‘πšβ‰₯0
π™²π™΄π™»π™»πš‚.πš›πš’πšπš‘πšβ‰€|π™²π™΄π™»π™»πš‚|
π™²π™΄π™»π™»πš‚.πš•πšŽπšπšβ‰₯0
π™²π™΄π™»π™»πš‚.πš•πšŽπšπšβ‰€|π™²π™΄π™»π™»πš‚|
π™²π™΄π™»π™»πš‚.πšžπš™β‰₯0
π™²π™΄π™»π™»πš‚.πšžπš™β‰€|π™²π™΄π™»π™»πš‚|
π™²π™΄π™»π™»πš‚.πšπš˜πš πš—β‰₯0
π™²π™΄π™»π™»πš‚.πšπš˜πš πš—β‰€|π™²π™΄π™»π™»πš‚|
Purpose

Enforce all cells of the collection π™²π™΄π™»π™»πš‚ to be connected and to form one single block. Each cell is defined by the following attributes:

  1. The πš’πš—πšπšŽπš‘ attribute of the cell, which is an integer between 1 and the total number of cells, is unique for each cell.

  2. The πš›πš’πšπš‘πš attribute that is the index of the cell located immediately to the right of that cell (or 0 if no such cell exists).

  3. The πš•πšŽπšπš attribute that is the index of the cell located immediately to the left of that cell (or 0 if no such cell exists).

  4. The πšžπš™ attribute that is the index of the cell located immediately on top of that cell (or 0 if no such cell exists).

  5. 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Β [Golomb72].

Example
πš’πš—πšπšŽπš‘-1πš›πš’πšπš‘πš-0πš•πšŽπšπš-0πšžπš™-2πšπš˜πš πš—-0,πš’πš—πšπšŽπš‘-2πš›πš’πšπš‘πš-3πš•πšŽπšπš-0πšžπš™-0πšπš˜πš πš—-1,πš’πš—πšπšŽπš‘-3πš›πš’πšπš‘πš-0πš•πšŽπšπš-2πšžπš™-4πšπš˜πš πš—-0,πš’πš—πšπšŽπš‘-4πš›πš’πšπš‘πš-5πš•πšŽπšπš-0πšžπš™-0πšπš˜πš πš—-3,πš’πš—πšπšŽπš‘-5πš›πš’πšπš‘πš-0πš•πšŽπšπš-4πšžπš™-0πšπš˜πš πš—-0

The πš™πš˜πš•πš’πš˜πš–πš’πš—πš˜ constraint holds since all the cells corresponding to the items of the π™²π™΄π™»π™»πš‚ collection form one single group of connected cells: the i th (i∈[1,4]) cell is connected to the (i+1) th cell. FigureΒ 5.271.1 shows the corresponding polyomino.

Figure 5.271.1. Polyomino corresponding to the example
ctrs/polyomino1
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.

geometry: geometrical constraint.

puzzles: pentomino.

Arc input(s)

π™²π™΄π™»π™»πš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈ(β‰ )β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŒπšŽπš•πš•πšœ1,πšŒπšŽπš•πš•πšœ2)

Arc arity
Arc constraint(s)
β‹πšŒπšŽπš•πš•πšœ1.πš›πš’πšπš‘πš=πšŒπšŽπš•πš•πšœ2.πš’πš—πšπšŽπš‘βˆ§πšŒπšŽπš•πš•πšœ2.πš•πšŽπšπš=πšŒπšŽπš•πš•πšœ1.πš’πš—πšπšŽπš‘,πšŒπšŽπš•πš•πšœ1.πš•πšŽπšπš=πšŒπšŽπš•πš•πšœ2.πš’πš—πšπšŽπš‘βˆ§πšŒπšŽπš•πš•πšœ2.πš›πš’πšπš‘πš=πšŒπšŽπš•πš•πšœ1.πš’πš—πšπšŽπš‘,πšŒπšŽπš•πš•πšœ1.πšžπš™=πšŒπšŽπš•πš•πšœ2.πš’πš—πšπšŽπš‘βˆ§πšŒπšŽπš•πš•πšœ2.πšπš˜πš πš—=πšŒπšŽπš•πš•πšœ1.πš’πš—πšπšŽπš‘,πšŒπšŽπš•πš•πšœ1.πšπš˜πš πš—=πšŒπšŽπš•πš•πšœ2.πš’πš—πšπšŽπš‘βˆ§πšŒπšŽπš•πš•πšœ2.πšžπš™=πšŒπšŽπš•πš•πšœ1.πš’πš—πšπšŽπš‘
Graph property(ies)
β€’ 𝐍𝐕𝐄𝐑𝐓𝐄𝐗=|π™²π™΄π™»π™»πš‚|
β€’ 𝐍𝐂𝐂=1

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 𝐍𝐂𝐂=1 enforces to have one single group of connected cells.

PartsΒ (A) andΒ (B) of FigureΒ 5.271.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.271.2. Initial and final graph of the πš™πš˜πš•πš’πš˜πš–πš’πš—πš˜ constraint
ctrs/polyominoActrs/polyominoB
(a) (b)
Signature

From the graph property 𝐍𝐕𝐄𝐑𝐓𝐄𝐗=|π™²π™΄π™»π™»πš‚| and from the restriction |π™²π™΄π™»π™»πš‚|β‰₯1 we have that the final graph is not empty. Therefore it contains at least one connected component. So we can rewrite 𝐍𝐂𝐂=1 to 𝐍𝐂𝐂≀1 and simplify 𝐍𝐂𝐂 Β― Μ² to 𝐍𝐂𝐂 Μ².