Generation of maximal snake polyominoes using a deep neural network

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 28x28 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.