这样的话，证明，贪心算法是不能以最少的颜色解决所有的图着色问题的，啊…那怎么找出最少的颜色啊？？？有一个坏消息：
目前，大概是只能选择深度优先搜索了。。。摸摸毛，没有关系，网上的回溯算法很多，也很简单，但是我可以做更多的优化，关键是网上好像都没有预着色的步骤，所以这里可以创新一下。
数独问题的图搜索策略
深度优先搜索，出现无解的情况进行回溯，回溯到上一级继续进行尝试。
具体步骤
- 把起始节点S放到一个叫做OPEN的未扩展节点表中(简称OPEN表).如果此节点为一目标节点,则得到一个解
- 建立一个叫做 CLOSED的已扩展节点表简称 CLOSED表)其初始为空表
- 如果OPEN为一空表,则失败退出.
- 把第一个节点(节点n)从OPEN表移到CLOSED表
- 如果节点n的深度等于最大深度,则转向(3).
- 扩展节点n产生其全部后裔,并把它们放入OPEN表的前头.如果没有后裔,则转向(3)
- 如果后继节点中有任一个为目标节点,则求得一个解.成功退出;否则,转向(3).
主要函数
search(c)：参数c为单元格地址,给定一个c对该单元格所在行、列,所在小九宮格已有数字进行判断,返回还允许填入的数字,用有效数字序列的字符串格式表示,比如返回“1356”,表示该单元格还可以填入1、3、5、6中任一数字,返回“”,表示该单元格无数可填,此时检查OPEN表,若空,则失败退出,在递归程序中返回上一级。
idea
图着色可以应用到多面体的面着色