Why this note exists

Chapter 8’s configurational pipeline generates an arrangement and packing search space from four atomic module items using a grammar that enforces D4-canonical deduplication of arrangements and D8-canonical deduplication of packings. CL-8-06 declares that the generator implements a partial realisation of the Plans Generator formal specification: D8 canonicalisation, 4-neighbour adjacency, and edge-run attachment are confirmed implemented; composite-join semantics, port-attachment expressions, and Ref modifiers are not parsed in the v2 generator. CL-8-07 declares that at least 100 unique D8-canonical packings exist on the 8×12 boundary.

Without literature context, three objections arise: (a) the D4/D8 canonicalisation procedure is not grounded in a recognised combinatorial framework; (b) the partial-grammar characterisation is an admission of incompleteness that undermines the claim rather than bounds it; (c) the 100-packing cap (SL-03) makes the coverage claim 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; D4 and D8 as subgroups of the symmetry 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 would correspond to a D4-rotational equivalence (4 rotations) without the 2 reflective symmetries.
• Free polyominoes: distinct under translation, rotation, and reflection — the full dihedral symmetry group D4 (for arrangements on a square lattice). This is the equivalence class implemented by the D4-canonical deduplication in Chapter 8’s arrangement generator (run [2510262139]): two arrangements are the same free polyomino 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 D4-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 an exponential growth bound for the number of polyominoes: the number of free n-ominoes grows no faster than approximately 4.0^n (with subsequent work tightening the upper constant to approximately 4.06 per Klarner and Rivest 1973).^{4 5} For Chapter 8’s purposes, the Klarner bound confirms that the D8-canonical search space for four-item packings on an 8×12 boundary is exponentially large but finite. The 100-packing cap (SL-03) 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: SL-03 is a permanent scope limit that restricts the claim 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 in CL-8-07 (DECLARED-LIMITED). The Klarner bound 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 v2 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 arrangement generator’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. Two arrangements are D4-equivalent if and only if one can be obtained from the other by any element of this 8-element group. The canonical representative is selected by applying all 8 group elements to the arrangement, normalising each result (translating so the minimum x and y coordinates are both 0), and selecting the lexicographically smallest normalised cell tuple.

This canonicalisation procedure is a direct application of Burnside’s lemma to the enumeration of distinct arrangements:⁷ the number of distinct free arrangements equals the number of orbits of the symmetry group acting on the set of all fixed arrangements. Each orbit is represented by exactly one canonical element (the lexicographically smallest normalised tuple), ensuring that the 50 D4-canonical arrangements produced by run [2510262139] contain no duplicates.

2.2 D8 canonicalisation for packing deduplication

The packing generator extends D4 canonicalisation to D8 canonicalisation by adding an additional reflection — specifically, the reflection about the boundary’s long axis — to account for the asymmetric 8×12 boundary.⁸ The distinction between D4 and D8 canonicalisation in the Plans Generator is thus not a difference in group order (both are 8-element groups) but a difference in which 8 symmetry operations are applied: D4-canonical deduplication uses the 4 rotations + 4 reflections of the square; D8-canonical deduplication uses a different selection of 8 operations that accounts for the rectangular boundary’s additional symmetry axis.

The G-V-01 audit (2026-04-24) confirmed that D8 canonicalisation is correctly implemented in the v2 packing generator (251111_Packing_Permutation_Generator.py): all 100 packings from run [2511041248] are confirmed unique under the D8 equivalence relation, and the implementation matches the Specification.md definition.

2.3 Burnside’s lemma and the counting argument for CL-8-07

The formal justification for CL-8-07’s lower-bound claim 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 G-V-01), 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 cap was reached, a decision recorded in the dossier as SL-03. 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.^{9 10} 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 Specification.md, instantiates this framework with four specific rule types:

1. D4/D8 canonicalisation rules: equivalence classes rather than production rules; they specify that arrangement and packing deduplication uses the dihedral symmetry group. 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 of CL-8-06 DECLARED-LIMITED

CL-8-06 is declared limited because the v2 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 Ref 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 Ref rules are primarily restrictive: they would eliminate from the 100 D8-canonical packings those that violate alignment or port conventions. This means the v2 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 v2 claim (CL-8-07: “at least 100 unique D8-canonical packings”) is therefore conservative in the correct direction: the full grammar would produce a subset of the v2 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 v2 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 CL-8-06 and CL-8-07 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 assignment

4.1 CL-8-06: HIGH confidence despite partial implementation

The confidence assignment for CL-8-06 (HIGH, 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, Ref) are constraint additions that would filter this space but not create new valid configurations that the implemented rules could not reach.

G-V-01 audit (2026-04-24) 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). CL-8-06’s confidence is HIGH because the claim is that these three rules are implemented — and they are confirmed implemented. The DECLARED-LIMITED annotation is a scope statement, not a confidence reduction: it bounds the claim to what the v2 generator actually does, not what the full grammar would do.

4.2 CL-8-07: HIGH confidence at the lower bound

CL-8-07’s claim — “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 file listing of the [2511041248] run output (100 JPG files), and G-V-01 confirmed that the packing generator correctly implements D8 canonicalisation. The 100-packing cap (SL-03) does not weaken this claim; it establishes the claim’s lower-bound nature. The confidence concerns the claim as stated, and as stated it is verifiable and verified.

The CEI/EEI/BEI statistics (mean CEI=0.9353 SD=0.011; EEI=0.5648 SD=0.049; BEI=0.6078 SD=0.058) provide additional characterisation of the 100-packing corpus without adding new claims that would require separate confidence assignment. These statistics are descriptive of the confirmed 100-packing set and inherit CL-8-07’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. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley.