用振荡神经网络解数独，准确率显著提升。
Graph Coloring Approach to Solving Sudoku with Oscillatory Neural Networks
- 将数独转为图着色问题，用改进的振荡神经网络求解。
- 4×4数独接近完美准确率，9×9数独在多种空白数下表现优异。
- 相比传统方法更高效，适合解决约束优化类问题。
振荡神经网络（ONNs）是一种基于物理的计算范式，通过全连接振荡器网络动态最小化能量函数。本文提出一种基于ONN的数独求解器，将数独问题转化为图着色问题。通过改进现有图着色求解器并引入额外项以满足数独约束，该方法在准确率上显著优于现有的HNN和ONN求解器。尤其在4×4数独上达到近乎完美的准确率，在9×9数独上对不同数量未知数字也表现出较高的求解精度。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。