Snake Polyominoes of Maximal Area in a Rectangle

Alain Goupil (LACIM; Alexandre Blondin Mass\'e (LACIM; Universit\'e du Qu\'ebec \`a Montr\'eal); Universit\'e du Qu\'ebec \`a trois-Rivi\`eres)

arxiv: 2606.13155 · v1 · pith:VDBUEXYZnew · submitted 2026-06-11 · 💻 cs.DM

Snake Polyominoes of Maximal Area in a Rectangle

Alexandre Blondin Mass\'e (LACIM , Universit\'e du Qu\'ebec \`a Montr\'eal) , Alain Goupil (LACIM , Universit\'e du Qu\'ebec \`a trois-Rivi\`eres) This is my paper

Pith reviewed 2026-06-27 05:12 UTC · model grok-4.3

classification 💻 cs.DM

keywords snake polyominoesmaximal arearectangle4-adjacencyenumeration algorithmpolyomino chainsbinary matrices

0 comments

The pith

Snake polyominoes achieve explicit maximum areas in rectangles of height at most 5.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces an algorithm that generates every snake-like polyomino inside an h by w rectangle, defined as those whose cells form a single path under 4-adjacency. It then supplies closed-form expressions for the largest area any such polyomino can reach when the height is 5 or less. These formulas replace the need to search through all possible chains for each new width. A reader cares because the expressions let one compute the densest possible path-shaped filling directly for narrow rectangles without running the generator.

Core claim

The authors present an algorithm that generates the set W of all snake-like polyominoes contained in an h by w rectangle and supply exact formulas for the maximum area a attainable by any member of W when h is at most 5.

What carries the argument

An enumeration algorithm that produces every binary matrix whose 4-adjacency graph is a path, used to compute the area maximum for each fixed height.

If this is right

The maximum area a is given by a closed expression that depends only on w for each height from 1 to 5.
All snake polyominoes inside rectangles of height at most 5 can be listed exhaustively by the algorithm.
The maximal area increases linearly with width once height is fixed.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same algorithmic approach could be used to search for patterns or recurrences that might yield formulas for heights greater than 5.
The maximal-area expressions could be compared against known bounds for Hamiltonian paths on grid graphs.
Knowing these exact maxima supplies concrete targets for testing whether other connectivity rules or polyomino families admit similar closed forms.

Load-bearing premise

The algorithm correctly enumerates every snake-like polyomino whose adjacency graph is a path under 4-connectivity.

What would settle it

Discovery of a single snake polyomino inside a 5 by w rectangle whose area exceeds the formula value for that w.

read the original abstract

Given a discrete rectangle R of dimensions h x w, let W be the set of snake-like polyominoes contained in R represented as binary matrices, i.e. polyominoes whose underlying simple graph is a chain with respect to the 4-adjacency relation. We present an algorithm that generates W for any h and w. Also, let a be the maximal area that can be realized by an element of W. We provide exact formulas of a for h <= 5 and any w.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper supplies an algorithm for listing snake polyominoes in rectangles plus closed-form max areas for heights up to 5.

read the letter

The main takeaway is that the authors give a generation algorithm for all 4-connected path polyominoes inside an h by w rectangle and then extract exact formulas for the largest possible area when h is at most 5.

They handle the bounded-height case by what appears to be a row-by-row state machine that tracks the path endpoints and occupied cells. With height fixed at 5 or less the state count stays small enough to run for any width, and the resulting counts reveal simple patterns that become the closed forms. That is the useful part: instead of tables or code that must be rerun, you get an expression you can evaluate directly.

The work is narrow by design. Height 5 is small enough that standard transfer-matrix ideas suffice, so the advance is mainly in carrying the computation through to explicit formulas rather than stopping at numerical results. The paper does not claim a method for arbitrary height, which keeps the claims honest. One minor soft spot is that the abstract and stress-test note give no detail on how the formulas were verified for large w; if the authors computed up to moderate widths and then conjectured the pattern, a referee might ask for an independent check on a few big instances.

This is for people who already work on polyomino enumeration or grid-path problems. A reader who needs the specific max-area numbers for small heights will find it directly usable. The thinking is clear and the problem is well-posed, so the paper deserves a serious referee even though the scope is limited.

Referee Report

0 major / 1 minor

Summary. The paper defines W as the set of snake-like polyominoes (4-connected paths) inside an h×w rectangle, presents an algorithm that generates all members of W for arbitrary h and w, and supplies exact closed-form expressions for the maximal area a when h≤5.

Significance. The combination of an explicit enumeration algorithm with closed-form maximal-area formulas for all widths at fixed small heights constitutes a complete solution for this bounded-height case. Such results are useful in polyomino enumeration and grid-path problems because the fixed height permits standard dynamic-programming or transfer-matrix techniques to be applied exhaustively.

minor comments (1)

[Abstract] Abstract: a one-sentence outline of the algorithmic technique (e.g., dynamic programming over row configurations that track path endpoints) would help readers immediately understand how the enumeration is performed.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript, the accurate summary of its contributions, and the recommendation for minor revision. No specific major comments were raised.

Circularity Check

0 steps flagged

No significant circularity; enumeration yields independent formulas

full rationale

The paper defines W via the standard 4-connected path condition on binary matrices inside an h×w rectangle, supplies an explicit generation algorithm for W, and then reports closed-form expressions for the maximum cardinality a when h≤5. No equation equates a quantity to itself by definition, no fitted parameter is relabeled as a prediction, and no load-bearing step reduces to a self-citation or imported uniqueness claim. The bounded-height case permits standard exhaustive search whose output is then summarized algebraically; this chain is self-contained and externally verifiable by re-running the algorithm.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no free parameters, axioms, or invented entities can be extracted.

pith-pipeline@v0.9.1-grok · 5641 in / 924 out tokens · 25188 ms · 2026-06-27T05:12:58.439778+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

3 extracted references · 3 canonical work pages

[1]

In: International Conference on Combinatorics on Words , Springer, pp

Alexandre Blondin Massé, Alain Goupil, Raphael L’Heureux & Louis Marin (2025): Maximal 2-Dimensional Binary Words of Bounded Degree . In: International Conference on Combinatorics on Words , Springer, pp. 37–48, doi:10.1007/978-3-031-97548-6_4

work page doi:10.1007/978-3-031-97548-6_4 2025
[2]

In: Handbook of formal lan- guages: volume 3 beyond words , Springer, pp

Dora Giammarresi & Antonio Restivo (1997): Two-dimensional languages. In: Handbook of formal lan- guages: volume 3 beyond words , Springer, pp. 215–267, doi:10.1007/978-3-642-59126-6_4

work page doi:10.1007/978-3-642-59126-6_4 1997
[3]

In: Formal Languages and Applications , Springer, pp

Kenichi Morita (2004): Two-dimensional languages. In: Formal Languages and Applications , Springer, pp. 427–437, doi:10.1007/978-3-540-39886-8_22

work page doi:10.1007/978-3-540-39886-8_22 2004

[1] [1]

In: International Conference on Combinatorics on Words , Springer, pp

Alexandre Blondin Massé, Alain Goupil, Raphael L’Heureux & Louis Marin (2025): Maximal 2-Dimensional Binary Words of Bounded Degree . In: International Conference on Combinatorics on Words , Springer, pp. 37–48, doi:10.1007/978-3-031-97548-6_4

work page doi:10.1007/978-3-031-97548-6_4 2025

[2] [2]

In: Handbook of formal lan- guages: volume 3 beyond words , Springer, pp

Dora Giammarresi & Antonio Restivo (1997): Two-dimensional languages. In: Handbook of formal lan- guages: volume 3 beyond words , Springer, pp. 215–267, doi:10.1007/978-3-642-59126-6_4

work page doi:10.1007/978-3-642-59126-6_4 1997

[3] [3]

In: Formal Languages and Applications , Springer, pp

Kenichi Morita (2004): Two-dimensional languages. In: Formal Languages and Applications , Springer, pp. 427–437, doi:10.1007/978-3-540-39886-8_22

work page doi:10.1007/978-3-540-39886-8_22 2004