回溯法
回溯法是一种暴力试错法，其核心思想就是：
1.采用递归的方法对树进行深度优先遍历。
2.在遍历过程中去掉不符合约束条件的情况，达到剪枝的目的。
3.在各叶子节点返回递归结果。
例子：
8皇后问题。
如何将 8 个皇后放置在 8×8 的棋盘上，并且使皇后彼此之间不能相互攻击。
（国际象棋中，皇后可以横竖斜走1-7个单位）。
思路：
1.逐一判断所有8个皇后在棋盘上的摆法，可得到结果。（暴力试错）
2.同一行不可能有两个皇后，因此问题变成了每行摆一个皇后，选择其中的可行结果。（大量减少时间）
3.递归扫描所有情况。（深度优先遍历）
4.每次递归判断如果可以互相攻击，则返回，该路径废除。（剪枝）
5.然后判断是否是最后一行，如果是，表示此方案可行，可以进行打印等操作。
核心伪代码：
backtrack(选择列表, 棋盘状态):
if 能攻击到:
return
if 最后一行::
打印棋盘状态
return
for 选择 in 选择列表:
根据选择修改棋盘状态
backtrack(选择列表，棋盘状态)
撤销修改棋盘状态
评论