Graph Coloring Approach to Solving Sudoku with Oscillatory Neural Networks
Machine Learning
Summary
The authors developed a new way to solve Sudoku puzzles using a special kind of neural network called an Oscillatory Neural Network (ONN). They turned Sudoku into a graph coloring problem and improved an existing solver to make it faster and more accurate. Their method adds extra rules to make sure Sudoku’s unique constraints are met. Tests show their approach works very well on small (4x4) and fairly well on standard (9x9) Sudoku puzzles, beating previous similar methods.
Authors
Filip Sabo, Aida Todri-Sanial
Abstract
Oscillatory Neural Networks (ONNs) present an attractive physics-based computing paradigm rooted in the dynamics of a network of typically fully coupled oscillators aiming to minimize an underlying energy function. In this paper, we propose an ONN-based solver for one well-known constrained combinatorial optimization problem, namely a Sudoku, by formulating the problem as a Graph Coloring problem. By modifying the already existing Graph Coloring solver to a computationally cheaper version and introducing an additional term ensuring the fulfillment of the Sudoku constraints, our solver is shown to significantly outperform the existing HNN- and ONN solvers in terms of accuracy. In particular, we are able to achieve nearly flawless accuracies on $4 \times 4$ as well as rather high accuracies on $9 \times 9$ Sudoku puzzles for different numbers of unknown digits.