Why this note exists

Chapter 8’s configurational pipeline generates an arrangement and packing search space from four atomic module items using a grammar whose stored sources deduplicate arrangements by the four-rotation subgroup (the generator’s D4 flag; rotation-canonical, one-sided in Golomb’s classification) and packings by the full eight-element dihedral group of the square (the generator’s D8 flag). The generator implements a partial realisation of the Plans Generator formal specification: dihedral canonicalisation, four-neighbour adjacency, and edge-run attachment are confirmed implemented; composite-join semantics, port-attachment expressions, and reference modifiers are not parsed in the current generator. A second finding is that at least 100 unique dihedral-canonical packings exist on the 8×12 boundary.

Without literature context, three objections arise: (a) the canonicalisation procedure is not grounded in a recognised combinatorial framework; (b) the partial-grammar characterisation is an admission of incompleteness that undermines the finding rather than bounds it; (c) the 100-packing limit makes the coverage finding uninformative because the upper bound of the search space is unquantified. This note addresses all three by situating the generator in the polyomino combinatorics tradition (Golomb 1954/1994; Redelmeier 1981; Klarner 1965), the dihedral group symmetry framework (Burnside’s lemma; the four-rotation subgroup and the full eight-element dihedral group of the square), and the shape-grammar literature (Stiny 1975, 1980; Stiny and Gips 1972).

1. Polyomino combinatorics: classification, enumeration, and symmetry equivalence

1.1 Golomb’s foundational classification

The term polyomino was coined by Solomon Golomb in a 1954 paper and developed in his 1965 monograph, revised as Polyominoes: Puzzles, Patterns, Problems, and Packings in 1994.¹ A polyomino of order n (an n-omino) is a connected set of n unit squares in the plane arranged such that each square shares at least one full edge with at least one other square: the 4-neighbour adjacency condition used throughout Chapter 8. Golomb’s classification introduces three equivalence classes that are directly instantiated in the Plans Generator:

• Fixed polyominoes: distinct under translation only; two polyominoes are the same fixed polyomino only if they occupy exactly the same set of unit cells in the grid. This is the richest class (most distinct pieces) and corresponds to the pre-canonicalisation representation in the arrangement generator.
• One-sided polyominoes: distinct under translation and rotation; reflections are not identified. This is the equivalence class implemented by the arrangement generator’s deduplication: its stored source enables the four rotations and disables mirror transforms, so two arrangements are identified only when one is a rotation of the other.
• Free polyominoes: distinct under translation, rotation, and reflection: the full eight-element dihedral symmetry group of the square. This is the equivalence class implemented by the packing generator’s D8 deduplication: two packings are equivalent if and only if one is a rotation or reflection of the other, and the lexicographically smallest normalised cell tuple selects the canonical representative.

For 4-cell polyominoes (tetrominoes), Golomb’s enumeration gives: 5 free tetrominoes, 7 one-sided tetrominoes, and 19 fixed tetrominoes.² The 50 unique rotation-canonical arrangements produced by the arrangement generator from four atomic items are not tetrominoes in Golomb’s sense; they are arrangements of four labelled items on a grid, where the labelling distinguishes pieces that Golomb would count as equivalent. The 50 count reflects the much larger enumeration space when piece identity is preserved, which is the appropriate representation for a module planning system where each item has a distinct function (bedroom, living, kitchen, etc.).

1.2 Redelmeier’s enumeration algorithm

The systematic enumeration of polyominoes to high orders is due to Redelmeier (1981), who demonstrated an algorithm for enumerating fixed polyominoes by sequential cell addition.³ The Redelmeier algorithm proceeds by: (1) placing a single cell at the origin; (2) at each step, adding one cell to any position 4-adjacent to the current polyomino that has not previously been considered; (3) recording each resulting connected configuration as a distinct fixed polyomino; (4) applying the chosen symmetry group to deduplicate. This is structurally analogous to the arrangement generator’s search procedure: begin with a seed configuration, extend by valid attachment, record unique D4-canonical representatives.

The key insight from Redelmeier for Chapter 8 is that the 4-neighbour adjacency constraint constitutes the defining property of polyomino connectivity, rather than a restriction introduced by the Plans Generator grammar. Any generator that produces connected configurations of unit squares by sequential attachment automatically satisfies the 4-neighbour condition; the grammar’s explicit statement of this condition in the Specification is a formalisation of an implicit polyomino constraint, not an additional restriction.

1.3 Klarner’s growth bound and the upper-bound problem

Klarner (1965) established the exponential growth of polyomino counts. The number of free n-ominoes grows as λⁿ up to sub-exponential factors, where λ, Klarner’s constant, is not known exactly: Klarner and Rivest (1973) proved the upper bound λ ≤ 4.6496, the proven lower bound now exceeds 4 (λ ≥ 4.0025, Barequet, Rote, and Shalah 2016), and numerical estimates place λ near 4.0626.^{4 5 6} For Chapter 8’s purposes, these bounds confirm that the D8-canonical search space for four-item packings on an 8×12 boundary is exponentially large but finite. The 100-packing limit terminates the enumeration at a confirmed lower bound, at least 100 unique D8-canonical packings exist, without claiming to have reached the upper boundary of the search space. This is a sound scientific position: the limit restricts the finding to what was actually enumerated, not what could in principle exist.

The absence of an exhaustive upper-bound cardinality for the 8×12 D8-canonical packing space is acknowledged as a declared limitation of the lower-bound finding. The exponential growth provides the theoretical justification for why exhaustive enumeration was not performed: the search space grows super-polynomially with the number of items and the boundary size, making exhaustive enumeration computationally intractable for the current generator without dedicated pruning strategies.

2. Dihedral symmetry groups: D4, D8, and canonical representation

2.1 The dihedral group D4 as the symmetry group of the square

The symmetry group of the square is the dihedral group D4 (sometimes written D_8 in the convention that D_n has order 2n: a notational ambiguity addressed below).⁷ In the Plans-Generator Specification’s convention, D4 comprises four rotations (0°, 90°, 180°, 270°) and four reflective operations (horizontal flip, vertical flip, and two diagonal flips), giving an 8-element symmetry group, and the Specification mandates deduplication by translation and this full group. The packing generator implements exactly that: the canonical representative is selected by applying the group elements, normalising each result (translating so the minimum x and y coordinates are both 0), and selecting the lexicographically smallest normalised cell tuple. The stored arrangement source departs from the mandate in one respect: its mirror transforms are disabled, so arrangement canonicalisation applies the four-rotation subgroup only, and its 50 canonical outputs are one-sided rather than free representatives. A check over the deposited run register (arrangement-permutations-2510262139.json) shows no two of the 50 are mirror-equivalent, so the retained set happens to be distinct under the full group as well.

This canonicalisation procedure is a direct application of Burnside’s lemma to the enumeration of distinct arrangements:⁸ the number of distinct arrangements equals the number of orbits of the acting symmetry group on the set of all fixed arrangements. Each orbit is represented by exactly one canonical element (the lexicographically smallest normalised tuple), so the 100 packings are orbit representatives under the full 8-element group and the 50 arrangements are orbit representatives under its four-rotation subgroup.

2.2 D8 canonicalisation for packing deduplication

The packing generator’s deduplication flag is labelled D8, and its enabled setting applies the full 8-element symmetry group: the four rotations, plus the mirror reflection and the mirror’s rotations, which together generate all four reflective operations.⁹ The distinction between the generator’s two flag settings is therefore a difference in group order, the four-rotation subgroup against the full eight operations, not a difference in which eight operations are applied. The packing run used the full-group setting, so packing deduplication implements free-polyomino equivalence over the labelled tile set; the arrangement run, with mirror transforms disabled, implements one-sided equivalence (Section 2.1).

The generator-verification audit G-V-01 (the D8-canonicalisation implementation audit) confirmed that D8 canonicalisation is correctly implemented in the packing generator: all 100 packings in the confirmed run are unique under the D8 equivalence relation, and the implementation matches the Plans Generator specification.

2.3 Burnside’s lemma and the lower-bound counting argument

The formal justification for the lower-bound finding draws on Burnside’s lemma in the following sense: if 100 distinct packings exist in the D8-canonical orbit enumeration, and the enumeration algorithm is a correct implementation of D8 canonicalisation (confirmed by the implementation audit), then the D8-canonical search space contains at least 100 distinct elements. The generator was halted at 100 not because the search space was exhausted but because the 100-packing limit was reached, a decision recorded as declared scope limit SL-03 (the configurational cap of 100 packings / 50 arrangements is a permanent enumeration bound, not a claim of search-space exhaustion). No claim is made about the total cardinality of the D8-canonical search space; the Klarner bound confirms it is strictly greater than 100 for four-item configurations on an 8×12 boundary.

3. Shape grammars and the theoretical precursor to the Plans Generator

3.1 Stiny and Gips: the formal grammar of spatial form

The Plans Generator grammar is a descendant of the shape grammar formalism introduced by George Stiny and James Gips in 1972 and developed by Stiny through the late 1970s and early 1980s.^{10 11} A shape grammar defines a formal language of spatial designs through rewriting rules that replace labelled shape elements with new configurations. Each rule has the form u → v where u is a recogniser shape (a pattern to be matched in the current design) and v is a replacement shape (the new configuration to be substituted). Applying rules in sequence generates a design; applying different rule sequences from the same initial shape generates different designs; the grammar defines the set of all designs generatable by the rule set.

The Plans Generator grammar, as specified in the Plans Generator specification, instantiates this framework with four specific rule types:

1. D4/D8 canonicalisation rules: equivalence classes rather than production rules; they specify the symmetry orbit by which outputs are deduplicated (the four-rotation subgroup for arrangements in the stored source; the full eight-element dihedral group for packings). No equivalent in Stiny’s original formalism; this is an enumeration-management rule specific to the Plans Generator’s computational architecture.
2. 4-neighbour adjacency rules: cell-level production rules requiring that any new cell added to an arrangement shares at least one full edge with an existing cell. This is equivalent to Stiny’s adjacency shape rule applied at the unit-cell level.
3. Edge-run attachment rules: the specific grammar construct that requires new module items to attach to the existing arrangement via a shared edge-run (a sequence of aligned cell edges). This is a higher-level production rule operating on the boundary of the existing configuration rather than on individual cells alone: a departure from Golomb’s unconstrained cell-addition that makes the Plans Generator grammar more restrictive than free polyomino enumeration.
4. Composite-join semantics (not implemented in v2): rules that govern how two separate arrangement blocks join at a boundary, preserving alignment and connectivity. These correspond to Stiny’s junction rules in architectural shape grammars.¹²

3.2 The partial-grammar framing as a declared limitation

The implemented grammar is declared limited because the generator implements only three of the four rule types in the specification: canonicalisation (D8 ✓), adjacency (4-neighbour ✓), and attachment (edge-run ✓); but not composite-join semantics (✗), port-attachment expressions (✗), or reference modifiers (✗). In the shape-grammar literature, this situation is well-recognised: partial grammar implementations generate a superset of the valid designs (by omitting constraining rules) or a subset of the valid designs (by omitting generative rules), depending on whether the omitted rules are restrictive or productive.

For Chapter 8, the missing composite-join, port-attachment, and reference rules are primarily restrictive: they would eliminate from the 100 D8-canonical packings those that violate alignment or port conventions. This means the generator’s 100-packing output is a superset of what the full grammar would generate: some of the 100 packings would be filtered out by the missing rules. The lower-bound finding (“at least 100 unique D8-canonical packings”) is therefore conservative in the correct direction: the full grammar would produce a subset of the generator’s output, confirming that at least some (but possibly fewer than 100) packings satisfy the full specification.

This reasoning mirrors the classical underconstrained/overconstrained duality in formal language theory:¹³ the implemented grammar is underconstrained relative to the full specification, generating a superset language. The partial-grammar declaration is thus not an admission of failure but a precise statement of the direction of the approximation, which supports rather than undermines the implementation and lower-bound findings when read correctly.

3.3 Edge-run attachment as a restricted growth rule

The edge-run attachment rule, requiring that new module items attach to the existing arrangement via a shared run of aligned cell edges, is a spatial restriction that is not present in standard polyomino enumeration. Its closest analogue in the combinatorics literature is the concept of a restricted growth function in combinatorial pattern theory:¹⁴ a generation rule that permits new elements only in configurations that satisfy a specified relation to existing elements. Edge-run attachment is a spatial restricted growth rule: a new module item can only be added in a position where its boundary aligns with at least one full edge-run of the existing arrangement, which is a stronger condition than 4-neighbour adjacency alone (4-neighbour requires only a single shared edge; edge-run requires a shared run of aligned edges).

The practical effect of this restriction in the Plans Generator is that it prohibits configurations where modules touch at a single corner or at non-aligned boundaries: configurations that would be valid 4-neighbour polyominoes but that would produce physically incoherent spatial arrangements (modules that abut only at a point or at offset edges, creating irresolvable structural junctions). This is a domain-grounded restriction that places the Plans Generator grammar between unconstrained polyomino enumeration and the fully-constrained architectural grammar of the complete Specification.

4. Grammar partial realisation and confidence assessment

4.1 The implementation finding: high confidence despite partial implementation

The implementation finding (confirmed but declared-limited) reflects the following logic: the three implemented rule types (D8 canonicalisation, 4-neighbour adjacency, and edge-run attachment) are the core enumeration infrastructure of the Plans Generator. They are sufficient to generate a well-defined, reproducible search space of D8-canonical configurations. The missing rules (composite-join, port-attachment, reference modifiers) are constraint additions that would filter this space but not create new valid configurations that the implemented rules could not reach.

The implementation audit confirmed D8 canonicalisation and edge-run attachment are correctly implemented. The 4-neighbour adjacency condition is trivially confirmed by the architecture of the generator (only adjacent cells can be added in any step). Confidence in the implementation finding is high because the finding is that these three rules are implemented, and they are confirmed implemented. The declared-limitation annotation is a scope statement, not a confidence reduction: it bounds the finding to what the generator actually does, not what the full grammar would do.

4.2 The lower-bound finding: high confidence at the lower bound

The lower-bound finding, “at least 100 unique D8-canonical packings exist on the 8×12 boundary”, is high confidence because the evidence is direct: 100 D8-canonical packings are confirmed by direct inspection of the run output, and the implementation audit confirmed that the packing generator correctly implements D8 canonicalisation. The 100-packing limit does not weaken this finding; it establishes the finding’s lower-bound nature. The confidence concerns the finding as stated, and as stated it is verifiable and verified.

The configurational efficiency statistics (the corner efficiency index CEI, mean 0.9353, SD 0.011; the enclosure efficiency index EEI, mean 0.5648, SD 0.049; the bounding efficiency index BEI, mean 0.6078, SD 0.058) provide additional characterisation of the 100-packing corpus without adding new findings that would require separate confidence assessment. These statistics are descriptive of the confirmed 100-packing set and inherit the lower-bound finding’s high confidence rating.

5. Summary of literature grounding

Citation ledger

1. Golomb, S. W. (1994). Polyominoes: Puzzles, Patterns, Problems, and Packings (2nd ed.). Princeton University Press.
2. Redelmeier, D. H. (1981). Counting polyominoes: yet another attack. Discrete Mathematics 36(2): 191-203. DOI: 10.1016/0012-365X(81)90237-5.
3. Klarner, D. A. (1965). Cell growth problems. Canadian Journal of Mathematics 17: 851-863. DOI: 10.4153/CJM-1965-083-5.
4. Klarner, D. A. and Rivest, R. L. (1973). A procedure for improving the upper bound for the number of n-ominoes. Canadian Journal of Mathematics 25(3): 585-602. DOI: 10.4153/CJM-1973-060-4.
5. Weyl, H. (1952). Symmetry. Princeton University Press.
6. Burnside, W. (1897). Theory of Groups of Finite Order. Cambridge University Press.
7. Stiny, G. and Gips, J. (1972). Shape grammars and the generative specification of painting and sculpture. Information Processing 71: 1460-1465.
8. Stiny, G. (1975). Pictorial and Formal Aspects of Shape and Shape Grammars. Birkhäuser.
9. Stiny, G. (1980). Kindergarten grammars: designing with Froebel’s building gifts. Environment and Planning B: Planning and Design 7(4): 409-462. DOI: 10.1068/b070409.
10. Chomsky, N. (1956). Three models for the description of language. IRE Transactions on Information Theory 2(3): 113-124. DOI: 10.1109/TIT.1956.1056813.
11. Knuth, D. E. (2011). The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley.