Generation of maximal snake polyominoes using a deep neural network
Benjamin Gauthier Alain Goupil Fadel Toure · 2026
Read Generation of maximal snake polyominoes using a deep neural network by Benjamin Gauthier Alain Goupil Fadel Toure (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-12400.txt.
Introduction
Gauthier, Goupil, and Toure generate maximal snake polyominoes with a deep neural network. Counting all snakes in large rectangles takes brute force, which blocks study at scale. Their Structured Pixel Space Diffusion model learns maximality and adjacency from data, with no explicit rules coded in. Training on small rectangles generalizes to far larger ones in their tests. Valid snakes appear up to 28 by 28 squares, with maximal candidates near the current computational limit. Errors like branching and cycles remain, yet the route looks promising.
Catalog record
| CREATOR | Benjamin Gauthier Alain Goupil Fadel Toure |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 25985 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.12400
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Generation of maximal snake polyominoes using a deep neural network Benjamin Gauthier Alain Goupil Fadel Toure Abstract Maximal snake polyominoes are difficult to study numerically in large rectangles, as computing them requires the complete enumeration of all snakes for a specific grid size, which corresponds to a brute force algorithm. This technique is thus challenging to use in larger rectangles, which hinders the study of maximal snakes. Furthermore, most enumerable snakes lie in small rectangles, making it difficult to study large-scale patterns. In this paper, we investigate the contribution of a deep neural network to the generation of maximal snake polyominoes from a data-driven training, where the maximality and adjacency constraints are not encoded explicitly, but learned. To this extent, we experiment with a denoising diffusion model, which we call Structured Pixel Space Diffusion (SPS Diffusion). We find that SPS Diffusion generalizes from small grids to larger ones, generating valid snakes up to 28 × 28 28\times 28 squares and producing maximal snake candidates on squares close to the current computational limit. The model is, however, prone to errors such as branching, cycles, or multiple components. Overall, the diffusion model is promising and shows that complex combinatorial objects can be understood by deep neural networks, which is useful in their investigation. 1 Introduction In the past 40 years polyominoes and polycubes have been the object of intense investigations from different points of view: combinatorial, algorithmic and statistical physics ( [ 7 ] and ref. therein, [ 13 ] ). The problem of finding the length of maximal snake polyominoes in an arbitrary rectangle is still open. The most effective algorithmic approach currently available consists in enumerating all snake polyominoes and then selecting the maximal ones. Early foundational work on such brute force algorithms was conducted by Jensen [ 10 ] , who used transfer-matrix methods and enumeration techniques to count polyominoes and tree-like polyominoes. Later work with Guttmann [ 11 ] analyzed the asymptotic behavior of polyomino counts using tools from statistical mechanics, showing that the number of polyominoes grows by a factor of about 4.06 when the number of cells increases by one. Since there exists families of snake polyominoes that are in bijection with Fibonacci numbers ( [ 6 ] ), the number of snakes polyominoes grows exponentially with respect to their size and since there is an injection from the set of snake polyominoes of length n into the set of self-avoiding walks ( [ 6 ] ) the growth constant of snake polyominoes is at most that of self-avoiding walks which is known to be 2.6 ( [ 9 ] ). There is thus an inherent difficulty in generating snakes by exhaustive enumeration, especially in large rectangles. Barequet and Ben-Shachar [ 2 ] revisited polyomino enumeration by introducing bounding boxes rotated by 45^{\circ} instead of axis-aligned rectangles. This reformulation improved brute-force enumeration and allowed polyominoes up to size 70 to be enumerated, compared to Jensen’s previous limit of 56 . Nevertheless, the enumeration remains exponential, highlighting the difficulty of counting and generating maximal snakes in large grids. Another issue is that we observed (without proof) that the general structure of maximal snake polyominoes is different and more apparent in large rectangles compared to small rectangles. Maximal snakes in large rectangles are, so far, impossible to obtain with conventional programming. It becomes relevant to observe maximal snake polyominoes in large rectangles in the hope of formulating conjectures of exact expressions about their size and their enumeration. A theoretical upper bound on the maximal length of snake polyominoes is provided by the 2/3 theorem [ 14 ] . While these upper bounds provide useful theoretical guidance, they do not help overcome the computational difficulties of generating maximal snake polyominoes in large rectangles. Knowing these previous algorithmic limitations, the use of deep neural network (DNN) becomes an interesting alternative to circumvent exponential complexity and study snakes in larger rectangles. Indeed, DNNs have polynomial complexity, which makes them theoretically faster than the current brute force algorithms used for generating snake polyominoes of maximal length. While DNNs have achieved remarkable success in domains such as image generation and natural language processing [ 20 , 8 ] , their application in discrete combinatorial objects and mathematical structure discovery remains relatively unseen to us. In this work, we generate snake polyominoes using a Structured Pixel Space Diffusion (SPS Diffusion) model. Our goal is not to replace exact methods for enumerating snake polyominoes , but rather to evaluate whether deep neural networks can learn the structural constraints of snake polyominoes and produce candidates for maximal snakes, thus offering an additional tool to classical enumeration techniques and, as a byproduct, an argument for the existence of combinatorial structure of these objects. Section 2 introduce the necessary concepts. In section 3 we introduce two neural network and compare them. In section 4 . we present the results obtained. 2 Preliminaries 2.1 snake polyominoes definitions In this section, we recall useful definitions to understand some technical aspects of this research. For a rigorous definition of snake polyominoes, see [ 12 ] . A snake polyomino, or more briefly a snake, is a polyomino where all cells are of degree two except for two cells of degree one, called the head and tail. In a grid representation, living cells (black) correspond to the snake body and dead cells (white) to empty cells (Fig. 1(a) ). We use a matrix representation where living cells are labeled 1 and dead cells 0 (Fig. 1(b) ). Snakes are contained in discrete rectangles of size H\times W , and, naturally, the same goes for their matrix representation. From graph theory, it follows that the degree of a cell x is the number of edge-adjacent living cells. We assume the standard 4-connexity of square cells, where each cell has at most four neighbors [ 4 ] . (a) Grid representation of a snake. (b) Matrix representation of a snake. Figure 1 : Different representations of snake polyominoes. To qualitatively assess generated snakes, we identify recurring snake-like structures, i.e., patterns commonly observed in maximal snakes (Fig. 2 ). Examples include stairs, which provide a compact folding of cells of degree at most two [ 3 ] , triangles of six dead cells, and configurations where the head or tail folds compactly. Such structures frequently appear in maximal snakes, although they are not exclusive. For example, head and tail are frequently observed along the borders and corners of the grid. Conversely, we identify snake malformations, which are structures incompatible with valid snakes (Fig. 2 ). Examples include branching, cycles (absence of head and tail), open heads/tails and forests of snakes where several disconnected components appear. The presence of such structures generally indicates that the snake is not maximal. Note that an open head/tail doesn’t imply that the snake is not maximal, rather that it may not be. It is also useful to know that density is in general greater along the edges of the grid than in the center This fact has been proved for 2D -words ( [ 14 ] ). Border density is thus a good indicator that a snake is maximal. Figure 2 : Maximal snake-like structures (above) - stairs, a triangle