🤖 machine learning

Graph Coloring Approach to Solving Sudoku with Oscillatory Neural Networks

This paper introduces an optimized Oscillatory Neural Network (ONN) solver that reformulates Sudoku as a Graph Coloring problem, achieving significantly higher accuracy than existing HNN and ONN approaches on both $4 \times 4$ and $9 \times 9$ puzzles.

Original authors: Filip Sabo, Aida Todri-Sanial

Published 2026-07-20

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Filip Sabo, Aida Todri-Sanial

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 a world where computers don't just crunch numbers like a super-fast calculator, but instead dance to a rhythm. This is the realm of Oscillatory Neural Networks (ONNs), a type of "physics-based" computing. Instead of using standard electronic switches, these networks use tiny, vibrating units called oscillators. Think of them like a room full of metronomes or a choir of singers. In this system, information isn't stored as a simple "on" or "off" bit; it's stored in the timing of the vibrations, known as phases. If two oscillators vibrate in perfect sync, they are "in phase"; if they vibrate at opposite times, they are "out of phase."

The goal of these networks is to find a state of perfect harmony, or the lowest possible energy, where all the oscillators settle into a stable pattern. This approach is particularly good at solving combinatorial optimization problems—puzzles where you have to arrange a bunch of pieces to fit specific rules without any clashes. You might have heard of the Graph Coloring problem, which is like trying to color a map so that no two neighboring countries share the same color. If you can get a network of oscillators to naturally settle into a pattern where no "neighbors" are vibrating at the same time, you've solved a complex puzzle using the laws of physics rather than just brute-force math. This matters because traditional computers struggle with these types of puzzles, often burning through massive amounts of electricity and time, whereas these dancing oscillators might offer a faster, more energy-efficient way to think.

The Great Sudoku Dance-Off

Now, let's talk about Sudoku. You know the drill: a grid of numbers where you have to fill in the blanks so that every row, column, and little box contains the digits 1 through 9 (or 1 through 4 for the smaller version) without any repeats. It's a classic logic puzzle, but for a computer, it's a massive headache of trial and error.

The researchers in this paper, Filip Sabo and Aida Todri-Sanial from Eindhoven University of Technology, decided to tackle Sudoku using their "dancing oscillator" network. They treated the Sudoku grid like a Graph Coloring problem. Imagine each empty cell in the Sudoku grid is a dancer. The rule is simple: no two dancers in the same row, column, or box can be wearing the same "color" (which, in this case, represents a specific number like 1, 2, or 3).

In the world of oscillators, "wearing a color" means vibrating at a specific rhythm. For a 9x9 Sudoku, there are 9 possible rhythms (phases) the oscillators can choose from. The network's job is to get all the dancers to pick a rhythm such that no two neighbors are doing the same dance move.

The Problem with the Old Dance Moves

The authors looked at how other scientists had tried to solve this before. One method involved a complex mathematical formula that was very expensive to compute, like trying to choreograph a dance by calculating every single muscle movement in advance. Another method used a simpler approach, but it had a fatal flaw: it allowed the dancers to cheat.

Imagine a scenario where two dancers in the same row both decide to do the "Number 1" dance. In the old, simpler models, the network might think, "Hey, they are both doing the 'Number 1' rhythm, which is a valid rhythm, so we are good!" But in Sudoku, that's a disaster. The rules say you can't have two 1s in the same row. The old models didn't have a way to kick the dancers out of that bad state if they accidentally synced up on the wrong number.

The New "Kick" Term

To fix this, the authors invented a new, simpler way to make the oscillators dance, and they added a special "kick" mechanism.

The Simpler Rhythm: Instead of using the complicated, expensive math formula, they used a cleaner, more direct equation. This made the computer simulation run much faster and cheaper.
The "Kick" (The Secret Sauce): This is the most important part. They added a special term to the equations that acts like a referee. If two dancers in the same row, column, or box accidentally start vibrating at the exact same frequency (meaning they picked the same number), this referee gives them a sharp "kick." It pushes them out of that stable, comfortable state and forces them to try a different rhythm.

This "kick" ensures that the network only settles down when the puzzle is actually solved correctly. It's like a teacher walking around a classroom: if two students are whispering the same wrong answer, the teacher taps them on the shoulder to make them stop and think again.

The Results: A Flawless Performance

The team tested their new "kick-ass" oscillator solver on thousands of Sudoku puzzles, ranging from small 4x4 grids to the standard 9x9 grids. They compared their results against two other famous solvers: one based on Hopfield Neural Networks (HNN) and another standard Oscillatory Neural Network.

Here is what they found:

For the 4x4 puzzles: Their new solver was practically perfect. It solved nearly 100% of the puzzles correctly, regardless of how many numbers were missing. The other solvers struggled, with accuracy dropping sharply as the puzzles got harder (more missing numbers).
For the 9x9 puzzles: The results were still impressive, though not quite perfect. When the puzzles had fewer missing numbers (up to about 25% unknown), their solver was flawless. Even when the puzzles got harder (up to 37.5% unknown), it still solved more than 80% of them. However, when the puzzles became very difficult (more than 50% unknown numbers), the solver started to stumble, getting about 50% right. The other solvers failed much earlier, often unable to solve any puzzles correctly once the missing numbers passed 40-50%.

The researchers also looked at an "order parameter," which is basically a score of how well the oscillators managed to settle into their final, correct rhythms. They found that whenever the solver got the puzzle right, the oscillators were very well-organized (high order parameter). When it got the puzzle wrong, the oscillators were chaotic and couldn't agree on a stable pattern.

What's Next?

The authors are pretty confident that their "kick" term is the reason for the success, but they admit there's still work to do. Their model has a few knobs they had to turn manually (tuneable parameters) to get it working, which took a lot of time to figure out. They also noticed that for the hardest 9x9 puzzles, the oscillators sometimes needed more time to "dance" and settle down, or perhaps the "kick" wasn't strong enough.

They suggest that future versions of this solver might try using even more complex, "nonlinear" oscillators (dancers with more complicated moves) or tweaking the "kick" function to be even better at catching rule-breakers. But for now, they've shown that by adding a simple, clever rule to the physics of these dancing networks, we can solve Sudoku puzzles much better than before. It's a small step, but it proves that sometimes, all you need to fix a broken system is a little push in the right direction.

Technical Summary: Graph Coloring Approach to Solving Sudoku with Oscillatory Neural Networks

Problem Statement
The paper addresses the challenge of solving constrained combinatorial optimization problems (COPs), specifically the Sudoku puzzle, using a physics-based computing paradigm. Traditional computing architectures face memory-compute bottlenecks and high power consumption when tackling NP-hard problems where solution time scales exponentially with problem size. The authors propose utilizing Oscillatory Neural Networks (ONNs), which minimize an underlying energy function through the dynamics of coupled oscillators, as an alternative to conventional Artificial Neural Networks and Hopfield Neural Networks (HNNs). The specific challenge lies in mapping Sudoku rules—where no digit may repeat in any row, column, or box—to the phase dynamics of oscillators without allowing rule violations (e.g., two oscillators in the same row settling on the same "digit" phase).

Methodology
The authors formulate Sudoku as a Graph Coloring problem, where each cell is a node and edges connect cells sharing a row, column, or box. The goal is to assign a unique "color" (phase) to each node.

Phase Mapping: For a Sudoku of size $N \times N$ (where $K=N$ ), the ideal phases are mapped to discrete values: $\phi_{ideal} = \frac{2\pi(k-1)}{K}$ for $k \in \{1, ..., K\}$ .
Modified ODE: The authors critique existing ONN Graph Coloring models (specifically the Max-K-Cut formulation) for being computationally expensive due to tunable parameters and for potentially allowing invalid roots where oscillators settle on the same phase despite being connected. They propose a simplified, computationally cheaper Ordinary Differential Equation (ODE) for the oscillator dynamics:
$\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)$
- First Term: Drives oscillators to be separated by $\frac{2\pi}{K}$ (Max-K-Cut logic).
- Second Term ( $K_S$ ): Forces oscillators to settle at the specific ideal phase values.
- Third Term (Novel Contribution): An additional term involving a function $g(\phi_i, \phi_j)$ that detects if two connected oscillators have settled on the same phase (a rule violation). If a violation is detected, this term injects a gradient to "kick" the oscillators out of that stable state.
Weight Matrix ( $W_{ij}$ ): The weights are designed such that known digits exert a stronger influence than unknown digits. Known digits are fixed (zero gradient), while unknown digits interact with neighbors. The weight between two unknowns in the same row/column/box is negative but smaller in magnitude than the weight involving a known digit.
Order Parameter ( $\kappa$ ): A metric is defined to track convergence, where values near 1 indicate successful convergence to the pre-established ideal phases.

Key Contributions

Novel ONN Formulation: The paper introduces a modified ONN solver that reformulates Sudoku as a Graph Coloring problem but adds a specific constraint-enforcement term to the ODE. This term ensures that the system only reaches a vanishing gradient (stable state) when all Sudoku constraints are satisfied, preventing the "false positives" where oscillators settle on identical phases for connected nodes.
Computational Efficiency: The authors replace the complex, parameter-heavy Max-K-Cut ODE with a simpler, computationally cheaper model that does not require tunable peak-width parameters for the interaction function.
Benchmarking: The study provides a comprehensive accuracy comparison against an established HNN solver and a conventional ONN Sudoku solver across $4 \times 4$ and $9 \times 9$ puzzles with varying ratios of unknown digits.

Results

$4 \times 4$ Puzzles: The proposed solver achieved nearly flawless accuracy across all tested unknown ratios (up to 87.5%), significantly outperforming both the HNN and conventional ONN solvers. The HNN solver failed completely for unknown ratios above 60%, while the conventional ONN solver dropped to ~80% accuracy at 50% unknowns.
$9 \times 9$ Puzzles: The proposed solver demonstrated superior performance compared to the other methods. It achieved perfect accuracy for unknown ratios up to 25% and maintained over 80% accuracy at 37.5% unknowns. However, performance degraded as the number of unknowns increased, dropping to ~50% at 50% unknowns and failing to solve puzzles correctly for unknown ratios greater than 70%.
Order Parameters: There was a strong correlation between accuracy and the order parameter. High accuracy corresponded to order parameters near 1 (convergence to ideal phases), while lower accuracy correlated with lower order parameters, suggesting the system failed to settle into a valid stable state.

Significance and Claims
The paper claims that the proposed approach significantly outperforms existing HNN and ONN Sudoku solvers in terms of accuracy, particularly for smaller grids ( $4 \times 4$ ) and moderately constrained $9 \times 9$ grids. The authors attribute this success to the additional term in the ODE, which effectively eliminates invalid stable states that satisfy the energy minimization but violate Sudoku rules.

The authors modestly acknowledge limitations, noting that the model relies on four tunable parameters, making the parameter sweep costly. They suggest that for larger unknown ratios in $9 \times 9$ puzzles, the additional term may not be scaled strongly enough, or the system may require more oscillatory cycles to stabilize. The paper concludes that expanding ODEs with constraint-enforcing terms is a relevant strategy for solving COPs with ONNs and suggests future work should explore highly nonlinear oscillators and alternative formulations for the constraint-enforcement function.