思路:

从题中给出的有效信息：

  • 任何两个皇后不同行，不同列也不再同一条斜线上，计算n皇后的排列种类

由于此题需要对nxn棋盘中的每个点进行判断，在符合情况的点再进行选择，穷举棋盘是不可避免，故此我们可以使用回溯的方法进行解决此问题

方法一：常用-集合

具体做法：
1.设置三个集合分别记录不能再被选中的的列col，正斜线pos，反斜线neg
2.经规律发现 行号i - 列号j 可确定唯一正斜线，行号i + 列号j 可确定唯一反斜线
3.符合要求的点记录当前点并递归下一个皇后，最后一个皇后成功安置后将res+1，然后需回溯回初始点将初始点删除，将初始点的皇后放置其他位置进行判断
4.不符合要求的需要进行循环

具体过程如下图所示：
图片说明 

import java.util.*;
public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    Set<Integer> column = new HashSet<Integer>(); //标记列不可用
    Set<Integer> posSlant = new HashSet<Integer>();//标记正斜线不可用
    Set<Integer> conSlant = new HashSet<Integer>();//标记反斜线不可用
    int result = 0;

    public int Nqueen (int n) {
        // write code here
        compute(0, n);
        return result;
    }
    private void compute(int i, int n){
        if(i == n){
            result++;
            return;
        }
        for(int j = 0; j < n; j++){
            if(column.contains(j) || posSlant.contains(i - j) || conSlant.contains(i + j)){
                continue;
            }
            column.add(j);//列号j 
            posSlant.add(i - j);//行号i - 列号j 正斜线
            conSlant.add(i + j);//行号i + 列号j 反斜线
            compute(i + 1, n); //计算下一行
            column.remove(j); //完成上一步递归计算后，清除
            posSlant.remove(i - j);
            conSlant.remove(i + j);
        }
    }
}

复杂度分析：

  • 时间复杂度：O(n!) 皇后每次递减，根据全排列可得O(n!)
  • 空间复杂度：O(n) 申请3个set集合

方法二：位运算

具体做法：
1.N个位置对应N个二进制位，0代表无皇后，1代表有皇后
2.例如对于col = 0100对应第二列已有皇后，那么下一行的第一列和第三列都不能选
对应pos = 0010，也就是col右移一位；对应neg = 1000，也就是col左移一位
pre = ~ (col | pos | neg) & ((1 << n) - 1) 代表可以放皇后的位置
~ (col | pos | neg)：col、pos、neg取或运算后0表示可以放皇后的位置，取反后1表示可以放皇后的位置
((1 << n) - 1) ：是为了保证pre不大于n位
3.然后对pre中所有的1进行遍历，从最后一个1开始往前遍历，在当前行放置了一个皇后之后进入下一行，对col、pos、neg做出相应的处理，其余操作与上一个方法相同

import java.util.*;
public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    int res;
    public int Nqueen (int n) {
        // write code here
        backtrack(0, 0, 0, 0, n);
        return res;
    }
    public void backtrack(int i, int col, int pos, int neg, int n){
        if(i == n){
            res++;
            return;
        }
         //标记放皇后的位置
        int pre = ~(col | pos | neg) & ((1 << n) - 1);
        //遍历pre
        while(pre > 0){
            int cur = pre & (-pre);
            //当前行放置了一个皇后之后进入下一行
            backtrack(i + 1, col | cur, (pos | cur) >> 1, (neg | cur) << 1, n);
            pre &= pre - 1;
        }
    }
}

复杂度分析：

  • 时间复杂度：O(n!) n是皇后数量
  • 空间复杂度：O(n) n是皇后数量,递归调用层数不会超过n