Graph Coloring Approach to Solving Sudoku with Oscillatory Neural Networks

• URL: http://arxiv.org/abs/2607.15814v1
• Date: Fri, 17 Jul 2026 10:24:18 GMT
• Title: Graph Coloring Approach to Solving Sudoku with Oscillatory Neural Networks
• Abstract summary: We propose an ONN-based solver for one well-known constrained optimization problem, namely a Sudoku, by formulating the problem as a Graph Coloring problem.<n>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.
• Score: 1.2315012216991832
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  This paper studies how to introduce the popular positive linear satisfiability to neural networks. We propose the first differentiable satisfiability layer based on an extension of the classic Sinkhorn algorithm for jointly encoding multiple sets of marginal distributions.
  arXiv  Detail & Related papers  (2024-07-18T22:05:21Z)
• Bridging Logic and Learning: A Neural-Symbolic Approach for Enhanced Reasoning in Neural Models (ASPER) [0.13053649021965597]
  This paper introduces an approach designed to improve the performance of neural models in learning reasoning tasks. It achieves this by integrating Answer Set Programming solvers and domain-specific expertise. The model shows a significant improvement in solving Sudoku puzzles using only 12 puzzles for training and testing.
  arXiv  Detail & Related papers  (2023-12-18T19:06:00Z)
• Degree-based stratification of nodes in Graph Neural Networks [66.17149106033126]
  We modify the Graph Neural Network (GNN) architecture so that the weight matrices are learned, separately, for the nodes in each group. This simple-to-implement modification seems to improve performance across datasets and GNN methods.
  arXiv  Detail & Related papers  (2023-12-16T14:09:23Z)
• Graph Neural Network Bandits [89.31889875864599]
  We consider the bandit optimization problem with the reward function defined over graph-structured data. Key challenges in this setting are scaling to large domains, and to graphs with many nodes. We show that graph neural networks (GNNs) can be used to estimate the reward function.
  arXiv  Detail & Related papers  (2022-07-13T18:12:36Z)
• Cracking nuts with a sledgehammer: when modern graph neural networks do worse than classical greedy algorithms [2.436681150766912]
  We show that a simple greedy algorithm, running in almost linear time, can find solutions for the MIS problem of much better quality than the GNN. We do not see any good reason for solving the MIS with these GNN, as well as for using a sledgehammer to crack nuts.
  arXiv  Detail & Related papers  (2022-06-27T11:54:01Z)
• Graph Neural Networks for Propositional Model Counting [1.0152838128195467]
  Graph Networks (GNNs) have been recently leveraged to solve logical reasoning tasks. We present an architecture based on the GNN framework for belief propagation (BP) of Kuch et al., extended with self-attentive GNN and trained to approximately solve the #SAT problem.
  arXiv  Detail & Related papers  (2022-05-09T17:03:13Z)
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks [0.0]
  We show how graph neural networks can be used to solve optimization problems. We find that the neural network performs on par or outperforms existing solvers.
  arXiv  Detail & Related papers  (2021-07-02T16:54:35Z)
• Very Deep Graph Neural Networks Via Noise Regularisation [57.450532911995516]
  Graph Neural Networks (GNNs) perform learned message passing over an input graph. We train a deep GNN with up to 100 message passing steps and achieve several state-of-the-art results.
  arXiv  Detail & Related papers  (2021-06-15T08:50:10Z)
• Increase and Conquer: Training Graph Neural Networks on Growing Graphs [116.03137405192356]
  We consider the problem of learning a graphon neural network (WNN) by training GNNs on graphs sampled Bernoulli from the graphon. Inspired by these results, we propose an algorithm to learn GNNs on large-scale graphs that, starting from a moderate number of nodes, successively increases the size of the graph during training.
  arXiv  Detail & Related papers  (2021-06-07T15:05:59Z)
• dNNsolve: an efficient NN-based PDE solver [62.997667081978825]
  We introduce dNNsolve, that makes use of dual Neural Networks to solve ODEs/PDEs. We show that dNNsolve is capable of solving a broad range of ODEs/PDEs in 1, 2 and 3 spacetime dimensions.
  arXiv  Detail & Related papers  (2021-03-15T19:14:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.