四色问题的解决方法

四色问题穷举

def fourColors(areas, colors, close_areas, currentArea=1, result=list(), results=list()):
    """
    四色问题暴力解决，枚举出所有可行的填色方案。需要传入总区域数和取色序列以及每个区域所邻接区域的字典。
    :param areas: 总区域数
    :param colors: 取色序列
    :param close_areas: 所有区域所邻接区域的字典
    :param currentArea: 当前填色区域
    :param result: 填色结果列表
    :param results: 填色结果总列表
    :return: 填色结果总列表
    """
    closeColors = set()                                                 # 当前区域所邻接区域所有填色的集合
    for area in close_areas[currentArea]:                               # 遍历当前区域所邻接区域
        if area < currentArea:                                          # 当临界区域标号小于当前区域标号(防止超出result下标索引)
            closeColors.add(result[area - 1])                           # 从result中得到临界区域所填色添加进邻接区域填色集合
    for color in colors:                                                # 遍历取色序列
        if color not in closeColors:                                    # 若当前取色未在邻接区域所有填色集合中
            result.append(color)                                        # 将其添加进填色结果列表
            if len(result) < areas:                                     # 若填色结果列表已填色区域数小于总区域数
                fourColors(areas, colors, close_areas, currentArea + 1, result, results)    # 递归调用,当前填色区域号+1
            elif len(result) == areas:                                  # 若填色结果列表已填色区域数等于总区域数
                results.append(result)                                  # 填色结果添加进填色结果总列表
                print(result)                                           # 输出填色结果
            result.pop()                                                # 删去填色结果列表最后所填色,对当前区域进行下一次取色判断
    return results


print("区域请以数字标号".center(50, "!"))
Areas = eval(input("请输入总区域数:"))
Colors = tuple(input("请输入所有取色(以英文逗号隔开):").split(","))
Close_areas = {}
for Area in range(1, Areas + 1):
    Close_areas[Area] = eval((input(f"请输入区域 {Area} 所邻接的区域(以英文逗号隔开):")))
position = list()
for i in range(1, Areas + 1):
    position.append(str(i))
print(position, "\t<序号标记>\n")
print(f"共有{len(fourColors(Areas, Colors, Close_areas))}种填色方法!")

四色问题回溯法解决

无向图如下：

区域图如下：

import numpy as np
color = 4                          # 颜色种类
line = 0                           # 从矩阵第零行开始着色
knot = 5                           # 顶点个数
color_list = np.zeros([1, 5])      # 每次染色的颜色顺序
sum = 0                            # 染色总数


def panduancolor(arr, line , color_list):
    '''
    :param arr:              输入邻接矩阵
    :param line:             输入根结点，即从邻接矩阵第一行开始
    :param color_list:       填充颜色的顺序
    :return:                 返回True or False
    '''
    for i in range(5):                                                     # 遍历所有的点一遍
        if arr[line][i] != 0 and color_list[0][i] == color_list[0][line]:  # 判断邻接矩阵中那个点颜色是否与相邻的区块颜色相同
            return False                                                   # 与邻接区块有相同颜色则返回False
    return True                                                            # 没有相同颜色则返回True


def caculatecolornum(arr, line, knot, color_list1):
    '''
    :param arr:             输入邻接矩阵
    :param line:            输入根结点，即从邻接矩阵第一行开始
    :param knot:            输入总节点数
    :param color_list1:     添加颜色的顺序
    :return:                返回添加完颜色后的颜色列表
    '''
    global sum
    if line < knot:                                    # 递归结束条件， 当邻接矩阵所有行都遍历完， 则递归结束
        for i in range(1, color + 1):                  # 遍历所有的颜色一遍
            color_list1[0][line] = i                   # 第一个点赋值一种颜色后，利用递归搜索树，找出其余点可能被赋予颜色的情况
            if panduancolor(arr, line, color_list1):   # 判断所赋值的颜色是否合法
                caculatecolornum(arr, line + 1, knot, color_list1)
            color_list1[0][line] = 0                   # 恢复现场，即返回上一个节点，使上一个节点的颜色为空
    else:
        print(color_list[0])
        sum += 1


group_arr = [[0, 1, 0, 0, 1],
             [1, 0, 1, 0, 1],
             [0, 1, 0, 1, 1],
             [0, 0, 1, 0, 1],
             [1, 1, 1, 1, 0]]

caculatecolornum(group_arr, 0, knot, color_list)

结果如下：

[1. 2. 1. 2. 3.]
[1. 2. 1. 2. 4.]
[1. 2. 1. 3. 4.]
[1. 2. 1. 4. 3.]
[1. 2. 3. 1. 4.]
[1. 2. 3. 2. 4.]
[1. 2. 4. 1. 3.]
[1. 2. 4. 2. 3.]
[1. 3. 1. 2. 4.]
[1. 3. 1. 3. 2.]
[1. 3. 1. 3. 4.]
[1. 3. 1. 4. 2.]
[1. 3. 2. 1. 4.]
[1. 3. 2. 3. 4.]
[1. 3. 4. 1. 2.]
[1. 3. 4. 3. 2.]
[1. 4. 1. 2. 3.]
[1. 4. 1. 3. 2.]
[1. 4. 1. 4. 2.]
[1. 4. 1. 4. 3.]
[1. 4. 2. 1. 3.]
[1. 4. 2. 4. 3.]
[1. 4. 3. 1. 2.]
[1. 4. 3. 4. 2.]
[2. 1. 2. 1. 3.]
[2. 1. 2. 1. 4.]
[2. 1. 2. 3. 4.]
[2. 1. 2. 4. 3.]
[2. 1. 3. 1. 4.]
[2. 1. 3. 2. 4.]
[2. 1. 4. 1. 3.]
[2. 1. 4. 2. 3.]
[2. 3. 1. 2. 4.]
[2. 3. 1. 3. 4.]
[2. 3. 2. 1. 4.]
[2. 3. 2. 3. 1.]
[2. 3. 2. 3. 4.]
[2. 3. 2. 4. 1.]
[2. 3. 4. 2. 1.]
[2. 3. 4. 3. 1.]
[2. 4. 1. 2. 3.]
[2. 4. 1. 4. 3.]
[2. 4. 2. 1. 3.]
[2. 4. 2. 3. 1.]
[2. 4. 2. 4. 1.]
[2. 4. 2. 4. 3.]
[2. 4. 3. 2. 1.]
[2. 4. 3. 4. 1.]
[3. 1. 2. 1. 4.]
[3. 1. 2. 3. 4.]
[3. 1. 3. 1. 2.]
[3. 1. 3. 1. 4.]
[3. 1. 3. 2. 4.]
[3. 1. 3. 4. 2.]
[3. 1. 4. 1. 2.]
[3. 1. 4. 3. 2.]
[3. 2. 1. 2. 4.]
[3. 2. 1. 3. 4.]
[3. 2. 3. 1. 4.]
[3. 2. 3. 2. 1.]
[3. 2. 3. 2. 4.]
[3. 2. 3. 4. 1.]
[3. 2. 4. 2. 1.]
[3. 2. 4. 3. 1.]
[3. 4. 1. 3. 2.]
[3. 4. 1. 4. 2.]
[3. 4. 2. 3. 1.]
[3. 4. 2. 4. 1.]
[3. 4. 3. 1. 2.]
[3. 4. 3. 2. 1.]
[3. 4. 3. 4. 1.]
[3. 4. 3. 4. 2.]
[4. 1. 2. 1. 3.]
[4. 1. 2. 4. 3.]
[4. 1. 3. 1. 2.]
[4. 1. 3. 4. 2.]
[4. 1. 4. 1. 2.]
[4. 1. 4. 1. 3.]
[4. 1. 4. 2. 3.]
[4. 1. 4. 3. 2.]
[4. 2. 1. 2. 3.]
[4. 2. 1. 4. 3.]
[4. 2. 3. 2. 1.]
[4. 2. 3. 4. 1.]
[4. 2. 4. 1. 3.]
[4. 2. 4. 2. 1.]
[4. 2. 4. 2. 3.]
[4. 2. 4. 3. 1.]
[4. 3. 1. 3. 2.]
[4. 3. 1. 4. 2.]
[4. 3. 2. 3. 1.]
[4. 3. 2. 4. 1.]
[4. 3. 4. 1. 2.]
[4. 3. 4. 2. 1.]
[4. 3. 4. 3. 1.]
[4. 3. 4. 3. 2.]