🔢 mathematics

Generation of maximal snake polyominoes using a deep neural network

Dit paper onderzoekt hoe een diep neurale netwerk, specifiek het Structured Pixel Space Diffusion-model, kan worden getraind om maximale slang-polyomino's te genereren die generaliseren naar grotere roosters, hoewel het model nog vatbaar is voor fouten zoals vertakkingen en cycli.

Oorspronkelijke auteurs: Benjamin Gauthier, Alain Goupil, Fadel Toure

Gepubliceerd 2026-03-16

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Benjamin Gauthier, Alain Goupil, Fadel Toure

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Reizende Slangje: Hoe een AI een wiskundig raadsel probeert op te lossen

Stel je voor dat je een gigantisch raster hebt, zoals een enorm schaakbord of een muur vol tegels. Je taak is om een slang te tekenen die over deze tegels kruipt. Maar dit is geen gewone slang:

Hij mag nooit zijn eigen staart bijten (geen lussen).
Hij mag nooit een kruispunt maken waar hij in drie richtingen kan gaan (geen takken).
Hij moet zo lang mogelijk zijn, zonder dat hij uit het raster valt.

In de wiskunde noemen we dit een "maximale slang-polyomino". Het probleem? Als het raster klein is, kun je dit makkelijk uitrekenen. Maar als het raster groot wordt (bijvoorbeeld 50 bij 50 tegels), wordt het aantal mogelijke routes zo enorm dat het voor een gewone computer onmogelijk is om ze allemaal te tellen. Het is alsof je probeert elke mogelijke route in een doolhof van een heel land te vinden; het duurt langer dan de leeftijd van het heelal.

De oude manier: Tellen tot je gek wordt
Vroeger probeerden wiskundigen dit door brute kracht te gebruiken. Ze lieten de computer alle mogelijke slangen één voor één genereren en tellen. Dit werkt goed voor kleine puzzels, maar bij grote puzzels stopt de computer met werken omdat het te veel tijd kost.

De nieuwe manier: Een AI die "leert" tekenen
De auteurs van dit paper (Benjamin, Alain en Fadel) hebben een slimme oplossing bedacht. In plaats van de computer te laten rekenen, hebben ze hem laten leren. Ze hebben een Deep Neural Network (een soort kunstmatige intelligentie) getraind, vergelijkbaar met de technologie die wordt gebruikt om prachtige kunst te genereren of foto's te verbeteren.

Ze noemen hun model SPS Diffusion. Hier is hoe het werkt, vertaald naar een eenvoudig verhaal:

1. De "Drukkende" Methode (Diffusie)

Stel je voor dat je een prachtig tekening van een slang op een stuk papier hebt. Dan gooi je er een flesje inkt overheen en schud je het papier, zodat de tekening onherkenbaar wordt en er alleen nog maar vlekken en ruis op staan.

De AI doet het omgekeerde:

Het begint met een vel papier dat vol zit met statische ruis (alsof je een tv hebt zonder signaal).
De AI kijkt naar die ruis en zegt: "Hm, hier lijkt een stukje slang te zitten, en hier een bocht."
Het verwijdert beetje bij beetje de ruis, net als iemand die een schilderij schoonveegt.
Uiteindelijk blijft er een schone, lange slang over.

2. Waarom is dit speciaal?

Normaal gesproken leren AI's om dingen te tekenen door voorbeelden te zien. Maar deze AI is niet verteld: "Je mag geen takken maken" of "Je mag geen lussen maken". De auteurs hebben deze regels niet in de code gezet.

In plaats daarvan hebben ze de AI duizenden voorbeelden van goede slangen gegeven. De AI heeft zelf ontdekt: "Oh, als ik hier een takje maak, ziet het er raar uit. Als ik een lus maak, is het ook raar. Ik moet dus een rechte lijn houden." De AI heeft de regels van de wiskunde geleerd door te kijken naar de patronen, net zoals een kind leert dat een hond niet op twee poten loopt door veel honden te zien.

3. De Resultaten: Een Magische Slang

Het resultaat is verbazingwekkend:

De AI kan slangen genereren op rastergroottes die voor de oude computers te groot waren (tot wel 28x28 tegels, en zelfs pogingen op 50x50).
Ze vinden vaak slangen die langer zijn dan wat mensen eerder met de hand hadden kunnen bewijzen.
De AI kan zelfs slangen tekenen in vormen die ze tijdens het leren nooit hadden gezien (generalisatie).

Maar... het is niet perfect
De AI is nog niet perfect. Soms maakt ze fouten:

Soms maakt ze een tak (de slang splitst zich).
Soms maakt ze een lus (de slang bijt in zijn eigen staart).
Soms maakt ze een bos van kleine slangjes in plaats van één grote.

Dit is als een kunstenaar die een meesterwerk probeert te schilderen, maar soms per ongeluk een vlek maakt. Toch is het een enorme doorbraak, omdat de AI complexe patronen begrijpt die we zelf nog niet volledig kunnen uitleggen.

Conclusie: Een nieuwe blik op oude problemen
Dit onderzoek toont aan dat we niet altijd hoeven te rekenen om wiskundige raadsels op te lossen. Soms kunnen we een AI laten "dromen" van oplossingen. Hoewel de AI soms fouten maakt, helpt ze ons om nieuwe ideeën te krijgen over hoe lange slangen eruitzien in grote doolhoven. Het is een nieuwe manier om de wiskunde te verkennen: niet door alles te tellen, maar door te leren wat een "mooie" oplossing eruit ziet.

Kortom: De auteurs hebben een digitale kunstenaar gevonden die, zonder de regels te kennen, zelf de regels van de slang heeft ontdekt en nu helpt om de langste mogelijke slangen te vinden.

Probleemstelling

Het vinden van de lengte van maximale slang-polyomino's (snake polyominoes) in willekeurige rechthoeken is een open probleem in de combinatoriek. Een slang-polyomino is een verzameling cellen in een rooster waarbij alle cellen graad 2 hebben, behalve twee cellen (het hoofd en de staart) die graad 1 hebben.

Uitdaging: De huidige meest effectieve aanpak is het volledig enumereren (opsporen) van alle mogelijke slangen en het selecteren van de langste. Dit is een brute-force algoritme met exponentiële complexiteit.
Beperkingen: Deze methode is onuitvoerbaar voor grote roosters. Bovendien liggen de meeste telbare slangen in kleine rechthoeken, wat het moeilijk maakt om grootschalige patronen te bestuderen of conjectures te formuleren over de exacte grootte in grote roosters.
Doel: Het ontwikkelen van een alternatieve methode om maximale slangen te genereren in grotere roosters zonder de beperkingen van brute-force enumeratie, en om te onderzoeken of neurale netwerken de structurele beperkingen van deze discrete objecten kunnen leren.

Methodologie: SPS Diffusion

De auteurs introduceren een nieuw model genaamd Structured Pixel Space Diffusion (SPS Diffusion), een variant van een Denoising Diffusion Probabilistic Model (DDPM).

Aanpassing aan het domein:
- In tegenstelling tot standaard beeldgeneratie-modellen (zoals Stable Diffusion) die werken met RGB-kleuren en grote afbeeldingen, werken slangen met binaire matrices (0 voor lege cellen, 1 voor levende cellen).
- Het model gebruikt geen CLIP-encoder (geen tekst-prompt nodig) en geen Variational Autoencoder (VAE), omdat de afbeeldingen klein zijn en geen compressie nodig hebben.
- Het model bestaat uit een Mini U-Net met slechts drie niveaus van downsampling (in plaats van 5 of 6 bij standaardmodellen) om structurele informatie in de kleine roosters te behouden.
Architectuur:
- Het model gebruikt convolutielagen, residual blocks en self-attention blokken met 2D Rotary Positional Embeddings (RoPE-2D). Dit laat het model toe om ruimtelijke relaties en lange-afstand afhankelijkheden in het rooster te begrijpen.
- De training gebeurt via forward diffusion: ruis wordt toegevoegd aan bekende maximale slangen ( $x_0$ ) om een ruisig beeld ( $x_t$ ) te creëren. Het model leert vervolgens de ruis ( $\epsilon$ ) te voorspellen om terug te keren naar de originele slang.
- De verliesfunctie is de Mean Squared Error (MSE), die beter presteerde dan andere opties bij het genereren van slang-achtige structuren zonder fouten.
Generatieproces:
- Tijdens inferentie start het model met puur ruis en voert het iteratieve backward diffusion uit om een gestructureerde slang te genereren.

Belangrijkste Resultaten

Generalisatie: Het model, getraind op roosters tot $50 \times 10$ $50 \times 10$ en $14 \times 14$ $14 \times 14$ (voor vierkanten), slaagt erin om te generaliseren naar veel grotere roosters die niet tijdens de training zijn gezien.
- Het genereerde geldige slangen in vierkante roosters tot $28 \times 28$ .
- Voor rechthoekige roosters werden successen geboekt tot $10 \times 60$ .
Kwaliteit van resultaten:
- Voor roosters kleiner dan $17 \times 17$ (de huidige computergrens voor exacte enumeratie) genereerde het model slangen die de bekende ondergrenzen voor maximale lengte soms met één cel overtroffen.
- Het model produceerde vaak geldige slangen in roosters die tijdens training niet waren gezien, wat aantoont dat het de onderliggende structuur heeft geleerd.
Beperkingen en Fouten:
- Naarmate de roostergrootte toeneemt, neemt de foutkans toe.
- Het model produceert soms malformaties zoals:
  - Vertakkingen (cellen met graad 3).
  - Cirkels (geen hoofd of staart).
  - "Wouden" van gescheiden slangen of polyomino's.
- Voor roosters groter dan $28 \times 28$ (bijv. $29 \times 29$ ) slaagde het model er niet meer in om een enkele slang te genereren; het produceerde alleen nog maar fragmenten of wouden.

Bijdragen en Significantie

Nieuwe numerieke tool: De studie demonstreert dat diepe neurale netwerken (DNN's) complexe combinatorische objecten kunnen begrijpen en genereren zonder dat de regels (zoals "geen cirkels" of "graad 2") expliciet in de code worden geprogrammeerd. Ze leren deze beperkingen puur uit de data.
Onderzoek naar grote roosters: De methode biedt een manier om maximale slangen te bestuderen in groottes die onbereikbaar zijn voor brute-force algoritmen. Dit kan leiden tot nieuwe conjectures over de exacte grootte en enumeratie van maximale slangen.
Iteratief potentieel: De auteurs suggereren een iteratieve aanpak waarbij gegenereerde slangen (zelfs als ze niet perfect maximaal zijn) worden toegevoegd aan de trainingsset om het model te verbeteren voor nog grotere roosters.
Combinatorische inzichten: Het succes van het model bevestigt dat er diepe, leerbare structurele patronen bestaan in de wereld van polyomino's, die door DNN's kunnen worden geëxploiteerd.

Conclusie: Hoewel het SPS Diffusion-model nog niet perfect is (het produceert nog fouten bij zeer grote roosters), is het een veelbelovende benadering die de exponentiële complexiteit van traditionele methoden omzeilt en een nieuwe weg opent voor het onderzoek naar maximale slang-polyomino's in grote roosters.