背景知识
为地图或其他由不同区域组成的图形着色时，相邻国家/地区不能使用相同的颜色。 我们可能还想使用尽可能少的不同颜色进行填涂。一些简单的“地图”（例如棋盘）仅需要两种颜色（黑白），但是大多数复杂的地图需要更多颜色。
每张地图包含四个相互连接的国家时，它们至少需要四种颜色。1852年，植物学专业的学生弗朗西斯·古思里（Francis Guthrie）于1852年首次提出“四色问题”。他观察到四种颜色似乎足以满足他尝试的任何地图填色问题，但他无法找到适用于所有地图的证明。这个问题被称为四色问题。长期以来，数学家无法证明四种颜色就够了，或者无法找到需要四种以上颜色的地图。直到1976年德国数学家沃尔夫冈·哈肯（Wolfgang Haken）（生于1928年）和肯尼斯·阿佩尔（Kenneth Appel，1932年-2013年）使用计算机证明了四色定理，他们将无数种可能的地图缩减为1936种特殊情况，每种情况都由一台计算机进行了总计超过1000个小时的检查。
他们因此工作获得了美国数学学会富尔克森奖。在1990年，哈肯（Haken）成为伊利诺伊大学（University of Illinois）高级研究中心的成员，他现在是该大学的名誉教授。
四色定理是第一个使用计算机证明的著名数学定理，此后变得越来越普遍，争议也越来越小 更快的计算机和更高效的算法意味着今天您可以在几个小时内在笔记本电脑上证明四种颜色定理。
问题描述
我们可以将地图转换为平面图，每个地区变成一个节点，相邻地区用边连接，我们要为这个图形的顶点着色，并且两个顶点通过边连接时必须具有不同的颜色。附件是给出的地图数据，请针对三个地图数据尝试分别使用5个（le450_5a），15个（le450_15b），25个（le450_25a）颜色为地图着色。
算法思想
回溯法
回溯法（back tracking）（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。 但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
在地图填色问题中，我们使用了回溯法。择优对每个点进行探索测试，当点可以使用某种颜色时，将该点进行上色，并继续探索下一个点进行测试。当一个点所有的颜色都不满足条件时，进行回溯，退回到上一个节点，并且寻找下一个满足的颜色。
算法核心伪代码如下：
时间复杂度分析：
由于在每层节点都有type种颜色可填涂，点集set的大小为size，需要递归size层才能出解，所以最坏时间复杂度为
T(n) = O(typesize)最好情况时，每一层涂色都不需要遍历和回溯，最好时间复杂度为
T(n) = O(size)可见时间复杂度为指数级，需要对算法进行剪枝，在大规模地图时需要通过剪枝缩小所需时间。
剪枝优化
1.排序优化->选取点空间剪枝（度、可选颜色）
在前面的普通回溯法中，我们的算法选取点集使用了序列优先，即按照添加进入点集的点顺序来选取点的优先顺序。这种方法虽然不需要占用额外的空间，但是对我们减小解空间没有额外的帮助。
我们可以采取两种策略优先，来减小解空间，优先选出更不容易找到解的点（假设我们要比较点a和点b的优先度）：
- 当点a和点b可以着色的颜色种类不同时，优先选取其中可以填涂颜色种类更少的点；
- 当点a和点b可以着色的颜色种类相同时，优先选取其中邻接点更多（即度更大）的点。
使用策略优先法虽然对回溯的速度没有积极影响，但是可以大大缩小解空间，减少回溯的次数，从而减少算法消耗的时间。
在使用了策略优先后，我们的主算法结构如下：
为每个点集设置可涂色数组can[]以及度degree。 当两点可涂色种类不同时，优先返回可涂色种类较少的点；当两点可涂色种类相同时，优先放回度较大的点。
如果在该点可以涂色，调用update，更新各点数据。
其中若该点的可涂色为1时，将该点的颜色设置为1，同时设置其相邻点的can[1]为0，表示该颜色该点已经不能上色。
当该点上色后，后面颜色发生冲突，证明该涂色方法不成立，进行回溯，将与其相邻点的can[]置为1，同时将自身颜色置为-1。
2.向前探测
单步探测
优化可选解空间后，考虑优化回溯的次数。当点上色成功后，进行单步向前探测。如果该点的其中一个相邻点有且只有一种上色的可能性，且该相邻点的可能颜色与将要上色的颜色相同时，提前终止回溯，并考虑另一个解。当其相邻点已经无解时，说明在回溯进行的过程中，到达该点后该上色方案注定失败，如果能够提前预知并终止该解，就可以减少大量的回溯次数。
多步探测
原理与单步探测相同，但是在试探邻接点可以上色后，通过对该点上色，进一步探测，重复执行相同的动作，称为多步探测。
*经测试后发现多步探测并没有对时间有明显的优化，原因有二：剪枝数量较少，第二步剪枝舍去的点较少；多步探测时间呈指数级增加，不利于优化。
提前探测
以上的探测执行都在数据更新之后，当数据更新（update）后，如果向前探测返回false，进行数据回溯（back）。
我们可以进行进一步优化，将向前探测的过程置于legal中进行判断。如果向前探测返回false，则legal返回false，提前终止回溯，节省update和back的成本开销。
