N 皇后 II[困难]

一、题目

n皇后问题研究的是如何将n个皇后放置在n × n的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数n，返回n皇后问题不同的解决方案的数量。

示例 1：

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

示例 2：
输入：n = 1
输出：1

1 <= n <= 9

二、代码

皇后的走法是：可以横直斜走，格数不限。因此要求皇后彼此之间不能相互攻击，等价于要求任何两个皇后都不能在同一行、同一列以及同一条斜线上。直观的做法是暴力枚举将N个皇后放置在N×N的棋盘上的所有可能的情况，并对每一种情况判断是否满足皇后彼此之间不相互攻击。暴力枚举的时间复杂度是非常高的，因此必须利用限制条件加以优化。显然，每个皇后必须位于不同行和不同列，因此将N个皇后放置在N×N的棋盘上，一定是每一行有且仅有一个皇后，每一列有且仅有一个皇后，且任何两个皇后都不能在同一条斜线上。基于上述发现，可以通过回溯的方式得到可能的解的数量。

回溯的具体做法是：依次在每一行放置一个皇后，每次新放置的皇后都不能和已经放置的皇后之间有攻击，即新放置的皇后不能和任何一个已经放置的皇后在同一列以及同一条斜线上。当N个皇后都放置完毕，则找到一个可能的解，将可能的解的数量加1。

由于每个皇后必须位于不同列，因此已经放置的皇后所在的列不能放置别的皇后。第一个皇后有N列可以选择，第二个皇后最多有N−1列可以选择，第三个皇后最多有N−2列可以选择（如果考虑到不能在同一条斜线上，可能的选择数量更少），因此所有可能的情况不会超过N!种，遍历这些情况的时间复杂度是O(N!)。为了降低总时间复杂度，每次放置皇后时需要快速判断每个位置是否可以放置皇后，显然，最理想的情况是在O(1)的时间内判断该位置所在的列和两条斜线上是否已经有皇后。

以下两种方法分别使用集合和位运算对皇后的放置位置进行判断，都可以在O(1)的时间内判断一个位置是否可以放置皇后，算法的总时间复杂度都是O(N!)。

【1】基于集合的回溯： 为了判断一个位置所在的列和两条斜线上是否已经有皇后，使用三个集合columns、diagonals1和diagonals2分别记录每一列以及两个方向的每条斜线上是否有皇后。列的表示法很直观，一共有N列，每一列的下标范围从0到N−1，使用列的下标即可明确表示每一列。如何表示两个方向的斜线呢？对于每个方向的斜线，需要找到斜线上的每个位置的行下标与列下标之间的关系。

方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如(0,0)和(3,3)在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。
方向二的斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，例如(3,0)和(1,2)在同一条方向二的斜线上。因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。

每次放置皇后时，对于每个位置判断其是否在三个集合中，如果三个集合都不包含当前位置，则当前位置是可以放置皇后的位置。

class Solution {
    public int totalNQueens(int n) {
        Set<Integer> columns = new HashSet<Integer>();
        Set<Integer> diagonals1 = new HashSet<Integer>();
        Set<Integer> diagonals2 = new HashSet<Integer>();
        return backtrack(n, 0, columns, diagonals1, diagonals2);
    }

    public int backtrack(int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if (row == n) {
            return 1;
        } else {
            int count = 0;
            for (int i = 0; i < n; i++) {
                if (columns.contains(i)) {
                    continue;
                }
                int diagonal1 = row - i;
                if (diagonals1.contains(diagonal1)) {
                    continue;
                }
                int diagonal2 = row + i;
                if (diagonals2.contains(diagonal2)) {
                    continue;
                }
                columns.add(i);
                diagonals1.add(diagonal1);
                diagonals2.add(diagonal2);
                count += backtrack(n, row + 1, columns, diagonals1, diagonals2);
                columns.remove(i);
                diagonals1.remove(diagonal1);
                diagonals2.remove(diagonal2);
            }
            return count;
        }
    }
}

时间复杂度： O(N!)，其中N是皇后数量。
空间复杂度： O(N)，其中N是皇后数量。空间复杂度主要取决于递归调用层数以及三个集合，递归调用层数不会超过N，每个集合的元素个数都不会超过N。

【2】基于位运算的回溯： 方法一使用三个集合记录分别记录每一列以及两个方向的每条斜线上是否有皇后，每个集合最多包含N个元素，因此集合的空间复杂度是O(N)。如果利用位运算记录皇后的信息，就可以将记录皇后信息的空间复杂度从O(N)降到O(1)。

具体做法是，使用三个整数columns、diagonals1和diagonals2分别记录每一列以及两个方向的每条斜线上是否有皇后，每个整数有N个二进制位。棋盘的每一列对应每个整数的二进制表示中的一个数位，其中棋盘的最左列对应每个整数的最低二进制位，最右列对应每个整数的最高二进制位。如果要在下一行放置皇后，哪些位置不能放置呢？我们用0代表可以放置皇后的位置，1代表不能放置皇后的位置。新放置的皇后不能和任何一个已经放置的皇后在同一列，因此不能放置在第2列和第4列，对应columns=00010100(2)。

新放置的皇后不能和任何一个已经放置的皇后在同一条方向一（从左上到右下方向）的斜线上，因此不能放置在第4列和第5列，对应diagonals1=00110000(2)。其中，第4列为其前两行的第2列的皇后往右下移动两步的位置，第5列为其前一行的第4列的皇后往右下移动一步的位置。新放置的皇后不能和任何一个已经放置的皇后在同一条方向二（从右上到左下方向）的斜线上，因此不能放置在第0列和第3列，对应diagonals2=00001001(2)。其中，第0列为其前两行的第2列的皇后往左下移动两步的位置，第3列为其前一行的第4列的皇后往左下移动一步的位置。

由此可以得到三个整数的计算方法：
1、初始时，三个整数的值都等于0，表示没有放置任何皇后；
2、在当前行放置皇后，如果皇后放置在第i列，则将三个整数的第i个二进制位（指从低到高的第i个二进制位）的值设为1；
3、进入下一行时，columns的值保持不变，diagonals1左移一位，diagonals2右移一位，由于棋盘的最左列对应每个整数的最低二进制位，即每个整数的最右二进制位，因此对整数的移位操作方向和对棋盘的移位操作方向相反（对棋盘的移位操作方向是diagonals1右移一位，diagonals2左移一位）。

每次放置皇后时，三个整数的按位或运算的结果即为不能放置皇后的位置，其余位置即为可以放置皇后的位置。可以通过(2n−1) & (∼(columns∣diagonals1∣diagonals2))得到可以放置皇后的位置（该结果的值为1的位置表示可以放置皇后的位置），然后遍历这些位置，尝试放置皇后并得到可能的解。

遍历可以放置皇后的位置时，可以利用以下两个按位与运算的性质：
1、x & (−x)可以获得x的二进制表示中的最低位的1的位置；
2、x & (x−1)可以将x的二进制表示中的最低位的1置成0。

具体做法是，每次获得可以放置皇后的位置中的最低位，并将该位的值置成0，尝试在该位置放置皇后。这样即可遍历每个可以放置皇后的位置。

class Solution {
    public int totalNQueens(int n) {
        return solve(n, 0, 0, 0, 0);
    }

    public int solve(int n, int row, int columns, int diagonals1, int diagonals2) {
        if (row == n) {
            return 1;
        } else {
            int count = 0;
            int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
            while (availablePositions != 0) {
                int position = availablePositions & (-availablePositions);
                availablePositions = availablePositions & (availablePositions - 1);
                count += solve(n, row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
            }
            return count;
        }
    }
}