问题背景
澳大利亚地图染色问题： 用红绿蓝3色标出各省， 相邻者颜色不同。
对应于澳大利亚地图的约束图， 相互关联的节点用边连接。
− 西澳大利亚 – WA
− 北领地 – NT
− 南澳大利亚 – SA
− 昆士兰 – Q
− 新南威尔士 – NSW
− 维多利亚 – V
− 塔斯马尼亚 – T
一组满足约束的完全赋值： { WA=R, NT=G, Q=R, SA=B, NSW=G, V=R, T=R }
澳大利亚地图染色问题的搜索树
一个简单的回溯算法:深度优先(本文不推荐)
用回溯法模版解决染色问题(本文推荐)
如何理解回溯法
回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！
因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。
递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。
回溯法模版回顾
参考文章：代码随想录
从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
溯法解决的问题都可以抽象为树形结构（N叉树）
回溯法模版伪代码
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}模版应用例子
回溯法:0-1背包问题-CSDN博客
解决本文染色问题伪代码(本文推荐)
最后去掉"去掉这个节点染色，即让节点空白"这里欢迎读者对这个地方讨论
void backtracking(当前的节点) {
//下面条件改为"(当前的地图都被染色了"应该也可以
if (当前的地图都被染色了且染色合法) {
存放当前染色结果;
return;
}
//N为总共可染色的色料个数
for (第i种颜色:N) {
if(当前节点染第i种颜色且染色合法){
让该节点染第i种颜色;
//递归
//类似图的遍历中找下一个相邻且未被访问的节点
backtracking(找出下一个当前节点相邻且未被染色的节点);
//个人认为下面这个操作去掉应该也可以
//以防漏掉一些情况,先加上,欢迎读者对这个地方讨论
去掉这个节点染色，即让节点空白
}
}
}
