LeetCode-52-N皇后Ⅱ

题目

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

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

示例 1：

img

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

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 9

题解

首先要知道皇后怎么攻击吧？皇后可以攻击同一行、同一列以及同一斜线上的棋子。

那么题目就是要求任意两个棋子不能放在同一行、列以及斜线上。

参考：

52. N 皇后 II - 力扣（LeetCode）

class Solution {
    private int ans = 0;

    public int totalNQueens(int n) {
        dfs(n, 0, 0, 0, 0);
        return this.ans;
    }

    private void dfs(int n, int row, int cols, int pie, int na) {
        if (row == n) {
            this.ans++;
            return;
        }
        // 将所有能放置 Q 的位置由 0 变成 1，以便进行后续的位遍历
        int positions = ((1 << n) - 1) & (~(cols | pie | na));
        while (positions != 0) {
            int p = positions & (-positions);
            positions &= (positions - 1);
            dfs(n, row + 1, cols | p, (pie | p) << 1, (na | p) >> 1);
        }
    }
}