四色定理

Question

我一直在尝试编写一个代码，将使用四色定理对邻接矩阵定义的区域进行着色。邻接矩阵如下所示：

    A B C D

A   0 1 0 1
B   1 0 1 0
C   0 1 0 1
D   1 0 1 0

因此对于这个例子A本身或C不相邻，但它与B和D相邻。

我正在编写的程序必须使用递归和回溯来为定义的区域指定4种颜色（或更少）。

到目前为止我的算法如下：

global int[] colors = <region one color,region two, region three, region four >
public static int color(row,column)
  if out of bounds ??
    loop(!colored)
    {
      case 1: are any adjacent regions this color? assign
      case 2: are any adjacent regions this color? assign.
      case 3: are any adjacent regions this color? assign.
      case 4: are any adjacent regions this color? assign.
      case 5: if nothing found, steal closest (in #) region's color and call method from there
  }

但我有几个问题：

1. 这个方法会返回什么？
2. 这是否可行，是否应该有递归/回溯？
3. 如果给定的行/列超出边界，我将输出什么？

谢谢你！

Answer 1

您的伪代码看起来更像本地搜索，而不是递归/回溯。逻辑返回将是空，因为本地搜索不能证明没有解决方案，所以失败是通过永远运行来表示的。（如果找到着色本身，则通过全局变量返回。）

递归/回溯更像这样。

boolean extend-coloring(partial-coloring):
    if every vertex has a color, then return true
    let v be a vertex without a color
    for each color c,
        if v has no neighbors of color c,
            apply color c to v in partial-coloring
            if extend-coloring(partial-coloring), then return true
            remove color c from v
    return false

根调用是extend coloring（empty coloring），其中empty coloring不为顶点指定颜色。返回值指示扩展部分着色的尝试是否成功。