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 时，基本上就等不起了，耗时非常长。

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

import itertools as it 
n = 6
blank = n*n
chest = [[0]*n for i in range(n)]
comb = it.combinations(list(range(blank)),n)

def check(x,y):
        if max(chest[x]) == 1:
                return False
        if max([chest[i][y] 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[i][j] == 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[x][y] = 1
                        queen += 1
                else:
                        chest = [[0]*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 = [[0]*n for i in range(n)]
                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[i]个是皇后的情况。
排列组合是最简单的方法，10多行代码就可以搞定：

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

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

jerryxjr1220

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

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

yifenyu

赞一个

WelanceLee

学习下

新手·ing

谢谢

shigure_takimi

到现在都还没搞明白

jerryxjr1220

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

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

更新好了，第四种方法

YURiCa

学习一下

WelanceLee

n = 8
chess = [[0]*n for i in range(n)]
result = [ ]

def check(x, y):
    for i in range(n):
        if chess[i][y] == 1:
            return False
    for j in range(n):
        if chess[x][i] == 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[i][j] == 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[step][i] = 1
            dfs(step+1)
        chess[step][i] = 0

dfs(0)
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饭

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

t = [[0]*8 for i in range(8)]

v = []
v1 = []
v2 = []
begin1 = [i for i in range(8)]
begin2 = begin1[:]

def bu(f1,f2):
    if len(f1)>0:
        f3 = []
        for j in range(len(f1)):
            f1[j] -= 1
            if f1[j] >= 0:
                f3.append(f1[j])
        f1 = f3
    if len(f2)>0:
        f4 = []
        for k in range(len(f2)):
            f2[k] += 1
            if f2[k] < 8:
                f4.append(f2[k])
        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 = [i for i in begin2 if i not in f3]
    
        pick(begin,f,f1,f2)
        
pick(begin1,v,v1,v2)