1. 参考

  1. 《程序设计基础》9.2.6分书问题，9.2.7（八皇后问题）
  2. 知乎：一篇总结带你彻底搞透回溯算法！

2. 简要介绍

可以用走迷宫的方式去理解回溯，设想把你放在一个迷宫里，想要走出迷宫，最直接的办法是什么呢？没错，试。先选一条路走起，走不通就往回退尝试别的路，走不通继续往回退，直到走遍所有的路，并且在走的过程中你可以记录所有能走出迷宫的路线。

2.1 回溯与八皇后问题

在国际象棋中，皇后是最强大的一枚棋子，可以吃掉与其在同一行、列和斜线的敌方棋子。八皇后问题是这样一个问题：将八个皇后摆在一张8*8的国际象棋棋盘上，使每个皇后都无法吃掉别的皇后，一共有多少种摆法？

如果使用暴力穷举算法的话要在8*8个格子中选择8个格子来摆放皇后，一共要尝试 C648C_{64}^{8} 次，十亿级别的尝试次数！

稍加分析，我们可以得到一个不那么暴力的办法，显然，每行每列最多只能有一个皇后，如果基于这个事实进行暴力破解，那结果会好得多。安排皇后时，第一行有8种选法，一旦第一行选定，假设选为（1，i），第二行只能选（2，j），其中j!=i，所以有7种选法。以此类推，需要穷举的情况有8！=40320种。

我们先降下规模来看看4皇后问题：4个皇后在4*4的格子里各自安排不打架，一共有多少种安排方法？试着来穷举一下，真的需要4！=24次尝试吗？现在我们把第一个皇后放在第一个格子，被涂黑的地方是不能放皇后的。

Q1的控制线
Q      
     
     
       

第二行的皇后只能放在第三格或第四格，按照回溯我们要先尝试放在第三格，则：

Q1、Q2的控制线
Q      
  Q  
     
       

这样第三位皇后无论放哪里都难逃被吃掉的厄运。于是在第一个皇后位于1号，第二个皇后位于3号的情况下问题无解。我们只能返回上一步来，给2号皇后换个位置。

Q1、Q2的控制线
Q      
  Q
     
       

显然，第三个皇后只有一个位置可选。当第三个皇后占据第三行蓝色空位时，第四行皇后无路可走，于是发生错误，返回上层调用（3号皇后），而3号也别无可去，继续返回上层调用（2号），2号已然无路可去，继续返回上层（1号），于是1号皇后改变位置如下，继续搜索。

考虑Q1的控制线
Q    
     
     
       

代码方面，回溯算法的框架：

result = []
def try(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        try(路径, 选择列表)
        撤销选择

3. 编程练习

  1. 标记皇后的攻击区域
  2. 回溯法解N皇后
  3. 分书问题

4. 阅读题