52. N-Queens II
n 皇后問題是在 n x n 棋盤上放置 n 個皇后，使得任何兩個皇后之間都不能互相攻擊的問題。
給定一個整數 n，返回 n 皇后問題的不同解法數量。
範例 1：
輸入：n = 4 輸出：2 解釋：4 皇后問題有兩個不同的解法，如圖所示。
Python
class Solution:
def totalNQueens(self, n: int) -> int:
def backtrack(row: int):
if row == n:
self.count += 1
return
for col in range(n):
if col in cols or (row - col) in pos_diags or (row + col) in neg_diags:
continue
# Place the queen
cols.add(col)
pos_diags.add(row - col)
neg_diags.add(row + col)
# Move to the next row
backtrack(row + 1)
# Remove the queen and backtrack
cols.remove(col)
pos_diags.remove(row - col)
neg_diags.remove(row + col)
self.count = 0
cols = set()
pos_diags = set()
neg_diags = set()
backtrack(0)
return self.count
16.30MB, 40ms
C++
#include <vector>
#include <unordered_set>
using namespace std;
class Solution {
public:
int totalNQueens(int n) {
count = 0;
cols.clear();
posDiags.clear();
negDiags.clear();
backtrack(0, n);
return count;
}
private:
int count;
unordered_set<int> cols;
unordered_set<int> posDiags;
unordered_set<int> negDiags;
void backtrack(int row, int n) {
if (row == n) {
count++;
return;
}
for (int col = 0; col < n; ++col) {
if (cols.find(col) != cols.end() || posDiags.find(row - col)
!= posDiags.end() || negDiags.find(row + col) != negDiags.end()) {
continue;
}
// Place the queen
cols.insert(col);
posDiags.insert(row - col);
negDiags.insert(row + col);
// Move to the next row
backtrack(row + 1, n);
// Remove the queen and backtrack
cols.erase(col);
posDiags.erase(row - col);
negDiags.erase(row + col);
}
}
};
Javascript
/**
* @param {number} n
* @return {number}
*/
var totalNQueens = function(n) {
let count = 0;
const cols = new Set();
const posDiags = new Set();
const negDiags = new Set();
const backtrack = (row) => {
if (row === n) {
count++;
return;
}
for (let col = 0; col < n; col++) {
if (cols.has(col) || posDiags.has(row - col) || negDiags.has(row + col)) {
continue;
}
// Place the queen
cols.add(col);
posDiags.add(row - col);
negDiags.add(row + col);
// Move to the next row
backtrack(row + 1);
// Remove the queen and backtrack
cols.delete(col);
posDiags.delete(row - col);
negDiags.delete(row + col);
}
};
backtrack(0);
return count;
};
51.2MB, 65ms
