急！！！！！ 招聘时给的关于“四色”题，请大虾们给点意见

Question

软件设计问题,已经表明,可以最多四种颜色对行政区图上色.使得相邻的行政区颜色不同.请设计一个程序,完成行政区图的上色方案的算法.要求:1.提供完备的输入,输出手段,可充分验证算法.     2.上色方案并不唯一,考虑多种上色方案(可通过程序演示),选出其中较好的一种,将其参数存入数据库,并说明理由.     3.可使用delphi,vc等语言提示:    1.上色采用试探回溯算法,一步一步的试探,若全部行政区都试完,则算法完成.否则,向前回溯一步,接着进行试探.    2.采用二维矩阵表示行政区的相邻关系    3.采用一个堆栈来纪录没一步的试探结果.

Answer 1

假设有n个国家，
你建一个 n*n的数组。比如 1,2,3...代表国家编号   1  2  3  4  5  6
1
2  x 
3     x
4  x  x
5     x     x
6              x相邻的你就标志一下，比如X，不相邻的就是空。递归方法给每个国家添颜色，然后按照这个表来检查相邻的国家是否有相同颜色的。
比如国家 2， 3 都是红色，一查表，2,3是相邻的，说明颜色方案不对，需要修改；
再比如 2, 5都是红的，查表可知他们不相邻，此方案可行。关于著名的4色问题的证明，就是把这个矩阵的所有组合都测试一遍，结果4色足够，这个证明如果人来做可能需要几百年，但是据说当时计算机24个小时就算完了（现在的计算机估计几分钟就完了）。这个你该能看明白吧？