使用图着色解决数独问题

下载 SudokuSolver.zip

引言

在本文中，我将解释图着色的概念以及如何使用它来解决一个 9x9 的数独谜题。本文假设读者已经熟悉图及其表示的概念。

图着色揭秘

图是对一组对象的一种数学表示，其中一些对象对（链接）彼此连接。对象由顶点（节点）表示，链接称为边。

 

一个有 5 个节点和 5 条边的图

图着色是指为图的顶点分配“颜色”，使得任意两个相邻的顶点不能共享相同的颜色。例如，在上面提到的图中，顶点 1 和 2 不能具有相同的颜色，因为它们之间有一条边连接。但是，顶点 2 和 3 可以具有相同的颜色，因为它们不相连。以下是该图的一种可能的着色方案。

现在应该很清楚，一个图可以有不止一种可能的着色方案。目标是使用最少数量的颜色。下面是该示例图的另外两种可能的着色方案。着色 (1) 使用了 3 种颜色，而着色 (2) 使用了 5 种颜色，因此，着色 (1) 比着色 (2) 更好。

我们的目标是找到一个给定图的着色方案，该方案使用的颜色数量最少。使用最多 k 种颜色的着色称为k-着色（例如，上面示例中的着色 (1) 是 3-着色，而着色 (2) 是 5-着色）。

如果您尝试仅使用两种颜色为上面的图着色，您会发现它根本无法着色，快去试试吧，我等着 :)。因此，给图着色所需的颜色数量最少称为其色数。

收缩和贪心着色算法

图着色在计算上是困难的，并且多年来一直是研究课题。大多数算法可以广泛地分为两个主要主题：“收缩”和“贪心着色”。

贪心着色侧重于仔细选择下一个要着色的顶点。一旦顶点被着色，其颜色将永不改变。此类别中的算法在选择下一个顶点的方式上有所不同。

该类别中一个著名的算法是 Welsh–Powell 算法。其工作原理如下

1. Find the degree of each vertex. (Degree: is the number of edges connected to it)

2. Order the vertices in descending order according to their degree.

3. Go through the list, color each vertex not connected to colored vertices with the same color.

4. Remove colored vertices from the list and repeat the process until all vertices are colored.

让我们回到我们的例子。

步骤 1

顶点	度
1	3
2	1
3	2
4	1
5	3

步骤 2：顺序是1,5,3,2,4

步骤 3

顶点		操作
1		着色为红色
5		不要着色为红色，因为它连接到 1
3		不要着色为红色，因为它连接到 1
2		不要着色为红色，因为它连接到 1
4		着色为红色

现在图看起来像这样，新列表是 5,3,2

顶点		操作
5		着色为蓝色
3		不要着色为蓝色，因为它连接到 5
2		着色为 蓝色

 

现在图看起来像这样，我们还剩一个顶点，它将被着色为绿色。

第二个类别“收缩”通过找到两个顶点，删除它们之间的所有边，然后用一个新顶点替换它们来工作，任何连接到其中任何一个顶点的边现在都将重定向到新的单个顶点。收缩算法的工作原理如下

1. Select the vertex of maximum degree V.

2. Find the set of non-adjacent vertices to V.

3. From this set select the vertex Y of maximum common vertices with V.

4. Contract Y into V to be colored with the same color.

5. Remove Y from the set and repeat steps 3-5 until the list is empty.

6 .Remove vertex V from the graph

7. Repeat steps 1-6 until the resulting graph has all contracted nodes adjacent to each other.

让我们回到我们的例子。顶点 (1) 的度最大；其非相邻顶点是顶点 (4)。因此，将顶点 (1) 和 (4) 收缩为一个节点。

 

现在，度最大的顶点是 ({1,4})，它和所有剩余的顶点都是相邻的。因此，从图中移除顶点 ({1,4}) 并选择度最大的顶点。

 

 

现在，顶点 (3) 的度最大，并且有一个非相邻顶点 (2)。将顶点 (3) 和 (2) 收缩为单个顶点。

顶点 ({3,2}) 没有非相邻顶点，因此，它将从图中移除。我们还剩一个顶点 (5)；我们的工作完成了。该算法产生三个组 {1,4}、{2,3} 和 {5}，每个组将采用不同的颜色。

实现算法

在我的实现中，我选择了一种贪心着色算法，并根据 Dr. Hussein Al-Omari 和 Khair Eddin Sabri 在《美国数学与统计学杂志》上发表的文章中的提议进行了一些修改。

正如我之前讨论过的，技巧在于选择下一个要着色的顶点。所提出的算法使用了饱和度排序 (SDO) 和我们之前解释过的度排序的组合。

顶点的饱和度是指与其相邻的不同颜色的顶点的数量。顶点根据其饱和度进行排序，如果两个顶点具有相同的度，则通过比较它们的度来打破平局。

int colorNumber = 1; //number of used colors
int numberOfColoredNodes = 0;

while (numberOfColoredNodes < graph.Count)
{
 var max = -1;
 var index = -1;

 for (int i = 0; i < graph.Count; i++)
 {
  if (!Colored(graph.Nodes[i], nodeSet))
  {
   var d = SaturatedDegree(graph.Nodes[i], nodeSet);
   if (d > max)
   {
    max = d;
    index = i;
   }
   else if (d == max)
   {
    if (Degree(graph.Nodes[i]) > Degree(graph.Nodes[index]))
    {
     index = i;
    }
   }
  }
 }
 AssignColor(graph.Nodes[index], nodeSet,ref colorNumber);
 numberOfColoredNodes++;
}

数独求解器

一个数独谜题（9x9）可以被看作是一个有 81 个顶点的图，每个单元格一个顶点，如果两个顶点不能被赋予相同的值，则它们之间就有一条边。例如，同一行、同一列或同一宫格的所有单元格的相应顶点之间都将有边。

给定一个数独谜题，我们可以构建相关的图。谜题中的给定数字可用于向图中添加额外的边，然后我们可以使用图着色来找到该图的 9-着色（颜色 1-9）

关注点

数独谜题最优解是找到一个仅使用 9 种颜色的着色方案。一些算法比其他算法表现更好，这通常是在运行时复杂度和使用的颜色数量之间的权衡。目前并非所有谜题都能解决；对于某些谜题，该算法找不到仅使用九种颜色的着色方案。下面给出了一个无法解决的谜题示例。

希望您喜欢这篇博文，如果您有任何问题，请留言。