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

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

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

解题思路分析

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

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

思考的时候从关键点出发，如果使用穷举判断的方式处理，需要在遍历每一行的时候都判断是否是前面所有已放置皇后的攻击范围，首先这个处理方式就需要增加一层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 -*-


from typing import List


class Solution1:
    """
    """
    def solveNQueens1(self, n: int) -> List[List[str]]:

        def dfs(cols, left_slash, right_slash):
            """
            横向范围不用考虑，因为每次遍历一行只处理一个皇后
            cols存放列的攻击范围的索引值，也是Q的列索引值
            left_slash存放左斜线攻击范围常数值c=y+x
            right_slash存放右斜线攻击范围常数值c=y-x
            """
            l_cols = len(cols)
            if l_cols == n:      # 递归结束条件：遍历完成c次，索引值到n时
                result.append(cols)
                return None
            for i in range(n):  # 遍历n行
                # 排除列攻击范围的索引值、左斜线和右斜线攻击范围的常数值，剩余的就是可以放置Q的位置
                if i not in cols and (l_cols + i) not in left_slash and (l_cols - i) not in right_slash:
                    dfs(cols + [i], left_slash + [l_cols + i], right_slash + [l_cols - i])

        result = []
        dfs([], [], [])
        return [["."*i + "Q" + "."*(n-1-i) for i in sol] for sol in result]


if __name__ == '__main__':
    s = Solution1()
    print(s.solveNQueens1(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皇后问题的最优解法，这种解决方式的记录和解析将会在下一节的时候补充进来