python小练习（056）：四种方法求解八皇后问题

jerryxjr1220

一. 八皇后问题的定义：

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。

该问题是国际西洋棋棋手马克斯·贝瑟尔于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 时，基本上就等不起了，耗时非常长。

不过排列组合的解法是最通俗易懂，也是最简单暴力的方法，程序就不多做说明了，直接看源代码就好了：

1. import itertools as it
   
2. n = 6
   
3. blank = n*n
   
4. chest = [[0]*n for i in range(n)]
   
5. comb = it.combinations(list(range(blank)),n)
   
6. 
   
7. def check(x,y):
   
8.         if max(chest[x]) == 1:
   
9.                 return False
   
10.         if max([chest[i][y] for i in range(n)]) == 1:
    
11.                 return False
    
12.         for i in range(n):
    
13.                 for j in range(n):
    
14.                         if i+j == x+y or i-j == x-y:
    
15.                                 if chest[i][j] == 1:
    
16.                                         return False
    
17.         return True
    
18. 
    
19. queen = 0
    
20. c = 0
    
21. for each in comb:
    
22.         for e in each:
    
23.                 x = e//n
    
24.                 y = e%n
    
25.                 if check(x,y):
    
26.                         chest[x][y] = 1
    
27.                         queen += 1
    
28.                 else:
    
29.                         chest = [[0]*n for i in range(n)]
    
30.                         queen = 0
    
31.                         break
    
32.         if queen == n:
    
33.                 c += 1
    
34.                 print ('Solution %d:' % c)
    
35.                 for q in chest:
    
36.                         print (q)
    
37.                 print ('*'*20)
    
38.                 chest = [[0]*n for i in range(n)]
    
39.                 queen = 0

复制代码

输出：
n = 6时的解：
Solution 1:
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 1, 0]
********************
Solution 2:
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0]
[1, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
********************
Solution 3:
[0, 0, 0, 1, 0, 0]
[1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0]
********************
Solution 4:
[0, 0, 0, 0, 1, 0]
[0, 0, 1, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0]
********************
[Finished in 36.1s]

可以看到，当n=6时，用时已经需要36秒以上了。

四. 解法二：回溯法+递归：

解题的思路已经写在注释里了，直接读源代码吧。

源代码：

游客，如果您要查看本帖隐藏内容请回复

当n=8时（八皇后），输出：
Solution 1:
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0]

Solution 2:
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]

中间省略N个解

Solution 91:
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 0, 0, 0]

Solution 92:
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 1, 0, 0, 0]

Total Solution 92, done!
[Finished in 4.0s]

可以看到，用时已经非常短了。

五. 解法三：生成器+递归：

解法三的算法不是我写出来的，我是参考了网上的达人的方法，用了生成器的方法，这样使得程序更简短、效率更高、更符合python的理念。

源代码：

游客，如果您要查看本帖隐藏内容请回复

当n=8时，输出：

省略前面若干解


Solution 91:
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 0, 0, 0]

Solution 92:
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 1, 0, 0, 0]

[Finished in 0.3s]
看到耗时只有0.3s，比我的递归解法缩短了10多倍的时间，而且程序不过短短二十多行代码，不愧是达人啊！

第四种方法：其实也是排列组合的方法，只是我做了一些优化，因为其实我们并不需要全排列，每一行每一列只有可能出现一个皇后，基于这样我们排列组合的时候就可以针对性的排列，减少很多组合，例如我们用一个一维的数列L 来表示第i行的第L个是皇后的情况。
排列组合是最简单的方法，10多行代码就可以搞定：

游客，如果您要查看本帖隐藏内容请回复

运行差不多也就3秒，与递归速度相当。

jerryxjr1220

另外提示一下，如果用回溯+递归方法求解n>8的情况时，请调高默认的递归层数，不然有可能超过递归最大深度。
方法：

1. import sys
   
2. sys.setrecursionlimit(1000000) #例如这里设置为一百万

复制代码

yifenyu

赞一个

WelanceLee

学习下

新手·ing

谢谢

shigure_takimi

到现在都还没搞明白

jerryxjr1220

shigure_takimi 发表于 2017-3-27 01:46
到现在都还没搞明白

看到你的留言，我又想到了一种新的解法，也是基于排列组合的，但是比之前的排列组合方法更优化

更新好了，第四种方法

YURiCa

学习一下

WelanceLee

1. n = 8
   
2. chess = [[0]*n for i in range(n)]
   
3. result = [ ]
   
4. 
   
5. def check(x, y):
   
6.     for i in range(n):
   
7.         if chess[i][y] == 1:
   
8.             return False
   
9.     for j in range(n):
   
10.         if chess[x][i] == 1:
    
11.             return False
    
12.     for i in range(n):
    
13.         for j in range(n):
    
14.             if i + j == x + y or i - j == x - y:
    
15.                 if chess[i][j] == 1:
    
16.                     return False
    
17.     return True
    
18. 
    
19. def dfs(step):
    
20.     if step == n:
    
21.         result.append(chess)
    
22.         return
    
23.     for i in range(n):
    
24.         if check(step, i):
    
25.             chess[step][i] = 1
    
26.             dfs(step+1)
    
27.         chess[step][i] = 0
    
28. 
    
29. dfs(0)
    
30. print(len(result))

复制代码

这个思路可能更直接点~ps.自己误打误撞写出来的

jerryxjr1220

WelanceLee 发表于 2017-6-14 15:53
这个思路可能更直接点~ps.自己误打误撞写出来的

你不觉得第四种排列组合的方法更直观，并且更简单吗？

WelanceLee

jerryxjr1220 发表于 2017-6-14 16:17
你不觉得第四种排列组合的方法更直观，并且更简单吗？

确实啊~不递归的感觉很不错

badaoqingchen

666

badaoqingchen

666

qaz123765

来看下生成器用法

liuwenqi

x3re5

看答案

小百合

答案答案答案

yjsx86

看一看

JAY饭

用深度回溯法+递归，写出来的，本想用下生成器，发现用生成器就函数就不动了。
没有深加工，这里得到的是每一行的位置参数。
唉，感觉这几天有点不想动，好迷茫。找不到学习的方向，很喜欢数据结构这一方面
但是貌似找不到一个比较明确的方向。

1. t = [[0]*8 for i in range(8)]
   
2. 
   
3. v = []
   
4. v1 = []
   
5. v2 = []
   
6. begin1 = [i for i in range(8)]
   
7. begin2 = begin1[:]
   
8. 
   
9. def bu(f1,f2):
   
10.     if len(f1)>0:
    
11.         f3 = []
    
12.         for j in range(len(f1)):
    
13.             f1[j] -= 1
    
14.             if f1[j] >= 0:
    
15.                 f3.append(f1[j])
    
16.         f1 = f3
    
17.     if len(f2)>0:
    
18.         f4 = []
    
19.         for k in range(len(f2)):
    
20.             f2[k] += 1
    
21.             if f2[k] < 8:
    
22.                 f4.append(f2[k])
    
23.         f2 = f4
    
24.     return f1,f2
    
25. 
    
26. def tuo(i,f1,f2):
    
27.     m1 = i-1
    
28.     m2 = i+1
    
29.     if 0 <= m1:
    
30.         f1.append(m1)
    
31.     if m2 < 8:
    
32.         f2.append(m2)
    
33. 
    
34. def pick(begin1,v,v1,v2):
    
35.    
    
36.     if len(v)== 8:
    
37.         print(v)
    
38.         return 1
    
39.         
    
40.    
    
41.     for i in begin1:
    
42.         f = v[:]
    
43.         f1 = v1[:]
    
44.         f2 = v2[:]
    
45.             
    
46.         f.append(i)
    
47.         f1,f2 = bu(f1,f2)
    
48.         tuo(i,f1,f2)
    
49.                                 
    
50.         f3 = set(f + f1 + f2)
    
51.         begin = [i for i in begin2 if i not in f3]
    
52.    
    
53.         pick(begin,f,f1,f2)
    
54.         
    
55. pick(begin1,v,v1,v2)

复制代码