三种不同算法求解八皇后问题：排列组合、回溯法+递归、生成器+递归
一. 八皇后问题的定义：八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。
该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：
在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。
二. 八皇后问题的引申 -- N皇后问题：
当n x n格的棋盘上摆放n个皇后，使其相互不能攻击，则此问题转化为n皇后问题。
显然n = 1，2，3都无解，所以n>=4。
三. 解法一： 排列组合：
当n值=4时，由排列组合C（4*4，4） = 1820 种不同排列 (算法为：math.factorial(16)/math.factorial(4)/math.factorial(16-4) = 1820，下同)
当n值=5时，由排列组合C（5*5，5） = 53130 种不同排列
当n值=6时，由排列组合C（6*6，6） = 1947792 种不同排列
当n值=7时，由排列组合C（7*7，7） = 85900584 种不同排列
当n值=8时，由排列组合C（8*8，8） = 4426165368 种不同排列
依据我们目前使用的家用型计算机，当n<7时，还勉强可以计算一下，当n>=7 时，基本上就等不起了，耗时非常长。
不过排列组合的解法是最通俗易懂，也是最简单暴力的方法，程序就不多做说明了，直接看源代码就好了：
import itertools as it
n = 6
blank = n*n
chest = [*n for i in range(n)]
comb = it.combinations(list(range(blank)),n)
def check(x,y):
if max(chest) == 1:
return False
if max( for i in range(n)]) == 1:
return False
for i in range(n):
for j in range(n):
if i+j == x+y or i-j == x-y:
if chest == 1:
return False
return True
queen = 0
c = 0
for each in comb:
for e in each:
x = e//n
y = e%n
if check(x,y):
chest = 1
queen += 1
else:
chest = [*n for i in range(n)]
queen = 0
break
if queen == n:
c += 1
print ('Solution %d:' % c)
for q in chest:
print (q)
print ('*'*20)
chest = [*n for i in range(n)]
queen = 0
输出：
n = 6时的解：
Solution 1:
********************
Solution 2:
********************
Solution 3:
********************
Solution 4:
********************
可以看到，当n=6时，用时已经需要36秒以上了。
四. 解法二：回溯法+递归：
解题的思路已经写在注释里了，直接读源代码吧。
源代码：
**** Hidden Message *****
当n=8时（八皇后），输出：
Solution 1:
Solution 2:
中间省略N个解
Solution 91:
Solution 92:
Total Solution 92, done!
可以看到，用时已经非常短了。
五. 解法三：生成器+递归：
解法三的算法不是我写出来的，我是参考了网上的达人的方法，用了生成器的方法，这样使得程序更简短、效率更高、更符合python的理念。
源代码：
**** Hidden Message *****
当n=8时，输出：
省略前面若干解
Solution 91:
Solution 92:
看到耗时只有0.3s，比我的递归解法缩短了10多倍的时间，而且程序不过短短二十多行代码，不愧是达人啊！ 我来学习 谢谢楼主分享 学习学习 好好看看代码 我也学学 ！！！！！！！！！！！！！！！！ 回复 学习学习 {:5_92:}{:5_92:} {:5_91:} 谢谢分享{:5_110:} sfdfgdfh 学习学习 。。。。。 {:10_257:}{:10_257:}{:10_257:}{:10_256:}。。。。。。 看看 谢谢楼主分享 学习学习
好好学习
学习学习 学会算法，走遍天下