穷举法的方法就是遍历所有的可能解。
我用iphone 6 测试了穷举法的效率：采用的是幻方（magic square）谜题解法：
试将1~9这9个不同整数填入一个3x3的表格，使得每行，每列以及每条对角线上的数字之和相同。
| ? | ? | ? |
|---|---|---|
| ? | ? | ? |
| ? | ? | ? |
使用穷举法，那么可能性有 9! = 362880 种可能。
**测试结果： 需要只用76秒。 **
使用的代码为：
private let MAGIC_SQUARE = 3;
private let beginTime = Date.init().timeIntervalSince1970;
override func viewDidLoad() {
super.viewDidLoad()
let result = Array<Int>.init();
var possibility = Array<Int>.init();
for index in 0..<(MAGIC_SQUARE * MAGIC_SQUARE)
{
possibility.append(index)
}
print("beginTime is \(beginTime)")
methodOfExhuastion(result: result, possibility: possibility)
}
func methodOfExhuastion(result:Array<Int>, possibility:Array<Int>) -> Void {
if 0 >= possibility.count {
print("result is \(result)")
let nowTime = Date.init().timeIntervalSince1970
let usingTime = nowTime - beginTime;
print("usingTime is \(usingTime)")
return;
}
for index in 0..<possibility.count
{
let number = possibility[index];
var tempResult = Array<Int>.init(result);
tempResult.append(number);
var tempPossibility = Array<Int>.init(possibility);
tempPossibility.remove(at: index);
methodOfExhuastion(result: tempResult, possibility: tempPossibility);
}
}
当幻方为2 x 2时，测试结果： 0.05秒。
当幻方为4 x 4时，测试结果： ？？？？
执行了1189秒时，才遍历到了第9位。
当幻方为5 x 5时，这个时候就会出现计算机已经无能为力。
是的你没看错，（（5 x 5）x （5 x 5））！ = 1.5 x 10000000000000000000000000（25个0）.如果是每秒计算100 000亿次的计算机，需要使用49 000年才能完成这项任务。你可以计算下。 当我看到这个结果时，我也是被震惊了。在等待4 x 4的计算时，我也已经觉得数据量大的概念是什么了。
16! = 2.0 x 10000000000000(13个0)。
SO， 尽量少用穷举法。可以尝试回溯法（backtracking）。
算法设计：
穷举搜索 -> 回溯法 -> 减而治之 -> 分而治之 -> 变而治之 -> 贪心法 -> 迭代改进 -> 动态规划
