🚩传送门：牛客题目
力扣题目

题目

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

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

示例 1：
[NC]39. N皇后问题 - 图1

输入：n = 4 输出：2 解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1 输出：1

解题思路：回溯

为判断一个位置所在的列和两条斜线上是否已有皇后，使用三个集合 [NC]39. N皇后问题 - 图2、[NC]39. N皇后问题 - 图3、
[NC]39. N皇后问题 - 图4 分别记录每一列以及两个方向的每条斜线上是否有皇后。

列的表示法很直观，一共有 [NC]39. N皇后问题 - 图5 列，使用列的下标即可明确表示每一列。

如何表示两个方向的斜线呢？
对于每个方向的斜线，需要找到斜线上的每个位置的行下标与列下标之间的关系。

  1. 斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等

[NC]39. N皇后问题 - 图6

  1. 斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等

[NC]39. N皇后问题 - 图7
每次放置皇后时，对于每个位置判断其是否在三个集合中，如果三个集合都不包含当前位置，则当前位置是可以放置皇后的位置。

复杂度分析

时间复杂度： [NC]39. N皇后问题 - 图8 ，其中 [NC]39. N皇后问题 - 图9 是皇后数量。

空间复杂度：[NC]39. N皇后问题 - 图10 ，其中 [NC]39. N皇后问题 - 图11 是皇后数量。

  1.   - 递归调用层数不会超过 ![](https://cdn.nlark.com/yuque/__latex/459f3c80a50b7be28751b0869ef5386a.svg#card=math&code=N&id=JyQaf) ，每个集合的元素个数都不会超过 ![](https://cdn.nlark.com/yuque/__latex/459f3c80a50b7be28751b0869ef5386a.svg#card=math&code=N&id=hytpk) 。

我的代码

  1. public class Solution {
  3.     public int DFS(int n,int CurRows,HashSet<Integer> columns,
  4.                    HashSet<Integer> diagonals1,HashSet<Integer> diagonals2){
  5.         // 递归到达最底层
  6.         if(CurRows==n){
  7.             return 1;
  8.         }
  9.         int ReturnCount=0;
  10.         // 当前CurRows行循环n列
  11.         for(int i=0;i<n;i++){
  12.             // 检查当前列是否被其他皇后占领
  13.             if(columns.contains(i)) continue;
  14.             int diagonals1Num = i-CurRows;    // 计算右斜号
  15.             // 检查当前右斜是否被其他皇后占领
  16.             if(diagonals1.contains(diagonals1Num)) continue;
  17.             int diagonals2Num = i+CurRows;    // 计算左斜号
  18.             if(diagonals2.contains(diagonals2Num)) continue;
  19.             // 如果此时还没有被 continue 说明此位置可以将其占领
  20.             columns.add(i);                   // 占领当前列
  21.             diagonals1.add(diagonals1Num);    // 占领右斜
  22.             diagonals2.add(diagonals2Num);    // 占领左斜
  23.             // 递归下一行进行计算
  24.             ReturnCount+=DFS(n,CurRows+1,columns,diagonals1,diagonals2);
  25.             // 将当前占领的列，左右斜资源释放
  26.             columns.remove(i);
  27.             diagonals1.remove(diagonals1Num);
  28.             diagonals2.remove(diagonals2Num);
  29.             // 开始循环尝试占领当前行的下一列
  30.         }
  31.         return ReturnCount;
  32.     }
  33.     public int Nqueen (int n) {
  34.         // write code here
  35.         HashSet<Integer> columns=new HashSet<>();
  36.         HashSet<Integer> diagonals1=new HashSet<>();
  37.         HashSet<Integer> diagonals2=new HashSet<>();
  38.         return DFS(n,0,columns,diagonals1,diagonals2);
  40.     }
  41. }