🤖 machine learning

Graph Coloring Approach to Solving Sudoku with Oscillatory Neural Networks

Dieses Paper stellt einen optimierten Solver für ein Oszillatorisches Neuronales Netz (ONN) vor, der Sudoku als Graphenfärbungsproblem umformuliert und dabei eine signifikant höhere Genauigkeit als bestehende HNN- und ONN-Ansätze bei sowohl $4 \times 4$ - als auch $9 \times 9$ -Rätseln erzielt.

Ursprüngliche Autoren: Filip Sabo, Aida Todri-Sanial

Veröffentlicht 2026-07-20

📖 7 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Filip Sabo, Aida Todri-Sanial

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich eine Welt vor, in der Computer nicht nur Zahlen wie ein superschneller Taschenrechner verarbeiten, sondern zu einem Rhythmus tanzen. Dies ist das Reich der oszillierenden neuronalen Netze (ONNs), einer Art von „physikbasierter“ Computertechnik. Anstatt herkömmliche elektronische Schalter zu verwenden, nutzen diese Netzwerke winzige, vibrierende Einheiten, die Oszillatoren. Denken Sie an einen Raum voller Metronome oder einen Chor von Sängern. In diesem System wird Information nicht als einfaches „An“ oder „Aus“-Bit gespeichert, sondern in der Zeitierung der Schwingungen, bekannt als Phasen. Wenn zwei Oszillatoren in perfekter Harmonie schwingen, sind sie „in Phase“; wenn sie zu entgegengesetzten Zeiten schwingen, sind sie „außer Phase“.

Das Ziel dieser Netzwerke ist es, einen Zustand vollkommener Harmonie oder der niedrigstmöglichen Energie zu finden, in dem sich alle Oszillatoren in einem stabilen Muster einpendeln. Dieser Ansatz eignet sich besonders gut zur Lösung von kombinatorischen Optimierungsproblemen – Rätseln, bei denen man eine Reihe von Teilen so anordnen muss, dass sie spezifische Regeln erfüllen, ohne dass es zu Kollisionen kommt. Sie haben vielleicht schon vom Graphenfärbungsproblem gehört, das ähnlich ist wie der Versuch, eine Landkarte so einzufärben, dass keine zwei benachbarten Länder dieselbe Farbe haben. Wenn Sie ein Netzwerk von Oszillatoren dazu bringen können, sich natürlich in einem Muster einzupendeln, bei dem keine „Nachbarn“ zur gleichen Zeit schwingen, haben Sie ein komplexes Rätsel mithilfe der Gesetze der Physik statt durch bloße Brute-Force-Mathematik gelöst. Dies ist wichtig, da traditionelle Computer mit diesen Arten von Rätseln oft Schwierigkeiten haben und dabei enorme Mengen an Elektrizität und Zeit verbrauchen, während diese tanzenden Oszillatoren eine schnellere, energieeffizientere Art des Denkens bieten könnten.

Das große Sudoku-Tanzduell

Lassen Sie uns nun über Sudoku sprechen. Sie kennen das Prinzip: ein Gitter aus Zahlen, bei dem Sie die Lücken so füllen müssen, dass jede Zeile, jede Spalte und jedes kleine Quadrat die Ziffern 1 bis 9 (oder 1 bis 4 für die kleinere Version) enthält, ohne dass Zahlen doppelt vorkommen. Es ist ein klassisches Logikrätsel, aber für einen Computer ist es ein massives Kopfzerbrechen aus Versuch und Irrtum.

Die Forscher in dieser Arbeit, Filip Sabo und Aida Todri-Sanial von der Eindhoven University of Technology, beschlossen, Sudoku mit ihrem „tanzenden Oszillator“-Netzwerk anzugehen. Sie behandelten das Sudoku-Gitter wie ein Graphenfärbungsproblem. Stellen Sie sich vor, jede leere Zelle im Sudoku-Gitter ist ein Tänzer. Die Regel ist einfach: Keine zwei Tänzer in derselben Zeile, Spalte oder demselben Block dürfen dieselbe „Farbe“ tragen (was in diesem Fall eine spezifische Zahl wie 1, 2 oder 3 repräsentiert).

In der Welt der Oszillatoren bedeutet „eine Farbe tragen“, mit einem bestimmten Rhythmus zu schwingen. Für ein 9x9-Sudoku gibt es 9 mögliche Rhythmen (Phasen), zwischen denen die Oszillatoren wählen können. Die Aufgabe des Netzwerks besteht darin, alle Tänzer dazu zu bringen, einen Rhythmus zu wählen, sodass keine zwei Nachbarn dieselbe Tanzbewegung ausführen.

Das Problem mit den alten Tanzbewegungen

Die Autoren untersuchten, wie andere Wissenschaftler dies zuvor versucht haben. Eine Methode basierte auf einer komplexen mathematischen Formel, die sehr rechenintensiv war – so als würde man versuchen, eine Choreografie zu entwerfen, indem man im Voraus jede einzelne Muskelbewegung berechnet. Eine andere Methode nutzte einen einfacheren Ansatz, hatte aber einen fatalen Fehler: Sie erlaubte den Tänzern zu betrügen.

Stellen Sie sich ein Szenario vor, in dem zwei Tänzer in derselben Zeile beschließen, beide den „Nummer 1“-Tanz zu machen. In den alten, einfacheren Modellen könnte das Netzwerk denken: „Hey, sie machen beide den ‚Nummer 1‘-Rhythmus, was ein gültiger Rhythmus ist, also ist alles in Ordnung!“ Aber beim Sudoku ist das eine Katastrophe. Die Regeln besagen, dass man nicht zwei Einsen in derselben Zeile haben darf. Die alten Modelle hatten keine Möglichkeit, die Tänzer aus diesem schlechten Zustand herauszukicken, falls sie sich versehentlich auf die falsche Zahl synchronisierten.

Der neue „Kick“-Term

Um dies zu beheben, erfanden die Autoren einen neuen, einfacheren Weg, die Oszillatoren tanzen zu lassen, und fügten einen speziellen „Kick“-Mechanismus hinzu.

Der einfachere Rhythmus: Anstatt die komplizierte, teure mathematische Formel zu verwenden, nutzten sie eine sauberere, direktere Gleichung. Dies ermöglichte es der Computersimulation, viel schneller und kostengünstiger zu laufen.
Der „Kick“ (Das Geheimrezept): Dies ist der wichtigste Teil. Sie fügten einen speziellen Term zu den Gleichungen hinzu, der wie ein Schiedsrichter fungiert. Wenn zwei Tänzer in derselben Zeile, Spalte oder demselben Block versehentlich anfangen, mit exakt derselben Frequenz zu schwingen (das heißt, sie haben dieselbe Zahl gewählt), gibt dieser Schiedsrichter ihnen einen scharfen „Kick“. Er stößt sie aus diesem stabilen, komfortablen Zustand heraus und zwingt sie, einen anderen Rhythmus auszuprobieren.

Dieser „Kick“ stellt sicher, dass sich das Netzwerk nur dann zur Ruhe setzt, wenn das Rätsel tatsächlich korrekt gelöst wurde. Es ist wie ein Lehrer, der durch ein Klassenzimmer geht: Wenn zwei Schüler versehentlich die gleiche falsche Antwort flüstern, tippt der Lehrer ihnen auf die Schulter, damit sie aufhören und wieder neu nachdenken.

Die Ergebnisse: Eine makellose Performance

Das Team testete ihren neuen „Kick-Ass“-Oszillator-Solver an tausenden Sudoku-Rätseln, die von kleinen 4x4-Gittern bis hin zu den Standard-9x9-Gittern reichten. Sie verglichen ihre Ergebnisse mit zwei anderen berühmten Solvern: einem, der auf Hopfield-Neuronalen Netzen (HNN) basiert, und einem Standard-Oszillations-Neuronalen-Netzwerk.

Hier ist, was sie fanden:

Für die 4x4-Rätsel: Ihr neuer Solver war praktisch perfekt. Er löste fast 100 % der Rätsel korrekt, unabhängig davon, wie viele Zahlen fehlten. Die anderen Solver hatten Schwierigkeiten, wobei die Genauigkeit drastisch sank, sobald die Rätsel schwieriger wurden (mehr fehlende Zahlen).
Für die 9x9-Rätsel: Die Ergebnisse waren immer noch beeindruckend, wenn auch nicht perfekt. Wenn die Rätsel weniger fehlende Zahlen hatten (bis zu etwa 25 % unbekannt), war ihr Solver makellos. Selbst wenn die Rätsel schwieriger wurden (bis zu 3et 37,5 % unbekannt), löste er immer noch mehr als 80 % davon. Wenn die Rätsel jedoch sehr schwierig wurden (mehr als 50 % unbekannte Zahlen), geriet der Solver ins Straucheln und löste etwa 50 % korrekt. Die anderen Solver scheiterten viel früher und konnten oft keine Rätsel mehr korrekt lösen, sobald die Anzahl der fehlenden Zahlen 40–50 % überschritt.

Die Forscher betrachteten auch einen „Ordnungsparameter“, der im Grunde ein Score dafür ist, wie gut die Oszillatoren es geschafft haben, sich in ihre endgültigen, korrekten Rhythmen einzupendeln. Sie fanden heraus, dass der Solver das Rätsel immer dann richtig löste, wenn die Oszillatoren sehr gut organisiert waren (hoher Ordnungsparameter). Wenn er das Rätsel falsch löste, waren die Oszillatoren chaotisch und konnten sich nicht auf ein stabiles Muster einigen.

Was kommt als Nächstes?

Die Autoren sind sehr zuversichtlich, dass ihr „Kick“-Term der Grund für den Erfolg ist, geben aber zu, dass noch Arbeit zu leisten ist. Ihr Modell hatte einige Knöpfe (einstellbare Parameter), an denen sie drehen mussten, um es zum Laufen zu bringen, was viel Zeit in Anspruch nahm, um sie zu verstehen. Sie stellten auch fest, dass die Oszillatoren bei den schwierigsten 9x9-Rätseln manchmal mehr Zeit zum „Tanzen“ und zur Beruhigung benötigten, oder dass der „Kick“ vielleicht nicht stark genug war.

Sie schlagen vor, dass zukünftige Versionen dieses Solvers vielleicht noch komplexere, „nichtlineare“ Oszillatoren (Tänzer mit komplizierteren Bewegungen) verwenden oder die „Kick“-Funktion noch besser anpassen könnten, um Regelbrecher zu überführen. Aber für den Moment haben sie gezeigt, dass wir, indem wir eine einfache, kluge Regel zur Physik dieser tanzenden Netzwerke hinzufügen, Sudoku-Rätsel viel besser lösen können als zuvor. Es ist ein kleiner Schritt, aber er beweist, dass man manchmal nur einen kleinen Anstoß in die richtige Richtung braucht, um ein kaputtes System zu reparieren.

Technische Zusammenfassung: Graphfarben-Ansatz zur Lösung von Sudoku mit oszillierenden neuronalen Netzen

Problemstellung
Die Arbeit befasst sich mit der Herausforderung, kombinatorische Optimierungsprobleme mit Einschränkungen (Constrained Combinatorial Optimization Problems, COPs), speziell das Sudoku-Rätsel, unter Verwendung eines physikbasierten Rechenparadigmas zu lösen. Traditionelle Computerarchitekturen stehen vor Engpässen zwischen Speicher und Rechenleistung sowie einem hohen Energieverbrauch, wenn sie NP-schwere Probleme bewältigen müssen, bei denen die Zeit bis zur Lösungsfindung exponentiell mit der Problemgröße skaliert. Die Autoren schlagen vor, Oszillierende Neuronale Netze (ONNs) einzusetzen, die eine zugrunde liegende Energiefunktion durch die Dynamik gekoppelter Oszillatoren minimieren, als Alternative zu konventionellen künstlichen Neuronalen Netzen und Hopfield-Neuronalen Netzen (HNNs). Die spezifische Herausforderung besteht darin, die Sudoku-Regeln – wonach keine Ziffer in jeder Zeile, Spalte oder jedem Block doppelt vorkommen darf – auf die Phasendynamik von Oszillatoren abzubilden, ohne Regelverstöße zuzulassen (z. B. dass zwei Oszillatoren in derselben Zeile auf dieselbe „Ziffern“-Phase einschwingen).

Methodik
Die Autoren formulieren Sudoku als Graphfärbungsproblem, bei dem jede Zelle ein Knoten ist und Kanten Zellen verbinden, die eine Zeile, Spalte oder einen Block teilen. Das Ziel ist es, jedem Knoten eine eindeutige „Farbe“ (Phase) zuzuweisen.

Phasen-Mapping: Für ein Sudoku der Größe $N \times N$ (wobei $K=N$ ist), werden die idealen Phasen auf diskrete Werte abgebildet: $\phi_{ideal} = \frac{2\pi(k-1)}{K}$ für $k \in \{1, ..., K\}$ .
Modifizierte ODE: Die Autoren kritisieren bestehende ONN-Graphfärbungsmodelle (speziell die Max-K-Cut-Formulierung) als rechenintensiv aufgrund von abstimmbaren Parametern und dafür, dass sie potenziell ungültige Wurzeln zulassen, bei denen Oszillatoren auf dieselbe Phase einschwingen, obwohl sie miteinander verbunden sind. Sie schlagen eine vereinfachte, recheneffizientere Gewöhnliche Differentialgleichung (ODE) für die Oszillatordynamik vor:
$\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)$
- Erster Term: Treibt die Oszillatoren dazu, durch $\frac{2\pi}{K}$ voneinander getrennt zu sein (Max-K-Cut-Logik).
- Zweiter Term ( $K_S$ ): Erzwingt, dass die Oszillatoren auf den spezifischen idealen Phasenwerten zur Ruhe kommen.
- Dritter Term (Neuheit): Ein zusätzlicher Term, der eine Funktion $g(\phi_i, \phi_j)$ beinhaltet, die erkennt, ob zwei verbundene Oszillatoren auf dieselbe Phase eingeschwenkt sind (ein Regelverstoß). Wenn ein Verstoß erkannt wird, injiziert dieser Term einen Gradienten, um die Oszillatoren aus diesem stabilen Zustand „herauszukicken“.
Gewichtsmatrix ( $W_{ij}$ ): Die Gewichte sind so gestaltet, dass bekannte Ziffern einen stärkeren Einfluss ausüben als unbekannte Ziffern. Bekannte Ziffern sind fixiert (Null-Gradient), während unbekannte Ziffern mit ihren Nachbarn interagieren. Das Gewicht zwischen zwei Unbekannten in derselben Zeile/Spalte/Box ist negativ, aber geringer in der Magnitude als das Gewicht, das eine bekannte Ziffer betrifft.
Ordnungsparameter ( $\kappa$ ): Eine Metrik wird definiert, um die Konvergenz zu verfolgen, wobei Werte nahe 1 darauf hindeuten, dass eine erfolgreiche Konvergenz zu den zuvor festgelegten idealen Phasen stattgefunden hat.

Wesentliche Beiträge

Neuartige ONN-Formulierung: Die Arbeit führt einen modifizierten ONN-Solver ein, der Sudoku als Graphfärbungsproblem formuliert, aber einen spezifischen Term zur Durchsetzung von Nebenbedingungen in die ODE integriert. Dieser Term stellt sicher, dass das System nur dann einen verschwindenden Gradienten (stabilen Zustand) erreicht, wenn alle Sudoku-Bedingungen erfüllt sind, wodurch „False Positives“ verhindert werden, bei denen Oszillatoren auf identische Phasen für verbundene Knoten einschwingen.
Recheneffizienz: Die Autoren ersetzen die komplexe, parameterintensive Max-K-Cut-ODE durch ein einfacheres, recheneffizienteres Modell, das keine abstimmbaren Peak-Breiten-Parameter für die Interaktionsfunktion benötigt.
Benchmarking: Die Studie bietet einen umfassenden Genauigkeitsvergleich gegenüber einem etablierten HNN-Solver und einem konventionellen ONN-Sudoku-Solver über $4 \times 4$ und $9 \times 9$ Rätsel mit variierenden Anteilen unbekannter Ziffern.

Ergebnisse

$4 \times 4$ Rätsel: Der vorgeschlagene Solver erreichte eine nahezu makellose Genauigkeit über alle getesteten Anteile unbekannter Ziffern (bis zu 87,5 %) und übertraf damit sowohl den HNN- als auch den konventionellen ONN-Solver signifikant. Der HNN-Solver versagte vollständig bei Anteilen Unbekannter über 60 %, während der konventionelle ONN-Solver bei 50 % Unbekannten auf ~80 % Genauigkeit abfiel.
$9 \times 9$ Rätsel: Der vorgeschlagene Solver zeigte eine überlegene Leistung im Vergleich zu den anderen Methoden. Er erreichte eine perfekte Genauigkeit für Anteile Unbekannter bis zu 25 % und hielt eine Genauigkeit von über 80 % bei 37,5 % Unbekannten. Die Leistung verschlechterte sich jedoch, wenn die Anzahl der Unbekannten zunahm, und sank auf ~50 % bei 50 % Unbekannten, wobei er Rätsel mit einem Anteil an Unbekannten von mehr als 70 % nicht korrekt lösen konnte.
Ordnungsparameter: Es bestand eine starke Korrelation zwischen Genauigkeit und Ordnungsparameter. Hohe Genauigkeit entsprach Ordnungsparametern nahe 1 (Konvergenz zu idealen Phasen), während eine geringere Genauigkeit mit niedrigeren Ordnungsparametern korrelierte, was darauf hindeutet, dass das System nicht in einen gültigen stabilen Zustand überging.

Bedeutung und Behauptungen
Die Arbeit behauptet, dass der vorgeschlagene Ansatz bestehende HNN- und ONN-Sudoku-Solver in Bezug auf die Genauigkeit deutlich übertrifft, insbesondere bei kleineren Gittern ( $4 \times 4$ ) und moderat eingeschränkten $9 \times 9$ Gittern. Die Autoren führen diesen Erfolg auf den zusätzlichen Term in der ODE zurück, der effektiv ungültige stabile Zustände eliminiert, die zwar die Energieminimierung erfüllen, aber gegen die Sudoku-Regeln verstoßen.

Die Autoren räumen bescheiden Einschränkungen ein und merken an, dass das Modell auf vier abstimmbare Parameter angewiesen ist, was die Parameter-Suche (Parameter Sweep) kostspielig macht. Sie schlagen vor, dass für größere Anteile Unbekannter in $9 \times 9$ Rätseln der zusätzliche Term möglicherweise nicht stark genug skaliert oder das System mehr oszillatorische Zyklen benötigt, um zu stabilisieren. Die Arbeit schließt mit dem Hinweis, dass die Erweiterung von ODEs durch bedingungsdurchsetzende Terme eine relevante Strategie zur Lösung von COPs mit ONNs ist, und schlägt vor, dass zukünftige Arbeiten hochgradig nichtlineare Oszillatoren und alternative Formulierungen für die Bedingungsdurchsetzungsfunktion untersuchen sollten.

Das große Sudoku-Tanzduell

Das Problem mit den alten Tanzbewegungen

Der neue „Kick“-Term

Die Ergebnisse: Eine makellose Performance

Was kommt als Nächstes?

Mehr davon