三种不同算法求解八皇后问题：排列组合、回溯法+递归、生成器+递归

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多倍的时间，而且程序不过短短二十多行代码，不愧是达人啊！

hvagab

我来学习

西瓜小刚

谢谢楼主分享 学习学习

呵呵哒123

好好看看代码

岁月依旧

我也学学

wo4wangle

！！！！！！！！！！！！！！！！

jikecoder

回复

YURiCa

学习学习

luohaoyan

DHP

HelloNewWorld

谢谢分享

weisuo

sfdfgdfh

fightingzjf

学习学习

Justin_u

。。。。。

Justin_u

。。。。。。

新手·ing

看看

独门暗器

谢谢楼主分享 学习学习

Code_mzh

好好学习

Bekkkkkahhh

学习学习

90182si

学会算法，走遍天下