Sponsored
Sponsored
This approach involves using backtracking to explore all possible ways of placing queens on the board. We maintain three sets to keep track of which columns and diagonals are already occupied by queens, ensuring no two queens threaten each other.
Time Complexity: O(n!), where n is the number of queens. Each queen has n options initially, and it decreases with increasing constraints.
Space Complexity: O(n) for the call stack and additional space for tracking columns and diagonals.
1var totalNQueens = function(n) {
2 let cols = new Set();
3 let diag1 = new Set();
4 let diag2 = new Set();
5
6 const backtrack = (row) => {
7 if (row === n) return 1;
8 let count = 0;
9 for (let col = 0; col < n; col++) {
10 if (cols.has(col) || diag1.has(row + col) || diag2.has(row - col)) continue;
11 cols.add(col);
12 diag1.add(row + col);
13 diag2.add(row - col);
14 count += backtrack(row + 1);
15 cols.delete(col);
16 diag1.delete(row + col);
17 diag2.delete(row - col);
18 }
19 return count;
20 };
21
22 return backtrack(0);
23};In JavaScript, we use Set objects to track column and diagonal attacks. The core is a recursive `backtrack` function that tries placing a queen at each row and validates against occupied positions via the sets.
This approach leverages bitmasking to store state information about occupied columns and diagonals. By using integer variables as bit masks, we can efficiently check and update occupation states, which is particularly useful for handling small fixed-size constraints like n <= 9.
Time Complexity: O(n!). Recursive full exploration, though bitwise operations are computationally efficient.
Space Complexity: O(n) due to recursion depth and bitmask integers.
1 public int TotalNQueens(int n) {
return Solve(n, 0, 0, 0, 0);
}
private int Solve(int n, int row, int columns, int diag1, int diag2) {
if (row == n) return 1;
int count = 0;
for (int col = 0; col < n; col++) {
int colMask = 1 << col;
if ((columns & colMask) == 0 && (diag1 & (1 << (row + col))) == 0 && (diag2 & (1 << (row - col + n - 1))) == 0) {
count += Solve(n, row + 1, columns | colMask, diag1 | (1 << (row + col)), diag2 | (1 << (row - col + n - 1)));
}
}
return count;
}
}This C# version employs bitwise operations similarly, adeptly balancing checks on column and diagonal occupation with quick updates achieved through bit shifts.