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.
1#include <stdbool.h>
2#include <stdlib.h>
3
4int totalNQueens(int n) {
5 int count = 0;
6 bool *columns = calloc(n, sizeof(bool));
7 bool *diag1 = calloc(2 * n, sizeof(bool));
8 bool *diag2 = calloc(2 * n, sizeof(bool));
9 solve(0, n, columns, diag1, diag2, &count);
10 free(columns);
11 free(diag1);
12 free(diag2);
13 return count;
14}
15
16void solve(int row, int n, bool *columns, bool *diag1, bool *diag2, int *count) {
17 if (row == n) {
18 (*count)++;
19 return;
20 }
21 for (int col = 0; col < n; col++) {
22 if (!columns[col] && !diag1[row + col] && !diag2[row - col + n]) {
23 columns[col] = diag1[row + col] = diag2[row - col + n] = true;
24 solve(row + 1, n, columns, diag1, diag2, count);
25 columns[col] = diag1[row + col] = diag2[row - col + n] = false;
26 }
27 }
28}This C implementation uses arrays (`columns`, `diag1`, and `diag2`) to mark the columns and diagonals that are occupied. The function recursively attempts to place a queen in each row and calls itself for the next row if successful. The base case is when all queens are placed (`row == n`), at which point we increment the solution count.
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
JavaScript benefits from using bitmasking to handle calculations for columns and diagonals, significantly boosting performance when transitioning through potential queen placements.