🔢 mathematics

Generation of maximal snake polyominoes using a deep neural network

This paper introduces a denoising diffusion model called Structured Pixel Space Diffusion (SPS Diffusion) that learns to generate maximal snake polyominoes from data without explicit constraint encoding, successfully generalizing to large grids up to 28x28 despite occasional structural errors.

Original authors: Benjamin Gauthier, Alain Goupil, Fadel Toure

Published 2026-03-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Benjamin Gauthier, Alain Goupil, Fadel Toure

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a giant, complex puzzle. The pieces are black squares, and your goal is to connect them all into one long, winding snake that never crosses itself, never branches off, and fills up as much of a rectangular grid as possible. This is the mathematical problem of finding the "maximal snake polyomino."

For decades, mathematicians have tried to solve this by brute force: they write computer programs to try every single possible arrangement of squares, one by one, until they find the longest one. But here's the catch: as the grid gets bigger, the number of possible arrangements explodes. It's like trying to find a specific grain of sand on a beach by checking every single grain. For large grids, this method is impossible; the computer would take longer than the age of the universe to finish.

The New Approach: Teaching a Computer to "Dream"

In this paper, the authors (Benjamin, Alain, and Fadel) decided to stop trying to count every grain of sand. Instead, they asked: What if we could teach a computer to recognize what a "good snake" looks like, just by showing it examples?

They used a type of Artificial Intelligence called a Deep Neural Network, specifically a model they named SPS Diffusion.

The Analogy: The "Denoising" Artist

To understand how this works, imagine a master artist who has seen thousands of perfect snake puzzles. Now, imagine you take a perfect drawing of a snake and slowly cover it with thick, gray fog until it's just a blurry mess.

The AI's job is to be the "Denoising Artist."

The Training: The AI is shown thousands of perfect snakes. Then, the computer takes those snakes, adds "noise" (static or fog) to them, and asks the AI: "If I give you this foggy picture, can you tell me exactly what the fog looks like so I can remove it?"
The Learning: The AI learns the patterns. It realizes, "Oh, if I see a black square here, there's usually a black square next to it, but never two black squares touching in a 'T' shape (that's a branch, which is bad)." It learns the rules of the snake not by being told the rules, but by seeing thousands of examples.
The Generation: Once trained, the AI starts with a completely blank, foggy canvas (pure random noise). It then starts "cleaning" the fog, step by step. It peels away the noise, guided by what it learned, until a clear, structured snake emerges from the chaos.

What Did They Discover?

The results were surprisingly promising, like watching a child learn to draw by copying their parents:

Generalization: The AI was trained on small grids (like 10x10). When they asked it to draw snakes on much larger grids (like 28x28) that it had never seen before, it didn't just fail. It successfully generated long, winding snakes that looked very similar to the ones mathematicians had found manually. It learned the concept of a snake, not just the specific pictures it memorized.
Breaking Records: In some cases, the AI generated snakes that were even longer than the best ones previously known for certain grid sizes. It found new, efficient ways to fold the snake that humans hadn't thought of yet.
The "Hallucinations": The AI isn't perfect. Sometimes, instead of one long snake, it draws a "forest" of disconnected snakes. Sometimes it draws a loop (a snake eating its own tail) or a branch (a T-shape). It's like a student who understands the concept of a snake but occasionally forgets to close the loop or adds an extra leg.

Why Does This Matter?

This paper is a big deal because it suggests that Deep Learning can understand complex mathematical rules without being explicitly programmed with them.

Think of it like teaching a dog to fetch. You don't explain the physics of throwing a ball or the geometry of a trajectory. You just throw the ball and reward the dog when it brings it back. Eventually, the dog understands the pattern of "throw -> run -> catch."

Similarly, this AI learned the "pattern" of a maximal snake. While it can't yet replace the rigorous math needed to prove a snake is the absolute longest possible, it acts as a powerful exploration tool. It can quickly generate thousands of "candidate" snakes in large grids where traditional computers would freeze. This gives mathematicians new ideas and patterns to study, helping them formulate new theories about how these snakes behave in the vast, uncharted territories of large grids.

In short: The authors built a digital artist that learned to draw the perfect mathematical snake by looking at examples. It sometimes makes mistakes, but it's fast, it works on giant grids, and it's showing us new ways to solve an old, stubborn puzzle.

1. Problem Statement

The paper addresses the computational challenge of finding maximal snake polyominoes (self-avoiding paths with degree-2 internal nodes and degree-1 endpoints) in large rectangular grids.

The Core Difficulty: Determining the exact length of the longest snake in an arbitrary rectangle is an open problem. Current state-of-the-art methods rely on brute-force enumeration, which has exponential time complexity. This limits the study of maximal snakes to relatively small grids (e.g., squares up to $17 \times 17$ ).
The Gap: While small grids are well-studied, the structural patterns of maximal snakes in large rectangles remain obscure because they cannot be enumerated. Furthermore, existing theoretical upper bounds (e.g., the 2/3 theorem) do not provide constructive methods to generate these objects.
Objective: The authors aim to bypass exponential complexity by using a Deep Neural Network (DNN) to learn the structural constraints of snake polyominoes from data, generating valid candidates for maximal snakes in grid sizes previously inaccessible to enumeration.

2. Methodology: Structured Pixel Space Diffusion (SPS Diffusion)

The authors propose a custom denoising diffusion probabilistic model (DDPM) tailored for discrete 2D structures, termed SPS Diffusion.

A. Model Architecture

Unlike standard image generation models (like Stable Diffusion), SPS Diffusion is simplified and specialized for binary grid data:

Input/Output: The model operates directly in pixel space (no Variational Autoencoder or latent space compression is used) because snake grids are small ( $<64 \times 64$ ) and binary (0 for empty, 1 for snake).
Network Structure: It utilizes a mini U-Net with only 3 levels of downsampling (compared to 5–6 in standard models) to preserve structural fidelity.
- Components: Residual blocks and Attention blocks.
- Attention Mechanism: Uses 2D Rotary Positional Embeddings (RoPE-2D) to capture long-range dependencies and global grid structure without relying on text prompts.
- Exclusions: The model omits the CLIP encoder (no text prompts) and the VAE (no latent space), focusing solely on the denoising task.
Process:
1. Forward Diffusion (Training): Noise is added to known maximal snake solutions ( $x_0$ ) to create noisy inputs ( $x_t$ ).
2. Backward Diffusion (Generation): The model starts with pure noise and iteratively predicts and subtracts noise to reconstruct a snake-like structure.
3. Loss Function: The model is trained using Mean Squared Error (MSE) between the predicted noise and the actual added noise. The authors found MSE superior to other loss functions for preserving snake topology.

B. Training Data

The model was trained on a dataset of maximal snakes from grids ranging from $4 \times 4$ to $50 \times 10$ .
Training involved over 200 different grid dimensions, with a specific focus on square grids up to $14 \times 14$ and various rectangular aspect ratios.

3. Key Contributions

Novel Application of DNNs: Demonstrates that deep neural networks can learn complex combinatorial constraints (self-avoidance, connectivity, maximality) without explicit programming of graph-theoretic rules.
SPS Diffusion Architecture: Introduces a specialized diffusion architecture that operates directly on pixel space for binary discrete objects, removing unnecessary components (VAE, CLIP) found in general-purpose image generators.
Generalization Capability: Shows that the model can generalize from small training grids to significantly larger inference grids, effectively "hallucinating" valid snake structures in domains where no training data existed.
New Lower Bounds: The model successfully generated snake configurations that exceed previously known rigorous lower bounds for maximal snake lengths in specific grid sizes.

4. Results

In-Distribution Performance: The model successfully generated maximal snakes for all grid sizes seen during training.
Out-of-Distribution Generalization:
- Square Grids: Successfully generated valid snakes up to $28 \times 28$ , a size far beyond the training limit of $14 \times 14$ and the current enumeration limit of $17 \times 17$ .
- Rectangular Grids: Generated snakes in highly elongated grids (e.g., $10 \times 60$ ) and large squares ( $50 \times 50$ ).
Performance Metrics:
- For grids up to $17 \times 17$ , the model produced snakes with lengths exceeding known lower bounds by up to 3 cells in some cases.
- Error Rates: As grid size increases, the error rate rises. For $29 \times 29$ grids, the model failed to produce any valid snakes, generating only "forests" of disconnected components.
Failure Modes: The model is prone to topological errors, including:
- Branching: Cells with degree 3.
- Cycles: Closed loops (no head/tail).
- Forests: Multiple disconnected snake components.
- Open Heads/Tails: Endpoints that do not fold correctly.

5. Significance and Future Directions

Theoretical Insight: The results suggest that maximal snake polyominoes possess an underlying statistical structure that can be approximated by neural networks, offering a new perspective on combinatorial objects.
Computational Tool: SPS Diffusion serves as a heuristic tool to explore grid sizes where exhaustive enumeration is impossible. It provides candidate solutions that can guide theoretical conjectures about maximal lengths.
Limitations & Future Work:
- Validity: The model does not guarantee valid snakes; post-processing or filtering is required to remove malformations.
- Scalability: The current fixed architecture (3 downsampling levels) and positional encoding (RoPE-2D) may struggle with very large grids. Future work suggests training larger U-Nets and potentially using an iterative "self-training" loop (generating data with the model to retrain it) to push boundaries further.
- Optimization: Improving the loss function or architecture to reduce the frequency of topological errors is a primary goal.

In conclusion, the paper establishes that deep learning can effectively model the complex constraints of snake polyominoes, offering a promising alternative to brute-force enumeration for studying large-scale combinatorial structures.