n皇后问题算法思路和python解法

问题描述

n皇后问题，在n×n的棋盘上，解出n个皇后所有不能互相攻击的摆法，
皇后在数组中用“Q”表示，空地用“.”表示
返回的数据结构格式要求：[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
注：皇后在棋盘中的攻击范围是横、竖、左和右中位线的四个方向

解题思路分析

红色划线部分为皇后的攻击范围，不可以放另外一个皇后
横竖方向的限制很容易：只要与当前Q的行和列相同的索引的部分全部禁止即可

关键的难点是如何处理左右斜线方向的皇后禁止放置点

思考的时候从关键点出发，如果使用穷举判断的方式处理，需要在遍历每一行的时候都判断是否是前面所有已放置皇后的攻击范围，首先这个处理方式就需要增加一层1, 2, 到 n的循环，其次判断皇后的斜线攻击范围直接处理并不方便

因此着手于关键点继续思考，只有尝试寻找斜线方向攻击范围是否存在什么规律，如果能找到规律应该能减少不少的处理复杂度
这里就直接放结论了，规律的思考和寻找主要是靠自己多观察、学习和动手尝试
对于正斜线方向，对于图中的Q地点视为坐标系原点，往右方向是x轴，往下方向是y轴，那么左斜线攻击范围是一条y=-x的线，右斜线方向攻击范围是一条y=x的线

这是对于第一行的Q
对于其他行的Q，也有类似的规律，左斜线攻击范围满足y+x=c, 右斜线方向攻击范围满足y-x=c，c是一个常数
例如Q在第三行的第一个位置(2, 0)，
那么第一行的(0, 2)和第二行的(1, 1)是左斜线的攻击范围（满足x+y=2的规律）
第四行的(3, 1)是右斜线的攻击范围（满足y-x=2的规律）

理解规律之后就剩下代码的逻辑处理了，

代码实现

# -*- coding:utf-8 -*-

class Solution:
    def solve_n_queens(self, n):
        # 1.定义一个二维数组用于存放Q在各行的位置（索引），每一个解法对应一个数组
        result = []  # 有几种解法目前还不确定

        # 2.遍历n×n棋盘求解
        # 2.1 按行遍历时，每行最多只能存放1个Q，遍历一次即可无需其他处理，因此递归回溯时只需要将Q能存放的列索引存储即可（所有解法）

        def backtrack(att_vertical, att_left, att_right):
            # 3.1 当遍历n次找到了n个皇后位置时递归结束，所有解法都找了一遍
            l_vertical = len(att_vertical)
            if l_vertical == n:
                result.append(att_vertical)
                return None
            for i in range(n):  # 这里可以认为行列同时增加，可以理解为for i, j in zip(n, n): ...
                # 3.2 将当前Q的所有攻击范围都搜索和加入到对应的累积攻击范围的数组中
                # 3.2.1 列攻击范围对应的值是i不用解释，
                # 左斜线攻击范围的值是i+l_vertical包含了当前行所有位置Q的左斜线攻击范围: 以n=4为例，l_vertical可能的取值为[0,3]（为4时结束），i的取值范围也是[0,3]，
                # 所以分别相加就是所有左斜线攻击范围的值
                # 右斜线攻击范围同理
                # left: x+y的值是常数，right: x-y的值是常数，x对应i，y对应l_vertical
                if i not in att_vertical and (i + l_vertical) not in att_left and (i - l_vertical) not in att_right:
                    # 3.2.2 当前Q的列不在攻击范围+左斜线不在攻击范围+右斜线不在攻击范围（这里的攻击范围是当前位置已累计的攻击范围），那么就可以加入当前Q的攻击范围并往下继续搜寻
                    backtrack(att_vertical + [i], att_left + [i + l_vertical], att_right + [i - l_vertical])
            # 当遍历n次没有找到解法时也会结束

        # 3. 皇后的攻击范围是：列、左斜线、右斜线方向，分别用3个数组存放其位置（索引）
        backtrack([], [], [])  # e.g. [[1, 3, 0, 2], [2, 0, 3, 1]]
        return [[i * "." + "Q" + (n - i - 1) * "." for i in sol] for sol in result]


if __name__ == '__main__':
    s = Solution()
    print(s.solve_n_queens(4))

输出

[['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]

代码主要的逻辑功能都写在了注释里面，这里主要补充result的作用，由于结果的格式是类似[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]的方式存储，因此设计result存放每种存放方式的一个数组，每种存放方式的数组的Q的列索引，也就是变量cols存放的值，都对应存放到了result中，对于这个示例，result的值是[[1, 3, 0, 2], [2, 0, 3, 1]]，最后根据Q的索引值生成空地“.”和皇后“Q”的位置

关于N皇后的问题，这种回溯递归的方法在n很大的时候仍然会持有不少的时间复杂度，要进一步减少复杂度，还有一种位运算的方式，是N皇后问题的最优解法，这种解决方式的记录和解析将会在下一节的时候补充进来