应用Python递归求解“八皇后”问题

近日，无意间又看到了“八皇后”这个题目，回想起曾经在学校时遇到过这个问题，但当时未能如愿求解，于是便想再次尝试。

八皇后问题是一个古老的问题（1848年），也是算法和编程领域的经典话题，常常是应用递归求解的范例。

问题描述：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

问题拓展：八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n1×n1，而皇后个数也变成n2。

八皇后问题的一个解（网图侵删）

求解八皇后问题，实际上，因为棋盘和皇后的维度不大，倘若采用暴力计算的方式其实也是可行的：因为八个皇后分布在8×8的棋盘上，那么从排列组合的角度上其实就是64个棋位中选择8个来安放皇后，即理论上有64选8= 4426165368~4.4G次计算。如果稍加筛选，那么其实八皇后必定是每行1个且每列也是1个，这样对于八皇后的分布位置实际上就是8！×8！= 1625702400~1.6G，然后对于每种理论分布再分别判断是否在行列上有重复或者在对角线上有通视即可。

然而，虽然计算量降低到1/3，但复杂度依然不可接受。如果八皇后的规模再稍微增长一点，那么计算量是阶数级的提高，瞬间暴涨！

而如果应用递归的思想来进行求解，那么该问题的计算量则大大降低。

递归，就是设计程序不断调用自身从而实现问题降维和求解的过程。

应用递归求解八皇后问题，首先，既然8个皇后放在8×8的棋盘上，那么每行肯定有且只有1个皇后，所以问题的核心就是在已经安排好前i个皇后理想位置的基础上（i=0时即为初始状态），如何顺序查找在第i+1行找到第i+1个皇后合适位置的问题。又分2种情况：

• 在i个皇后已安放理想的基础上，在第i+1行可能找到一种可能性，确保这i+1个皇后都“相安无事”，此时令i=i+1，递归继续或者i=7递归完毕；
• 是遍历了第i+1行，也无法找到一种允许这i+1个皇后共存的排布方案，此时就要回溯到前i个皇后的其他可行方案，看能否存在其他方案允许第i+1个皇后安放进来。

八皇后递归求解流程（拙图）

按此思路，利用python实现，求得最终八皇后的方案数有92种。