1.题目基本信息

1.1.题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

1.2.题目地址

https://leetcode.cn/problems/n-queens/description/

2.解题方法

2.1.解题思路

回溯+哈希表

2.2.解题步骤

第一步，构建维护变量。result维护所有合法的组合数组；combine动态维护当前的各行的列号组合；colsSet,diagonalSet,revDiagonalSet维护combine状态下已经占有的col、row-col、row+col（列、对角线、反对角线）

第二步，构建回溯递归函数。递归任务：在前面各行的列组合为combine的情况下，枚举下一行的合法情况添加到combine中，并进行回溯递归；并将合法的combine组合添加到result数组中

第三步，调用回溯递归，填充result数组，并返回

3.解题代码

Python代码

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # 思路：回溯+哈希表
        # 第一步，构建维护变量。result维护所有合法的组合数组；combine动态维护当前的各行的列号组合；colsSet,diagonalSet,revDiagonalSet维护combine状态下已经占有的col、row-col、row+col（列、对角线、反对角线）
        result = []
        colsSet, diagonalSet, revDiagonalSet = set(), set(), set()
        combine = []
        # 第二步，构建回溯递归函数。递归任务：在前面各行的列组合为combine的情况下，枚举下一行的合法情况添加到combine中，并进行回溯递归；并将合法的combine组合添加到result数组中
        def backtrack() -> None:
            # 2.1.回溯递归出口，构建成了合法的combine组合
            if len(combine) == n:
                # 2.1.1.将合法combine转换成字符串列表的形式加入到result结果数组中
                # print(combine)
                ls = []
                for i in combine:
                    ls.append("." * i + "Q" + "." * (n - i - 1))
                result.append(ls)
                return
            # 2.2.枚举当前加入到combine中的列号
            row = len(combine)
            for col in range(n):
                # 2.2.1.使用列、对角线、反对角线的集合进行剪枝
                if col in colsSet or row - col in diagonalSet or row + col in revDiagonalSet:
                    continue
                # 2.2.2.状态修改
                combine.append(col)
                colsSet.add(col)
                diagonalSet.add(row - col)
                revDiagonalSet.add(row + col)
                # 2.2.3.回溯递归
                backtrack()
                # 2.2.4.状态恢复
                combine.pop()
                colsSet.remove(col)
                diagonalSet.remove(row - col)
                revDiagonalSet.remove(row + col)
        # 第三步，调用回溯递归，填充result数组，并返回
        backtrack()
        return result

4.执行结果