🤖 machine learning

Graph Coloring Approach to Solving Sudoku with Oscillatory Neural Networks

Cet article présente un solveur de réseau de neurones oscillants (ONN) optimisé qui reformule le Sudoku en tant que problème de coloration de graphe, atteignant une précision nettement supérieure aux approches HNN et ONN existantes sur les puzzles $4 \times 4$ et $9 \times 9$ .

Auteurs originaux : Filip Sabo, Aida Todri-Sanial

Publié 2026-07-20

📖 8 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Filip Sabo, Aida Todri-Sanial

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez un monde où les ordinateurs ne se contentent pas de brasser des chiffres comme une calculatrice ultra-rapide, mais dansent plutôt au rythme d'une mélodie. C'est le domaine des réseaux de neurones oscillatoires (ONN), un type d'informatique « basée sur la physique ». Au lieu d'utiliser des commutateurs électroniques standards, ces réseaux utilisent de minuscules unités vibrantes appelées oscillateurs. Voyez cela comme une pièce remplie de métronomes ou une chorale de chanteurs. Dans ce système, l'information n'est pas stockée sous la forme d'un simple bit « on » ou « off » ; elle est stockée dans le rythme des vibrations, appelé phases. Si deux oscillateurs vibrent en parfaite synchronisation, ils sont « en phase » ; s'ils vibrent à des moments opposés, ils sont « hors phase ».

L'objectif de ces réseaux est de trouver un état d'harmonie parfaite, ou le niveau d'énergie le plus bas, où tous les oscillateurs se stabilisent dans un motif stable. Cette approche est particulièrement efficace pour résoudre des problèmes d'optimisation combinatoire — des casse-têtes où vous devez disposer un ensemble de pièces pour qu'elles respectent des règles spécifiques sans aucun conflit. Vous avez peut-être entendu parler du problème de la coloration de graphe, qui consiste à essayer de colorier une carte de manière à ce que deux pays voisins ne partagent pas la même couleur. Si vous pouvez amener un réseau d'oscillateurs à se stabiliser naturellement dans un motif où les « voisins » ne vibrent pas au même moment, vous avez résolu un puzzle complexe en utilisant les lois de la physique plutôt qu'un calcul mathématique par force brute. Cela importe car les ordinateurs traditionnels ont du mal avec ce type de puzzles, consommant souvent des quantités massives d'électricité et de temps, alors que ces oscillateurs dansants pourraient offrir une façon de réfléchir plus rapide et plus économe en énergie.

Le Grand Duel de Danse du Sudoku

Parlons maintenant du Sudoku. Vous connaissez la règle : une grille de nombres où vous devez remplir les cases vides afin que chaque ligne, chaque colonne et chaque petit carré contienne les chiffres de 1 à 9 (ou de 1 à 4 pour les versions plus petites) sans aucune répétition. C'est un classique de la logique, mais pour un ordinateur, c'est un énorme casse-tête de tâtonnements et d'erreurs.

Les chercheurs de cet article, Filip Sabo et Aida Todri-Sanial de l'Université de technologie d'Eindhoven, ont décidé de s'attaquer au Sudoku en utilisant leur réseau d'oscillateurs « dansants ». Ils ont traité la grille de Sudoku comme un problème de coloration de graphe. Imaginez que chaque cellule vide de la grille de Sudoku est un danseur. La règle est simple : aucun de deux danseurs dans la même ligne, colonne ou carré ne peut porter la même « couleur » (ce qui, dans ce cas, représente un nombre spécifique comme 1, 2 ou 3).

Dans le monde des oscillateurs, « porter une couleur » signifie vibrer à un rythme spécifique. Pour un Sudoku 9x9, il existe 9 rythmes possibles (phases) que les oscillateurs peuvent choisir. Le travail du réseau est de faire en sorte que tous les danseurs choisissent un rythme tel qu'aucun voisin ne fasse le même mouvement de danse.

Le Problème des Anciens Pas de Danse

Les auteurs ont examiné comment d'autres scientifiques avaient tenté de résoudre cela auparavant. Une méthode impliquait une formule mathématique complexe qui était très coûteuse à calculer, comme si l'on essayait de chorégraphier une danse en calculant chaque mouvement musculaire à l'avance. Une autre méthode utilisait une approche plus simple, mais elle présentait un défaut fatal : elle permettait aux danseurs de tricher.

Imaginez un scénario où deux danseurs dans la même ligne décident tous deux de faire la danse du « Nombre 1 ». Dans les anciens modèles plus simples, le réseau pourrait penser : « Hé, ils font tous les deux le rythme du Numéro 1, ce qui est un rythme valide, donc tout va bien ! » Mais dans le Sudoku, c'est un désastre. Les règles stipulent que vous ne pouvez pas avoir deux 1 dans la même ligne. Les anciens modèles n'avaient aucun moyen d'expulser les danseurs de cet état indésirable s'ils se synchronisaient accidentellement sur le mauvais nombre.

Le Nouveau Terme de « Coup »

Pour corriger cela, les auteurs ont inventé une nouvelle façon plus simple de faire danser les oscillateurs, et ils ont ajouté un mécanisme spécial de « coup » (ou impulsion).

Le Rythme Plus Simple : Au lieu d'utiliser la formule mathématique complexe et coûteuse, ils ont utilisé une équation plus propre et plus directe. Cela a rendu la simulation informatique beaucoup plus rapide et moins coûteuse.
Le « Coup » (La Recette Secrète) : C'est la partie la plus importante. Ils ont ajouté un terme spécial aux équations qui agit comme un arbitre. Si deux danseurs dans la même ligne, colonne ou carré commencent accidentellement à vibrer exactement à la même fréquence (ce qui signifie qu'ils ont choisi le même nombre), ce arbitre leur donne un « coup » sec. Cela les pousse hors de cet état stable et confortable et les force à essayer un autre rythme.

Ce « coup » garantit que le réseau ne se stabilise que lorsque le puzzle est réellement résolu correctement. C'est comme un professeur qui circule dans une classe : si deux élèves murmurent la même mauvaise réponse, le professeur leur tapote l'épaule pour qu'ils s'arrêtent et réfléchissent à nouveau.

Les Résultats : Une Performance Sans Faille

L'équipe a testé son nouveau solveur d'oscillateurs « kick-ass » sur des milliers de puzzles de Sudoku, allant de petites grilles 4x4 aux grilles standard 9x9. Ils ont comparé leurs résultats à deux autres solveurs célèbres : l'un basé sur les réseaux de neurones de Hopfield (HNN) et un autre réseau de neurones oscillatoires standard.

Voici ce qu'ils ont trouvé :

Pour les puzzles 4x4 : Leur nouveau solveur était pratiquement parfait. Il résolvait presque 100 % des puzzles correctement, quel que soit le nombre de chiffres manquants. Les autres solveurs peinaient, la précision chutant brutalement à mesure que les puzzles devenaient plus difficiles (plus de chiffres manquants).
Pour les puzzles 9x9 : Les résultats étaient toujours impressionnants, bien que pas tout à fait parfaits. Lorsque les puzzles avaient peu de chiffres manquants (jusqu'à environ 25 % d'inconnus), leur solveur était irréprochable. Même lorsque les puzzles devenaient plus difficiles (jusqu'à 37,5 % d'inconnus), il en résolvait encore plus de 80 %. Cependant, quand les puzzles devenaient très difficiles (plus de 50 % de chiffres inconnus), le solveur commençait à trébucher, réussissant environ 50 % des cas. Les autres solveurs échouaient beaucoup plus tôt, étant souvent incapables de résoudre correctement les puzzles une fois que les chiffres manquants dépassaient les 40-50 %.

Les chercheurs ont également observé un « paramètre d'ordre », qui est essentiellement un score de la manière dont les oscillateurs ont réussi à se stabiliser dans leurs rythmes finaux et corrects. Ils ont constaté que chaque fois que le solveur réussissait le puzzle, les oscillateurs étaient très bien organisés (paramètre d'ordre élevé). Lorsqu'il échouait, les oscillateurs étaient chaotiques et ne parvenaient pas à s'accorder sur un motif stable.

Et Après ?

Les auteurs sont assez convaincus que leur terme de « coup » est la raison de ce succès, mais ils admettent qu'il reste du travail. Leur modèle possède quelques boutons qu'ils ont dû tourner manuellement (paramètres réglables) pour le faire fonctionner, ce qui a pris beaucoup de temps pour être déterminé. Ils ont également remarqué que pour les puzzles 9x9 les plus difficiles, les oscillateurs avaient parfois besoin de plus de temps pour « danser » et se stabiliser, ou peut-être que le « coup » n'était pas assez fort.

Ils suggèrent que les futures versions de ce solveur pourraient essayer d'utiliser des oscillateurs encore plus complexes, « non linéaires » (des danseurs avec des mouvements plus compliqués) ou de peaufiner la fonction de « coup » pour être encore plus efficace pour attraper les tricheurs. Mais pour l'instant, ils ont montré qu'en ajoutant une règle simple et ingénieuse à la physique de ces réseaux dansants, nous pouvons résoudre les puzzles de Sudoku bien mieux qu'auparavant. C'est un petit pas, mais cela prouve que parfois, tout ce dont on a besoin pour réparer un système défaillant, c'est d'une petite poussée dans la bonne direction.

Résumé technique : Approche par coloration de graphe pour la résolution de Sudoku avec des réseaux de neurones oscillatoires

Énoncé du problème
L'article traite du défi que représente la résolution de problèmes d'optimisation combinatoire contraints (COP), spécifiquement le puzzle Sudoku, en utilisant un paradigme de calcul basé sur la physique. Les architectures informatiques traditionnelles sont confrontées à des goulots d'étranglement entre mémoire et calcul, ainsi qu'à une consommation d'énergie élevée lorsqu'elles abordent des problèmes NP-difficiles où le temps de résolution augmente de manière exponentielle avec la taille du problème. Les auteurs proposent d'utiliser des réseaux de neurones oscillatoires (ONN), qui minimisent une fonction d'énergie sous-jacente via la dynamique d'oscillateurs couplés, comme alternative aux réseaux de neurones artificiels conventionnels et aux réseaux de neurones de Hopfield (HNN). Le défi spécifique réside dans la transposition des règles du Sudoku — où aucun chiffre ne peut se répéter dans une ligne, une colonne ou un bloc — à la dynamique de phase des oscillateurs sans permettre de violations de règles (par exemple, deux oscillateurs dans la même ligne se stabilisant sur la même « phase » de chiffre).

Méthodologie
Les auteurs formulent le Sudoku comme un problème de coloration de graphe, où chaque cellule est un nœud et les arêtes relient les cellules partageant une ligne, une colonne ou un bloc. L'objectif est d'assigner une « couleur » (phase) unique à chaque nœud.

Cartographie de phase : Pour un Sudoku de taille $N \times N$ (où $K=N$ ), les phases idéales sont mappées vers des valeurs discrètes : $\phi_{ideal} = \frac{2\pi(k-1)}{K}$ pour $k \in \{1, ..., K\}$ .
EDO modifiée : Les auteurs critiquent les modèles existants de coloration de graphe par ONN (spécifiquement la formulation Max-K-Cut) qui sont coûteux en termes de calcul en raison de paramètres ajustables et qui peuvent potentiellement permettre des racines invalides où les oscillateurs se stabilisent sur la même phase malgré leur connexion. Ils proposent une équation différentielle ordinaire (EDO) simplifiée et moins coûteuse pour la dynamique des oscillateurs :
$\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)$
- Premier terme : Pousse les oscillateurs à se séparer par $\frac{2\pi}{K}$ (logique Max-K-Cut).
- Deuxième terme ( $K_S$ ) : Force les oscillateurs à se stabiliser aux valeurs de phase idéales spécifiques.
- Troisième terme (Contribution novatrice) : Un terme supplémentaire impliquant une fonction $g(\phi_i, \phi_j)$ qui détecte si deux oscillateurs connectés se sont stabilisés sur la même phase (une violation de règle). Si une violation est détectée, ce terme injecte un gradient pour « éjecter » les oscillateurs de cet état stable.
Matrice de poids ( $W_{ij}$ ) : Les poids sont conçus de telle sorte que les chiffres connus exercent une influence plus forte que les chiffres inconnus. Les chiffres connus sont fixes (gradient nul), tandis que les chiffres inconnus interagissent avec leurs voisins. Le poids entre deux inconnus dans la même ligne/colonne/bloc est négatif mais de plus faible magnitude que le poids impliquant un chiffre connu.
Paramètre d'ordre ( $\kappa$ ) : Une métrique est définie pour suivre la convergence, où les valeurs proches de 1 indiquent une convergence réussie vers les phases idéales préétablies.

Principales contributions

Nouvelle formulation d'ONN : L'article introduit un solveur ONN modifié qui reformule le Sudoku comme un problème de coloration de graphe, mais ajoute un terme d'application de contrainte spécifique à l'EDO. Ce terme garantit que le système n'atteint un gradient nul (état stable) que lorsque toutes les contraintes du Sudoku sont satisfaites, empêchant les « faux positifs » où les oscillateurs se stabilisent sur des phases identiques pour des nœuds connectés.
Efficacité computationnelle : Les auteurs remplacent l'EDO complexe et riche en paramètres du Max-K-Cut par un modèle plus simple et moins coûteux qui ne nécessite pas de paramètres de largeur de pic ajustables pour la fonction d'interaction.
Évaluation comparative : L'étude fournit une comparaison d'exactitude complète par rapport à un solveur HNN établi et un solveur ONN conventionnel sur des puzzles $4 \times 4$ et $9 \times 9$ avec des ratios variables de chiffres inconnus.

Résultats

Puzzles $4 \times 4$ : Le solveur proposé a atteint une précision quasi parfaite sur tous les ratios d'inconnus testés (jusqu'à 87,5 %), surpassant de manière significative les solveurs HNN et ONN conventionnels. Le solveur HNN a échoué complètement pour des ratios d'inconnus supérieurs à 60 %, tandis que le solveur ONN conventionnel est tombé à environ 80 % de précision à 50 % d'inconnus.
Puzzles $9 \times 9$ : Le solveur proposé a démontré une performance supérieure par rapport aux autres méthodes. Il a atteint une précision parfaite pour des ratios d'inconnus jusqu'à 25 % et a maintenu plus de 80 % de précision à 37,5 % d'inconnus. Cependant, la performance s'est dégradée à mesure que le nombre d'inconnus augmentait, tombant à environ 50 % à 50 % d'inconnus et échouant à résoudre correctement les puzzles pour des ratios d'inconnus supérieurs à 70 %.
Paramètres d'ordre : Il y avait une forte corrélation entre l'exactitude et le paramètre d'ordre. Une haute exactitude correspondait à des paramètres d'ordre proches de 1 (convergence vers les phases idéales), tandis qu'une exactitude plus faible était corrélée à des paramètres d'ordre plus bas, suggérant que le système ne parvenait pas à se stabiliser dans un état stable valide.

Signification et affirmations
L'article affirme que l'approche proposée surpasse significativement les solveurs Sudoku HNN et ONN existants en termes d'exactitude, particulièrement pour les grilles plus petites ( $4 \times 4$ ) et les grilles $9 \times 9$ modérément contraintes. Les auteurs attribuent ce succès au terme supplémentaire dans l'EDO, qui élimine efficacement les états stables invalides qui satisfont la minimisation de l'énergie mais violent les règles du Sudoku.

Les auteurs reconnaissent modestement les limites, notant que le modèle repose sur quatre paramètres ajustables, rendant le balayage des paramètres coûteux. Ils suggèrent que pour des ratios d'inconnus plus élevés dans les puzzles $9 \times 9$ , le terme supplémentaire peut ne pas être mis à l'échelle assez fortement, ou que le système pourrait nécessiter plus de cycles oscillatoires pour se stabiliser. L'article conclut que les EDO étendues avec des termes d'application de contraintes sont une stratégie pertinente pour résoudre les COP avec des ONN et suggère que les travaux futurs devraient explorer des oscillateurs hautement non linéaires et des formulations alternatives pour la fonction d'application de contrainte.

Le Grand Duel de Danse du Sudoku

Le Problème des Anciens Pas de Danse

Le Nouveau Terme de « Coup »

Les Résultats : Une Performance Sans Faille

Et Après ?

Articles similaires