基于振荡神经网络的数独求解图着色方法

# 基于图着色方法的振荡神经网络数独求解器††感谢：本研究得到了欧盟地平线欧洲研究与创新计划下PHASTRAC项目（资助协议号101092096）以及欧洲研究委员会ERC THERMODON项目（资助协议号101125031）的资助。
来源：https://arxiv.org/html/2607.15814

###### 摘要

振荡神经网络（ONNs）提供了一种有吸引力的基于物理的计算范式，其根源在于一个通常全耦合的振荡器网络的动态，旨在最小化一个底层能量函数。在本文中，我们提出了一种基于ONN的求解器，用于解决一个众所周知的约束组合优化问题，即数独，通过将该问题表述为一个图着色问题。通过将已有的图着色求解器修改为计算成本更低的版本，并引入一个确保满足数独约束的附加项，我们的求解器在准确性上显著优于现有的HNN和ONN求解器。特别是，我们能够在4×4数独谜题上实现近乎完美的准确率，并在不同未知数字数量的9×9数独谜题上获得相当高的准确率。

## I 引言

约束组合优化问题（COPs）在工业中无处不在，从调度到芯片设计再到金融领域[44 (https://arxiv.org/html/2607.15814#bib.bib30),46 (https://arxiv.org/html/2607.15814#bib.bib27),7 (https://arxiv.org/html/2607.15814#bib.bib28),3 (https://arxiv.org/html/2607.15814#bib.bib29)]。特别是，NP-hard问题构成了一类特殊的COPs，随着问题规模的增大，求解时间呈指数增长[18 (https://arxiv.org/html/2607.15814#bib.bib1)]。此外，当前的计算范式不适合处理此类问题，因为它受到存算瓶颈的影响，导致高功耗[42 (https://arxiv.org/html/2607.15814#bib.bib35),6 (https://arxiv.org/html/2607.15814#bib.bib36),39 (https://arxiv.org/html/2607.15814#bib.bib37)]。在这方面，最近出现了对替代计算范式的推动。在本文中，我们研究了一种基于耦合振荡器网络的物理计算范式的性能，称为振荡神经网络（ONNs）[38 (https://arxiv.org/html/2607.15814#bib.bib7)]。

与传统人工神经网络[32 (https://arxiv.org/html/2607.15814#bib.bib38),45 (https://arxiv.org/html/2607.15814#bib.bib40),47 (https://arxiv.org/html/2607.15814#bib.bib39)]不同，振荡神经网络提供了一种新兴的基于物理的计算范式，其根源在于一个通常全耦合的振荡器网络的动态，旨在最小化一个底层能量函数[16 (https://arxiv.org/html/2607.15814#bib.bib18),43 (https://arxiv.org/html/2607.15814#bib.bib5),38 (https://arxiv.org/html/2607.15814#bib.bib7)]。在这种网络中，信息被编码在振荡器的相位中。由于与Hopfield神经网络[13 (https://arxiv.org/html/2607.15814#bib.bib42),30 (https://arxiv.org/html/2607.15814#bib.bib43)]和Ising模型[15 (https://arxiv.org/html/2607.15814#bib.bib41),21 (https://arxiv.org/html/2607.15814#bib.bib2)]紧密相连，ONNs非常适合自动联想记忆任务[14 (https://arxiv.org/html/2607.15814#bib.bib4),11 (https://arxiv.org/html/2607.15814#bib.bib44),1 (https://arxiv.org/html/2607.15814#bib.bib45),22 (https://arxiv.org/html/2607.15814#bib.bib46),10 (https://arxiv.org/html/2607.15814#bib.bib47),34 (https://arxiv.org/html/2607.15814#bib.bib48),2 (https://arxiv.org/html/2607.15814#bib.bib49),31 (https://arxiv.org/html/2607.15814#bib.bib50),26 (https://arxiv.org/html/2607.15814#bib.bib51)]和组合优化问题[43 (https://arxiv.org/html/2607.15814#bib.bib5),12 (https://arxiv.org/html/2607.15814#bib.bib11),37 (https://arxiv.org/html/2607.15814#bib.bib52),9 (https://arxiv.org/html/2607.15814#bib.bib53),40 (https://arxiv.org/html/2607.15814#bib.bib54),4 (https://arxiv.org/html/2607.15814#bib.bib22),23 (https://arxiv.org/html/2607.15814#bib.bib25),17 (https://arxiv.org/html/2607.15814#bib.bib55),24 (https://arxiv.org/html/2607.15814#bib.bib3)]。在本文中，我们提出了一种基于ONN的求解器，用于一个众所周知的约束组合优化问题，即数独。

数独体现了著名的数字填充谜题。具体来说，给定一个大小为N×N的网格和一些已知数字，目标在于用范围[1,N]内的整数填充网格中剩余的空白单元格，使得网格的任何行、列或宫格中都没有数字重复。因此，数独可以被视为一个约束组合优化问题。特别是，图着色问题，即为图中的每个节点分配一种“颜色”，使得使用最少的颜色数量，并且没有两个相邻节点共享相同的颜色，非常适合数独。在本文中，我们基于图着色问题构建了一个针对数独约束量身定制的ONN求解器。

最近，文献[12 (https://arxiv.org/html/2607.15814#bib.bib11)]的作者开发了一种基于ONN的数独求解器，通过将给定的数独约束嵌入到权重矩阵中。他们的方法已被证明在4×4、9×9以及16×16谜题的准确性上优于现有的基于HNN的数独求解器[27 (https://arxiv.org/html/2607.15814#bib.bib10)]。相比之下，在本文中，我们提出了一种基于图着色的替代ONN数独求解器，并添加了一个确保满足约束的附加项。我们的模型在4×4和9×9数独谜题上的准确性显著优于现有的HNN和ONN求解器，在4×4数独上达到几乎完美的准确率，在9×9数独上针对不同未知数字数量实现了普遍较高的准确率。

本文结构如下。在第二节中，我们介绍基于物理的振荡神经网络（ONNs）计算的关键概念。此外，第三节概述了我们提出的基于图着色的ONN数独求解器以及基准测试设置。最重要的是，我们在第四节中展示了在4×4和9×9数独上针对已有HNN和ONN数独求解器的准确性基准测试。最后但同样重要的是，结果在第五节中讨论，本文在第六节中总结。

## II 背景

### II-A Ising模型

本文围绕振荡神经网络（ONNs）展开，这是一种新兴的基于物理的范式，根植于耦合振荡器的动态[38 (https://arxiv.org/html/2607.15814#bib.bib7)]。与人工神经网络[32 (https://arxiv.org/html/2607.15814#bib.bib38),45 (https://arxiv.org/html/2607.15814#bib.bib40),47 (https://arxiv.org/html/2607.15814#bib.bib39)]不同，ONN计算归结为在底层能量函数中寻找全局最小值[16 (https://arxiv.org/html/2607.15814#bib.bib18),43 (https://arxiv.org/html/2607.15814#bib.bib5),38 (https://arxiv.org/html/2607.15814#bib.bib7)]。ONN与Ising模型[15 (https://arxiv.org/html/2607.15814#bib.bib41),21 (https://arxiv.org/html/2607.15814#bib.bib2)]（一种描述系统自旋构型的铁磁性数学模型[15 (https://arxiv.org/html/2607.15814#bib.bib41)]）有内在联系。特别是，模型的动态可以用以下哈密顿量描述：

H = - ∑_{(i,j)} J_{ij} σ_i σ_j. (1)
给定一个耦合权重矩阵J_{ij}，目标是通过二进制自旋σ_i集的最小化上述哈密顿量来识别系统的自然状态。

### II-B 振荡神经网络（ONNs）

可以通过将自旋σ_i ∈ {1,-1} 映射到振荡器的相位φ_i ∈ {0,π} 来弥合Ising模型与ONN之间的差距，从而得到相应的ONN哈密顿量。此外，描述ONN中N个振荡器动态的常微分方程（ODE）可以通过遵循ONN哈密顿量的负梯度简单地确定[14 (https://arxiv.org/html/2607.15814#bib.bib4),43 (https://arxiv.org/html/2607.15814#bib.bib5)]：

φ_i ̇ = (1/N) ∑_j W_{ij} sin((φ_j - φ_i)), (2)
其中W_{ij}代表第i个和第j个振荡器之间的耦合。公式2中的ODE通常被称为Kuramoto模型[20 (https://arxiv.org/html/2607.15814#bib.bib6)]。如前所述，相位(0,π)编码布尔值(1,-1)。然而，当运行ONN时，相位很少在预设的二进制值0和π处稳定，而往往在连续值处稳定。因此，为了迫使振荡器进入二进制相位，我们引入一个由因子K_S缩放的附加项进入ODE，称为**次谐波注入锁定**（SHIL），它将二次谐波注入振荡器[38 (https://arxiv.org/html/2607.15814#bib.bib7),5 (https://arxiv.org/html/2607.15814#bib.bib8),43 (https://arxiv.org/html/2607.15814#bib.bib5)]：

φ_i ̇ = (1/N) ∑_j W_{ij} sin((φ_j - φ_i)) - K_S sin((2φ_i)). (3)

## III 方法

在本节中，我们介绍使用振荡神经网络解决数独谜题的方法。由于数独规则要求所有列、行和宫格中的数字不重复，图着色为求解该问题提供了一种合适的方法。在本节末尾，我们概述了基准测试过程。

### III-A 提出的ONN数独求解器

#### III-A1 基于ONN的图着色

给定一个图，图着色问题的目标归结为给图中的每个节点分配一种颜色，使得没有两个相邻节点共享相同的颜色，并且使用最少的颜色数量。作为21个Karp NP完全问题之一[18 (https://arxiv.org/html/2607.15814#bib.bib1)]，图着色是一个众所周知的困难组合优化问题。如作者在[21 (https://arxiv.org/html/2607.15814#bib.bib2)]中所示，所有NP难问题都可以映射到相应的Ising哈密顿量，图着色也不例外。

此外，文献[24 (https://arxiv.org/html/2607.15814#bib.bib3)]的作者展示了将一些非二进制困难优化问题映射到振荡伊辛机（“振荡神经网络”）的方法。特别是，图着色被定义为Max-K-Cut，其中最小的K使得没有两个相邻节点共享相同的集合。在数独的情况下，集合数或K是已知的，不需要最小化，因为它对应于数独的大小。因此，大小为K的数独的理想相位φ_ideal如下：

φ_ideal = {2π(k-1)/K | k ∈ {1,2,...,K}}. (4)
因此，对于9×9数独（K=9），我们得到数字到相位的以下映射：

1 → 0
2 → 2π/9
3 → 4π/9
4 → 2π/3
5 → 8π/9
6 → 10π/9
7 → 4π/3
8 → 14π/9
9 → 16π/9
(5)

现在让我们把注意力转向Max-K-Cut。给定一个图，Max-Cut问题涉及将节点划分为2个集合，使得切割边的总和最大化。在Max-K-Cut的情况下，需要找到划分为K个集合且切割边总和最大的划分。文献[24 (https://arxiv.org/html/2607.15814#bib.bib3)]的作者通过将公式(3)中的ODE扩展为以下形式，使用振荡神经网络求解Max-K-Cut：

φ_i ̇ = - (1/N) ∑_j W_{ij} sin((φ_i - φ_j + f(φ_i - φ_j))) - K_S sin((K φ_i)), (6)
其中f(Δφ_ij)确保来自公式(4)的理想相位在作用于正弦函数时产生消失的梯度。此外，函数f如下：

f(Δφ_ij) = ∑_{k=1}^{K-1} ((2k-1)π - (2kπ)/K) ( exp(-(Δφ_ij - (2kπ)/K)^2 / (2σ^2)) - exp(-(Δφ_ij + (2kπ)/K)^2 / (2σ^2)) ), (7)
其中σ是一个可调参数。图1展示了公式(7)中的函数f(Δφ_ij)以及项sin((Δφ_ij + f(Δφ_ij)))在K=4且σ相对较大(=0.15)时的图形，以显示函数的形式。

参见图注
图1：公式(7)中的函数f(Δφ_ij)（左）和项sin((Δφ_ij + f(Δφ_ij)))（右），K=4。

显然，使用公式(6)中的模型有多个缺点。首先，公式(7)中的函数有一个可调参数σ，它控制峰值的宽度。其次，计算公式(7)中的项在计算上是昂贵的，特别是当对数千个时间步和大型问题执行时。然而最重要的是，达到项sin((Δφ_ij + f(Δφ_ij)))的根的过程并不相同，因为梯度可能会根据所选路径而有显著变化。这可能导致某些根被优先选择，或者反过来被完全避免。因此，我们需要一个易于计算的模型，没有可调参数，并且每个根都是相同的。所有这些条件都通过以下模型得到满足：

φ_i ̇ = - (1/N) ∑_j W_{ij} sin( (K/2)(φ_i - φ_j) ) - K_S sin((K φ_i)). (8)
特别地，第一项确保振荡器相隔2πn/K，而第二项保证振荡器稳定在2πn/K值。我们在数独方法中使用公式(8)而不是公式(6)。