Graph Coloring Approach to Solving Sudoku with Oscillatory Neural Networks

想象一个这样的世界：计算机不再仅仅是像超级快速的计算器那样进行数字运算，而是随着节奏起舞。这就是振荡神经网络（ONNs）的领域，一种“基于物理学”的计算方式。这些网络不使用标准的电子开关，而是使用被称为振荡器的微小振动单元。你可以把它们想象成一间装满了节拍器的房间，或者一个合唱团。在这个系统中，信息不是以简单的“开”或“关”比特形式存储的，而是存储在振动的相位（即时间节奏）中。如果两个振荡器以完美的同步方式振动，它们就是“同相”的；如果它们的振动时间相反，则为“反相”。

这些网络的目标是寻找一种完美的和谐状态，或者说能量最低的状态，即所有的振荡器都稳定在一个模式中。这种方法特别擅长解决组合优化问题——这类问题需要你按照特定规则排列许多碎片，且不能产生冲突。你可能听说过**图着色（Graph Coloring）**问题，这就像是尝试为一个地图涂色，使得相邻的国家不能共享同一种颜色。如果你能让一个振荡器网络自然地稳定在一个模式中，使得没有“邻居”在同一时间进行相同的振动，你就利用物理定律解决了一个复杂的谜题。这之所以重要，是因为传统计算机在处理这类谜题时往往非常吃力，会消耗大量的电力和时间，而这些起舞的振荡器可能提供一种更快、更节能的思考方式。

---

伟大的数独舞会

现在，让我们来聊聊数独。你了解它的规则：一个数字网格，你必须填补空白，使得每一行、每一列以及每一个小方格都包含从1到9（或从1到4的小型版本）的数字且不重复。这是一个经典的逻辑谜题，但对于计算机来说，它是一个巨大的头痛问题，充满了试错过程。

来自埃因霍芬理工大学的 Filip Sabo 和 Aida Todri-Sanial 的研究人员决定利用他们的“跳舞振荡器”网络来解决数独问题。他们将数独网格视为一个图着色问题。想象一下，数独网格中的每个空格都是一名舞者。规则很简单：同一行、同一列或同一个方格内的两名舞者不能穿着相同的“颜色”（在这种情况下，颜色代表特定的数字，如1、2或3）。

在振荡器的世界里，“穿着颜色”意味着以特定的节奏进行振动。对于一个9x9的数独，有9种可能的节奏（相位）供振荡器选择。网络的任务是让所有舞者选择一种节奏，使得没有任何两个邻居在做相同的舞蹈动作。

旧舞步的问题

作者研究了其他科学家此前尝试解决此问题的方法。其中一种方法涉及一个非常复杂的数学公式，其计算成本极高，就像试图通过预先计算每一个肌肉动作来编排一场舞蹈一样。另一种方法使用了更简单的方法，但它有一个致命缺陷：它允许舞者“作弊”。

想象这样一个场景：同一行中的两名舞者都决定跳“数字1”的舞蹈。在旧的、更简单的模型中，网络可能会认为：“嘿，他们都在跳‘数字1’的节奏，这是一个有效的节奏，所以没问题！”但在数独中，这简直是一场灾难。规则规定同一行不能有两个1。旧的模型没有办法在舞者意外同步了错误的数字时，将他们踢出这种错误状态。

新的“踢”项

为了修复这个问题，作者发明了一种更简单的让振荡器起舞的方法，并添加了一个特殊的“踢”（kick）机制。

1. 更简单的节奏： 他们没有使用那种复杂、昂贵的数学公式，而是使用了一个更简洁、更直接的方程。这使得计算机模拟运行得更快、成本更低。
2. “踢”（秘诀）： 这是最重要的部分。他们在方程中添加了一个特殊的项，充当裁判的角色。如果同一行、同一列或同一方格内的两名舞者意外地开始以完全相同的频率振动（意味着他们选择了相同的数字），这个裁判就会给他们一个猛烈的“踢”。它把他们从那个稳定、舒适的状态中踢出来，迫使他们尝试不同的节奏。

这个“踢”确保了网络只有在谜题被正确解决时才会稳定下来。这就像一位老师在教室里巡视：如果两个学生正在窃窃私语同一个错误的答案，老师会拍拍他们的肩膀，让他们停下来重新思考。

结果：完美的表演

团队将他们这个全新的“带踢”振荡器求解器测试了数千个数独谜题，范围涵盖了从4x4的小型网格到标准的9x9网格。他们将结果与另外两个著名的求解器进行了对比：一个是基于 Hopfield 神经网络（HNN）的，另一个是标准的振荡神经网络。

以下是他们的发现：

• 对于4x4谜题： 他们的新求解器表现近乎完美。无论缺失多少数字，它几乎能正确解决100%的谜题。而其他求解器则表现挣扎，随着谜题变得更难（缺失数字更多），准确率大幅下降。
• 对于9x9谜题： 结果依然令人印象深刻，虽然并非完美。当谜题缺失数字较少（缺失比例在25%以内）时，他们的求解器是无懈可击的。即使在谜题变难（缺失比例达到37.5%）时，它仍能解决超过80%的谜题。然而，当谜题变得非常困难（缺失数字超过50%）时，求解器开始出错，正确率降至约50%。其他求解器则更早失败，一旦缺失数字超过40-50%，通常就无法正确解决任何谜题。

研究人员还观察了一个“序参数”（order parameter），这基本上是一个得分，衡量了振荡器成功稳定到最终正确节奏的程度。他们发现，每当求解器解对谜题时，振荡器都非常有组织性（高序参数）。当解错时，振荡器则是混乱的，无法达成稳定的模式。

未来展望

作者非常肯定他们的“踢”项是成功的关键，但也承认仍有工作要做。他们的模型有一些需要手动调节的“旋钮”（可调参数），确定这些参数需要耗费大量时间。他们还注意到，对于最难的9x9谜题，振荡器有时需要更长的时间来“跳舞”并稳定下来，或者也许是“踢”的力量还不够强。

他们建议，未来的版本可以尝试使用更复杂的、“非线性”的振荡器（拥有更复杂动作的舞者），或者进一步微调“踢”函数，使其能更有效地捕捉违规者。但就目前而言，他们已经证明了，通过在这些跳舞网络的物理特性中加入一个简单而巧妙的规则，我们可以比以前更好地解决数独谜题。这虽然只是小小的一步，但它证明了有时，要修复一个破碎的系统，你只需要一个正确的推力。