python小练习（056）：四种方法求解八皇后问题
本帖最后由 jerryxjr1220 于 2017-3-27 03:32 编辑一. 八皇后问题的定义：
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。
该问题是国际西洋棋棋手马克斯·贝瑟尔于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多倍的时间，而且程序不过短短二十多行代码，不愧是达人啊！
第四种方法：其实也是排列组合的方法，只是我做了一些优化，因为其实我们并不需要全排列，每一行每一列只有可能出现一个皇后，基于这样我们排列组合的时候就可以针对性的排列，减少很多组合，例如我们用一个一维的数列L 来表示第i行的第L个是皇后的情况。
排列组合是最简单的方法，10多行代码就可以搞定：
**** Hidden Message *****
运行差不多也就3秒，与递归速度相当。 另外提示一下，如果用回溯+递归方法求解n>8的情况时，请调高默认的递归层数，不然有可能超过递归最大深度。
方法：
import sys
sys.setrecursionlimit(1000000) #例如这里设置为一百万 赞一个
学习下 谢谢 到现在都还没搞明白 本帖最后由 jerryxjr1220 于 2017-3-27 03:32 编辑
shigure_takimi 发表于 2017-3-27 01:46
到现在都还没搞明白
看到你的留言，我又想到了一种新的解法，也是基于排列组合的，但是比之前的排列组合方法更优化{:10_256:}
更新好了，第四种方法{:5_95:} 学习一下 n = 8
chess = [*n for i in range(n)]
result = [ ]
def check(x, y):
for i in range(n):
if chess == 1:
return False
for j in range(n):
if chess == 1:
return False
for i in range(n):
for j in range(n):
if i + j == x + y or i - j == x - y:
if chess == 1:
return False
return True
def dfs(step):
if step == n:
result.append(chess)
return
for i in range(n):
if check(step, i):
chess = 1
dfs(step+1)
chess = 0
dfs(0)
print(len(result))
这个思路可能更直接点~ps.自己误打误撞写出来的{:5_107:} WelanceLee 发表于 2017-6-14 15:53
这个思路可能更直接点~ps.自己误打误撞写出来的
你不觉得第四种排列组合的方法更直观，并且更简单吗？{:10_256:} jerryxjr1220 发表于 2017-6-14 16:17
你不觉得第四种排列组合的方法更直观，并且更简单吗？
确实啊~不递归的感觉很不错 666
666 来看下生成器用法 {:5_90:} 看答案 答案答案答案{:5_105:} 看一看 用深度回溯法+递归，写出来的，本想用下生成器，发现用生成器就函数就不动了。
没有深加工，这里得到的是每一行的位置参数。
唉，感觉这几天有点不想动，好迷茫。找不到学习的方向，很喜欢数据结构这一方面
但是貌似找不到一个比较明确的方向。
t = [*8 for i in range(8)]
v = []
v1 = []
v2 = []
begin1 =
begin2 = begin1[:]
def bu(f1,f2):
if len(f1)>0:
f3 = []
for j in range(len(f1)):
f1 -= 1
if f1 >= 0:
f3.append(f1)
f1 = f3
if len(f2)>0:
f4 = []
for k in range(len(f2)):
f2 += 1
if f2 < 8:
f4.append(f2)
f2 = f4
return f1,f2
def tuo(i,f1,f2):
m1 = i-1
m2 = i+1
if 0 <= m1:
f1.append(m1)
if m2 < 8:
f2.append(m2)
def pick(begin1,v,v1,v2):
if len(v)== 8:
print(v)
return 1
for i in begin1:
f = v[:]
f1 = v1[:]
f2 = v2[:]
f.append(i)
f1,f2 = bu(f1,f2)
tuo(i,f1,f2)
f3 = set(f + f1 + f2)
begin =
pick(begin,f,f1,f2)
pick(begin1,v,v1,v2)