Leetcode-51. N皇后

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

上图为 8 皇后问题的一种解法。

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

示例:

输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

本题使用位运算进行速度最快的题解，很难理解，但是速度飞快，先上一下用set题解的代码

class Solution {
   
    public int count = 0;
    public int totalNQueens(int n) {
   
        Set<Integer> left = new HashSet<>();
        Set<Integer> right = new HashSet<>();
        Set<Integer> cols = new HashSet<>();
        List<Integer> tmp = new ArrayList<>();
        this.dfs(0, n, cols, left, right, tmp);
        return this.count;
    }

    public void dfs(int level, int n, Set<Integer> cols, Set<Integer> left, Set<Integer> right, List<Integer> tmp){
   
        if (tmp.size()==n) {
   
            // res.add(tmp); DO NOT ADD TMP DIRECTLY! tmp will change in backtracing! add a copy of tmp!
            this.count++;
            return;
        }
        for (int i=0;i<n;i++) {
   
            if (!cols.contains(i) && !left.contains(level+i) && !right.contains(level-i)) {
   
                cols.add(i);
                left.add(level+i);
                right.add(level-i);
                tmp.add(i);
                this.dfs(level+1, n, cols, left, right, tmp);
                cols.remove(i);
                left.remove(level+i);
                right.remove(level-i);
                tmp.remove(Integer.valueOf(i)); // remove(i) will not remove the i value in tmp ,but will remove the ith value! MARK THAT!
            }
        }
        return ;
    }
}

上一张伪代码的图

首先解释下 x & (-x)，这个的作用是取得最后一位的1的位置，
例如20为10100，-20是补码，也就是取反加一，01011 + 00001 = 01100，10100 & 01100 = 00100，作用确实是取得最后一位1的位置

• Java

class Solution {
   
    public int count;
    public int N;
    public int totalNQueens(int n) {
   
        this.N = n;
        this.dfs(0,0,0,0); // 设0为皇后可以放置的位置，则开始的时候4个位置都能放，0000还是0，所以传入0
        return this.count;
    }
    public void dfs(int level, int col, int pie, int na) {
   
        if (level==this.N) {
   
            this.count++;
            return ;
        }
        int zeroIsGood = ~(col|pie|na);// 列，撇，捺进行或操作，所有为1的位置都会有皇后攻击，因此0的位置是可放皇后的位置，取反变成1为可用的位置便于计算，但是由于取反了，前面有32-n数量的1，要把这32-n数量的1都变成0，需要与操作后n位都是1的数
        int makeN_1 = (int)Math.pow(2,this.N) - 1;
        int bits = zeroIsGood & makeN_1; // 得到包含可用位置信息的数
        while (bits!=0) {
   // 还有能用的位置的时候，要将所有位置的1都进行计算
            int p = bits & (-bits); // 取得包含最后一个1位置的数
            this.dfs(level+1, col|p, (pie|p)<<1, (na|p)>>1); // 下一行中，列要包含这次被占用的位置，撇要包含这个位置向左移动一格的位置，捺要包含这个位置向右移动一格的位置，出界的位置无论是左边还是右边都是用0补上的，而0代表可用，所以莫得问题
            bits = bits & (bits-1); // 消除最后已经被计算过的1，继续计算下一个1
        }
    }
}

• Python

class Solution:
    def totalNQueens(self, n: int) -> int:
        self.N = n
        self.count = 0
        self.dfs(0,0,0,0)
        return self.count
    
    def dfs(self,level, col, pie, na):
        if level==self.N: 
            self.count += 1
            return
        bits = (~(col|pie|na)) & (2**self.N - 1)
        while bits:
            p = bits & (-bits)
            self.dfs(level+1, col|p, (pie|p)<<1, (na|p)>>1)
            bits = bits & (bits-1)