八皇后问题--递归回溯算法（Python实现）

前两天做牛客的时候遇到了一个字符串的全排列问题。顺便回顾一下八皇后问题。（后附Python代码）

如何解决八皇后问题？

所谓递归回溯，本质上是一种枚举法。这种方法从棋盘的第一行开始尝试摆放第一个皇后，摆放成功后，递归一层，再遵循规则在棋盘第二行来摆放第二个皇后。如果当前位置无法摆放，则向右移动一格再次尝试，如果摆放成功，则继续递归一层，摆放第三个皇后......

如果某一层看遍了所有格子，都无法成功摆放，则回溯到上一个皇后，让上一个皇后右移一格，再进行递归。如果八个皇后都摆放完毕且符合规则，那么就得到了其中一种正确的解法。

解决八皇后问题，可以分为两个层面：

1.找出第一种正确摆放方式，也就是深度优先遍历。

2.找出全部的正确摆放方式，也就是广度优先遍历。

研究代码实现过程中，要解决以下几个问题：

1.国际象棋的棋盘如何表示？

很简单，用一个长度是8的二维数组来表示即可。

2.如何判断皇后的落点是否合规？

定义一个conflict方法，传入新皇后的落点，通过纵向和斜向是否存在其他皇后来判断是否合规。

3.如何进行递归回溯？

递归回溯是本算法的核心，代码逻辑有些复杂

4.如何输出结果？

这个问题很简单，直接遍历二维数组并输出就可以。

5.如何把这些方法串起来？

在main函数里分三步来调用：

第一步：初始化

第二步：递归摆放皇后

第三步：最后输出结果。

#coding=UTF-8
import random
#冲突检查，在定义state时，采用state来标志每个皇后的位置，其中索引用来表示横坐标，基对应的值表示纵坐标，例如： state[0]=3，表示该皇后位于第1行的第4列上
def conflict(state, nextX):
    nextY = len(state)
    for i in range(nextY):
        #如果下一个皇后的位置与当前的皇后位置相邻（包括上下，左右）或在同一对角线上，则说明有冲突，需要重新摆放
        if abs(state[i]-nextX) in (0, nextY-i):
        # 表示如果下一个皇后和正在考虑的前一个皇后的水平距离为0或者垂直距离相等，就返回TRUE，否则返回False
            return True
    return False

#采用生成器的方式来产生每一个皇后的位置，并用递归来实现下一个皇后的位置。
def queens(num, state=()):
    for pos in range(num):
        if not conflict(state, pos):
            #产生当前皇后的位置信息
            #如果只剩一个皇后没有放置
            if len(state) == num-1:
                yield (pos, )
            #否则，把当前皇后的位置信息，添加到状态列表里，并传递给下一皇后。
            #程序要从前面的皇后得到包含位置信息的元组（元组不可更改）
            #并要为后面的皇后提供当前皇后的每一种合法的位置信息
            #所以把当前皇后的位置信息，添加到状态列表里，并传递给下一皇后。
            else:
                for result in queens(num, state+(pos,)):
                    yield (pos, ) + result


#为了直观表现棋盘，用X表示每个皇后的位置
def prettyprint(solution):
    def line(pos, length=len(solution)):
        return '. ' * (pos) + 'X ' + '. '*(length-pos-1)
    for pos in solution:
        print line(pos)
    for item in queens(8):
        print item

if __name__ == "__main__":
    prettyprint(random.choice(list(queens(8))))

length = len(queens(8))        #92种

for item in queens(8):

    print item                        #输出每一种表示

输出如下一种结果：

参考资料：1.书圈 的一个漫画 “什么是八皇后问题”点击打开链接

                2.[挪]Python基础教程9.9节八皇后问题