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.
1class Solution:
2 def totalNQueens(self, n: int) -> int:
3 def backtrack(row = 0):
4 if row == n:
5 return 1
6 count = 0
7 for col in range(n):
8 if col in cols or (row + col) in diag1 or (row - col) in diag2:
9 continue
10 cols.add(col)
11 diag1.add(row + col)
12 diag2.add(row - col)
13 count += backtrack(row + 1)
14 cols.remove(col)
15 diag1.remove(row + col)
16 diag2.remove(row - col)
17 return count
18
19 cols = set()
20 diag1 = set()
21 diag2 = set()
22 return backtrack()The Python approach uses sets for columns and diagonals to check availability and recursively attempts to place queens one row at a time. It handles constraints by dynamically updating and rolling back changes in 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
The C implementation utilizes bitmasking for columns and diagonals, enabling efficient checking and updating of states. The code iterates over possible columns, shifting bit positions to represent occupation and recursively exploring valid paths.