算法
使用二进制来解八皇后问题。
时间复杂度: O(2^n)
空间复杂度: O(n)
C++代码
class Solution {
public:
static int totalNQueens(int n) {
if (n <= 1) {
return n;
}
int count = 0;
totalNQueens(n, 0, 0, 0, 0, count);
return count;
}
private:
static void totalNQueens(int n, int row, int col, int left, int right, int &count) {
if (row == n) {
++count;
return;
}
// 取所有空位
int bits = (~(col | left | right)) & ((1 << n) - 1);
while (bits) {
// 取最低位的1
const int bit = bits & (-bits);
totalNQueens(n, row + 1, col | bit, (left | bit) << 1, (right | bit) >> 1, count);
// 清除最低位的1
bits &= bits - 1;
}
}
};
Java代码
class Solution {
public static int totalNQueens(final int n) {
if (n <= 1) {
return n;
}
final int[] count = {0};
totalNQueens(n, 0, 0, 0, 0, count);
return count[0];
}
private static void totalNQueens(final int n, final int row, final int col,
final int left, final int right, final int[] count) {
if (row == n) {
++count[0];
return;
}
// 取所有空位
int bits = (~(col | left | right)) & ((1 << n) - 1);
while (bits != 0) {
// 取最低位的1
final int bit = bits & (-bits);
totalNQueens(n, row + 1, col | bit, (left | bit) << 1, (right | bit) >> 1, count);
// 清除最低位的1
bits &= bits - 1;
}
}
}
Python3代码
class Solution:
def totalNQueens(self, n: int) -> int:
if n <= 1:
return n
count = [0]
self.__totalNQueens(n, 0, 0, 0, 0, count)
return count[0]
def __totalNQueens(self, n: int, row: int, col: int, left: int, right: int, count: list) -> None:
if row == n:
count[0] += 1
return
# 取所有空位
bits = (~(col | left | right)) & ((1 << n) - 1);
while bits:
# 取最低位的1
bit = bits & (-bits)
self.__totalNQueens(n, row + 1, col | bit, (left | bit) << 1, (right | bit) >> 1, count)
# 清除最低位的1
bits &= bits - 1
感觉很厉害的样子