🤖 machine learning

Graph Coloring Approach to Solving Sudoku with Oscillatory Neural Networks

Dit artikel introduceert een geoptimaliseerde Oscillatory Neural Network (ONN) solver die Sudoku herformuleert als een grafiekkleurprobleem, waarmee een aanzienlijk hogere nauwkeurigheid wordt bereikt dan bestaande HNN- en ONN-benaderingen op zowel $4 \times 4$ als $9 \times 9$ puzzels.

Oorspronkelijke auteurs: Filip Sabo, Aida Todri-Sanial

Gepubliceerd 2026-07-20

📖 7 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Filip Sabo, Aida Todri-Sanial

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

Stel je een wereld voor waarin computers niet alleen getallen verwerken als een supersnelle rekenmachine, maar in plaats daarvan dansen op een ritme. Dit is het domein van Oscillatory Neural Networks (ONN's), een type "physics-gebaseerde" computing. In plaats van standaard elektronische schakelaars te gebruiken, maken deze netwerken gebruik van kleine, trillende eenheden die oscillatoren worden genoemd. Denk aan een kamer vol met metronomen of een koor van zangers. In dit systeem wordt informatie niet opgeslagen als een simpele "aan" of "uit" bit; het wordt opgeslagen in de timing van de trillingen, bekend als fasen. Als twee oscillatoren in perfecte synchronisatie trillen, zijn ze "in fase"; als ze op tegengestelde tijdstippen trillen, zijn ze "uit fase".

Het doel van deze netwerken is om een staat van perfecte harmonie te vinden, of de laagst mogelijke energie, waarbij alle oscillatoren tot een stabiel patroon komen. Deze aanpak is bijzonder goed in het oplossen van combinatorische optimalisatieproblemen—puzzels waarbij je een heleboel stukjes moet ordenen zodat ze aan specifieke regels voldoen zonder dat er conflicten ontstaan. Je hebt misschien wel eens gehoord van het Graph Coloring-probleem, wat lijkt op het inkleuren van een kaart zodat geen twee aangrenzende landen dezelfde kleur delen. Als je een netwerk van oscillatoren er natuurlijk in kunt laten komen dat ze in een patroon terechtkomen waarbij geen "buren" op hetzelfde moment trillen, heb je een complexe puzzel opgelost met de wetten van de fysica in plaats van met brute-force wiskunde. Dit is belangrijk omdat traditionele computers moeite hebben met dit soort puzzels en vaak enorme hoeveelheden elektriciteit en tijd verbruiken, terwijl deze dansende oscillatoren een snellere, meer energiezuinige manier van denken kunnen bieden.

De Grote Sudoku Danswedstrijd

Laten we het nu over Sudoku hebben. Je kent het wel: een raster van getallen waarbij je de lege vakjes moet invullen zodat elke rij, kolom en klein blokje de cijfers 1 tot en met 9 (of 1 tot en met 4 voor de kleinere versie) bevat zonder herhalingen. Het is een klassieke logische puzzel, maar voor een computer is het een enorme hoofdpijn van vallen en opstaan.

De onderzoekers in dit artikel, Filip Sabo en Aida Todri-Sanial van de Eindhoven University of Technology, besloten om Sudoku aan te pakken met hun "dansende oscillator"-netwerk. Ze behandelden het Sudoku-raster als een Graph Coloring-probleem. Stel je voor dat elk leeg vakje in het Sudoku-raster een danser is. De regel is simpel: geen twee dansers in dezelfde rij, kolom of blok mogen dezelfde "kleur" dragen (wat in dit geval een specifiek nummer vertegenwoordigt, zoals 1, 2 of 3).

In de wereld van oscillatoren betekent "een kleur dragen" dat men trilt op een specifiek ritme. Voor een 9x9 Sudoku zijn er 9 mogelijke ritmes (fasen) waar de oscillatoren uit kunnen kiezen. De taak van het netwerk is om alle dansers een ritme te laten kiezen zodat geen twee buren dezelfde dansbeweging doen.

Het Probleem met de Oude Dansbewegingen

De auteurs keken naar hoe andere wetenschappers dit eerder probeerden op te lossen. Eén methode maakte gebruik van een complexe wiskundige formule die erg duur was om te berekenen, alsof je een choreografie probeert te maken door vooraf elke spierbeweging te berekenen. Een andere methode gebruikte een simpelere aanpak, maar die had een fatale fout: het liet de dansers valsspelen.

Stel je een scenario voor waarin twee dansers in dezelfde rij er beide voor besluiten om de "Nummer 1"-dans te doen. In de oude, simpelere modellen zou het netwerk kunnen denken: "Hé, ze doen allebei het 'Nummer 1'-ritme, wat een geldig ritme is, dus het is goed zo!" Maar in Sudoku is dat een ramp. De regels zeggen dat je niet twee 1'en in dezelfde rij mag hebben. De oude modellen hadden geen manier om de dansers uit die slechte staat te trappen als ze per ongeluk synchroon gingen op het verkeerde nummer.

De Nieuwe "Kick"-term

Om dit op te lossen, hebben de auteurs een nieuwe, simpelere manier uitgevonden om de oscillatoren te laten dansen, en ze hebben een speciale "kick"-mechanisme toegevoegd.

Het Simpelere Ritme: In plaats van de ingewikkelde, dure wiskundige formule, gebruikten ze een schonere, directere vergelijking. Dit maakte de computersimulatie veel sneller en goedkoper.
De "Kick" (Het Geheime Sausje): Dit is het belangrijkste deel. Ze voegden een speciale term toe aan de vergelijkingen die fungeert als een scheidsrechter. Als twee dansers in dezelfde rij, kolom of blok per ongeluk op exact dezelfde frequentie beginnen te trillen (wat betekent dat ze hetzelfde nummer hebben gekozen), geeft deze scheidsrechter ze een scherpe "kick". Dit duwt hen uit die stabiele, comfortabele staat en dwingt hen om een ander ritme te proberen.

Deze "kick" zorgt ervoor dat het netwerk zich alleen tot rust komt wanneer de puzzel daadwerkelijk correct is opgelost. Het is als een leraar die door een klas loopt: als twee leerlingen samen het verkeerde antwoord fluisteren, tikt de leraar hen op de schouder om hen te laten stoppen en opnieuw na te denken.

De Resultaten: Een Vlekkeloze Prestatie

Het team testte hun nieuwe "kick-ass" oscillator solver op duizenden Sudoku-puzzels, variërend van kleine 4x4 rasters tot de standaard 9x9 rasters. Ze vergeleken hun resultaten met twee andere beroemde solvers: één gebaseerd op Hopfield Neural Networks (HNN) en een andere standaard Oscillatory Neural Network.

Dit is wat ze vonden:

Voor de 4x4 puzzels: Hun nieuwe solver was vrijwel perfect. Hij loste bijna 100% van de puzzels correct op, ongeacht hoeveel getallen er ontbraken. De andere solvers hadden moeite, waarbij de nauwkeurigheid scherp afnam naarmate de puzzels moeilijker werden (meer ontbrekende getallen).
Voor de 9x9 puzzels: De resultaten waren nog steeds indrukwekkend, hoewel niet perfect. Wanneer de puzzels minder ontbrekende getallen hadden (tot ongeveer 25% onbekend), was hun solver vlekkeloos. Zelfs toen de puzzels moeilijker werden (tot 37,5% onbekend), loste hij nog steeds meer dan 80% van de gevallen op. Echter, wanneer de puzzels zeer moeilijk werden (meer dan 50% onbekende getallen), begon de solver te struikelen en loste hij ongeveer 50% correct op. De andere solvers faalden veel eerder en waren vaak niet meer in staat om puzzels correct op te lossen zodra de ontbrekende getallen de 40-50% passeerden.

De onderzoekers keken ook naar een "orde-parameter", wat in feite een score is van hoe goed de oscillatoren erin slaagden om tot hun uiteindelijke, correcte ritmes te komen. Ze ontdekten dat telkens wanneer de solver de puzzel goed oploste, de oscillatoren zeer goed georganiseerd waren (hoge orde-parameter). Wanneer de solver de puzzel fout oploste, waren de oscillatoren chaotisch en konden ze geen stabiel patroon overeenkomen.

Wat Nu?

De auteurs zijn vrij zelfverzekerd dat hun "kick"-term de reden is voor het succes, maar ze geven toe dat er nog werk te doen is. Hun model heeft een paar knoppen die ze handmatig moesten instellen (instelbare parameters) om het werkend te krijgen, wat veel tijd kostte om uit te zoeken. Ze merkten ook op dat voor de moeilijkste 9x9 puzzels, de oscillatoren soms meer tijd nodig hadden om te "dansen" en tot rust te komen, of dat de "kick" misschien niet sterk genoeg was.

Ze suggereren dat toekomstige versies van deze solver wellicht nog complexere, "niet-lineaire" oscillatoren (dansers met complexere bewegingen) zouden kunnen gebruiken of de "kick"-functie nog beter zouden kunnen afstemmen om regelbrekers te vangen. Maar voor nu hebben ze aangetoond dat we, door een eenvoudige, slimme regel toe te voegen aan de fysica van deze dansende netwerken, Sudoku-puzzels veel beter kunnen oplossen dan voorheen. Het is een kleine stap, maar het bewijst dat je soms, om een kapot systeem te repareren, alleen maar een kleine duw in de juiste richting nodig hebt.

Technische Samenvatting: Grafiekkleuringsbenadering voor het oplossen van Sudoku met Oscillerende Neurale Netwerken

Probleemstelling
Het artikel behandelt de uitdaging van het oplossen van beperkte combinatorische optimalisatieproblemen (COPs), specifiek het Sudoku-raadsel, met behulp van een natuurkundig gebaseerd computparadigma. Traditionele computerarchitecturen kampen met bottlenecks tussen geheugen en rekenkracht en een hoog energieverbruik wanneer ze NP-harde problemen aanpakken waarbij de oplostijd exponentieel schaalt met de probleemgrootte. De auteurs stellen voor om Oscillerende Neurale Netwerken (ONNs) te gebruiken, die een onderliggende energiefunctie minimaliseren via de dynamiek van gekoppelde oscillatoren, als alternatief voor conventionele Kunstmatige Neurale Netwerken en Hopfield Neurale Netwerken (HNN's). De specifieke uitdaging ligt in het mappen van Sudoku-regels—waarbij geen enkel cijfer mag herhalen in een rij, kolom of blok—naar de fase-dynamica van oscillatoren zonder regelovertredingen toe te staan (bijv. twee oscillatoren in dezelfde rij die op dezelfde "cijfer"-fase terechtkomen).

Methodologie
De auteurs formuleren Sudoku als een grafiekkleuringsprobleem (Graph Coloring), waarbij elke cel een knoop is en randen knopen die een rij, kolom of blok delen verbinden. Het doel is om een unieke "kleur" (fase) aan elke knoop toe te wijzen.

Fase-mapping: Voor een Sudoku van grootte $N \times N$ (waarbij $K=N$ ), worden de ideale fasen gemapt naar discrete waarden: $\phi_{ideal} = \frac{2\pi(k-1)}{K}$ voor $k \in \{1, ..., K\}$ .
Gemodificeerde ODE: De auteurs bekritiseren bestaande ONN Grafiekkleuringsmodellen (specifiek de Max-K-Cut formulering) omdat deze computationeel duur zijn vanwege instelbare parameters en omdat ze potentieel ongeldige wortels toestaan waarbij oscillatoren op dezelfde fase tot rust komen ondanks dat ze verbonden zijn. Ze stellen een vereenvoudigde, computationeel goedkopere Gewone Differentiaalvergelijking (ODE) voor voor de oscillator-dynamiek:
$\dot{\phi}_i = -f_{unknown}(\phi_i) \left[ \frac{1}{N} \sum_{j} W_{ij} \sin\left(\frac{K}{2}(\phi_i - \phi_j)\right) + K_S \sin(K\phi_i) \right] + f_{unknown}(\phi_i) K_G \sum_{j} W'_{ij} g(\phi_i, \phi_j)$
- Eerste term: Stuurt oscillatoren aan om gescheiden te worden door $\frac{2\pi}{K}$ (Max-K-Cut logica).
- Tweede term ( $K_S$ ): Dwingt oscillatoren om te stabiliseren bij de specifieke ideale fasewaarden.
- Derde term (Nieuwe Bijdrage): Een extra term met een functie $g(\phi_i, \phi_j)$ die detecteert of twee verbonden oscillatoren op dezelfde fase zijn gestabiliseerd (een regelovertreding). Als een overtreding wordt gedetecteerd, injecteert deze term een gradiënt om de oscillatoren uit die stabiele staat te "trappen".
Gewichtsmatrix ( $W_{ij}$ ): De gewichten zijn zo ontworpen dat bekende cijfers een sterkere invloed uitoefenen dan onbekende cijfers. Bekende cijfers zijn vastgezet (nul gradiënt), terwijl onbekende cijfers interageren met hun buren. Het gewicht tussen twee onbekenden in dezelfde rij/kolom/blok is negatief maar kleiner in magnitude dan het gewicht dat een bekend cijfer betreft.
Ordeparameter ( $\kappa$ ): Een metriek wordt gedefinieerd om convergentie te volgen, waarbij waarden nabij 1 duiden op succesvolle convergentie naar de vooraf vastgestelde ideale fasen.

Kernbijdragen

Nieuwe ONN Formulering: Het artikel introduceert een gemodificeerd ONN-solver die Sudoku herformuleert als een grafiekkleuringsprobleem, maar een specifieke term voor het afdwingen van restricties toevoegt aan de ODE. Deze term zorgt ervoor dat het systeem alleen een verdwijnende gradiënt bereikt (stabiele staat) wanneer alle Sudoku-restricties zijn voldaan, wat "vals positieven" voorkomt waarbij oscillatoren identieke fasen aannemen voor verbonden knopen.
Computationele Efficiëntie: De auteurs vervangen de complexe, parameter-zware Max-K-Cut ODE door een eenvoudiger, computationeel goedkoper model dat geen instelbare piekbreedte-parameters vereist voor de interactiefunctie.
Benchmarking: De studie biedt een uitgebreide nauwkeurigheidsvergelijking tegenover een gevestigde HNN-solver en een conventionele ONN Sudoku-solver over $4 \times 4$ en $9 \times 9$ puzzels met variërende ratio's van onbekende cijfers.

Resultaten

$4 \times 4$ Puzzels: De voorgestelde solver bereikte bijna foutloze nauwkeurigheid over alle geteste ratio's van onbekende cijfers (tot 87,5%), waarmee het zowel de HNN als de conventionele ONN-solvers aanzienlijk versloeg. De HNN-solver faalde volledig voor onbekende ratio's boven de 60%, terwijl de conventionele ONN-solver daalde naar ~80% nauwkeurigheid bij 50% onbekenden.
$9 \times 9$ Puzzels: De voorgestelde solver demonstreerde superieure prestaties vergeleken met de andere methoden. Het bereikte perfecte nauwkeurigheid voor onbekende ratio's tot 25% en behield meer dan 80% nauwkeurigheid bij 37,5% onbekenden. Echter, de prestaties verslechterden naarmate het aantal onbekenden toenam, met een daling naar ~50% bij 50% onbekenden, en slaagde er niet in om puzzels correct op te lossen voor onbekende ratio's groter dan 70%.
Ordeparameters: Er was een sterke correlatie tussen nauwkeurigheid en de ordeparameter. Hoge nauwkeurigheid kwam overeen met ordeparameters nabij 1 (convergentie naar ideale fasen), terwijl lagere nauwkeurigheid correleerde met lagere ordeparameters, wat suggereert dat het systeem er niet in slaagde een geldige stabiele staat te bereiken.

Betekenis en Claims
Het artikel claimt dat de voorgestelde aanpak bestaande HNN en ONN Sudoku-solvers aanzienlijk overtreft in termen van nauwkeurigheid, met name voor kleinere roosters ( $4 \times 4$ ) en matig beperkte $9 \times 9$ roosters. De auteurs schrijven dit succes toe aan de extra term in de ODE, die effectief de ongeldige stabiele staten elimineert die weliswaar de energie minimaliseren maar de Sudoku-regels schenden.

De auteurs erkennen bescheiden de beperkingen, waarbij zij opmerken dat het model steunt op vier instelbare parameters, waardoor de parameter-sweep kostbaar is. Zij suggereren dat voor grotere ratio's van onbekenden in $9 \times 9$ puzzels, de extra term mogelijk niet sterk genoeg schaalt, of dat het systeem meer oscillerende cycli nodig heeft om te stabiliseren. Het artikel concludeert dat het uitbreiden van ODE's met restrictie-afdwingende termen een relevante strategie is voor het oplossen van COPs met ONNs en stelt voor dat toekomstig werk zeer niet-lineaire oscillatoren en alternatieve formuleringen voor de restrictie-afdwingende functie moet verkennen.

De Grote Sudoku Danswedstrijd

Het Probleem met de Oude Dansbewegingen

De Nieuwe "Kick"-term

De Resultaten: Een Vlekkeloze Prestatie

Wat Nu?

Meer zoals dit