1.什么是试探算法？
2.试探算法的解题的基本步骤
3.试探算法的思想
4.试探算法适合的问题
5.试探算法解决“八皇后”的问题
试探算法也叫回溯法，试探算法的处事方式比较委婉，它暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是正确的解时，就选择下一个候选解。如果当前候选解不满足问题规模要求外， 能够满足所有其他要求，则继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求，该候选解就是问题的一个解。在试探算法中，放弃当前候选解，并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，并继续试探的过程称为向前试探。
为了求得问题的正确解，试探算法会先委婉地试探某种可能的情况。在进行试探的过程中，一旦发现原来选择的假设情况是不正确的，立即会自觉的退回一步重新选择，然后继续向前试探，如此这般反复进行，直至得到解或证明无解时才死心.
比如有一个元组n组成的一个状态空间，关于元组n,有多个条件组成的约束集合，满足这个条件约束集合的任一n元组为问题的一个解。只要检测出元组中有一个违反了约束，就可以肯定这个元组就不是问题的解，因而不必去搜素和检测它们，试探算法就是针对这类问题而推出的，比枚举算法的效率更高。
“八皇后”问题是一个古老而著名的问题，是试探法的典型例题。该问题由19世纪的数学家高斯于1850年手工解决：在8×8的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
可以将整个问题简化为4×4的棋盘，就有两种摆法，每行摆在列2、4、1、3或列3、1、4、2上
试探算法将每行的可行位置入栈（就是放入数组a[5]，用的是a[1]~a[4]），不行就退栈还列重新试，直到找到一套方案并输出，接着从第一行换列重试其他方案。
为了简化问题，考虑到8个皇后不同行，则每一行放置一个皇后，每一行的皇后可以放置于第0~7列，我们认为每一行的皇后有8种状态。那么，只要套用子集树模板，从第0行开始，自上而下，对每一行的皇后，遍历它的8个状态即可。
n = 8 x = [] # 一个解（n元数组） X = [] # 一组解 # 冲突检测：判断x[k] 是否与前面的x[0] ~ x[k-1] def conflict(k): global x for i in range(k): # 遍历前面的x[0] ~ x[k-1]： if x[i] == x[k] or abs(x[i] - x[k]) == abs(i - k): # 判断是否与x[k]冲突 return True return False # 套用子集树模板 def queens(k): # 到达第k行 global n, x, X if k >= n: # 超出最底行 X.append(x[:]) # 保存（一个解），注意x[:] else: for i in range(n): # 遍历第0~n-1列（即n个状态） x.append(i) # 皇后置于第i列，入栈 if not conflict(k): # 剪枝 queens(k + 1) x.pop() # 回溯，出栈 def show(x): global n for i in range(n): print('. ' * (x[i]) + 'X ' + '. ' * (n - x[i] - 1)) if __name__ == '__main__': queens(0) # 从第0行开始 print(X[-1], '\n') show(X[-1])程序运行结果：
