52. N-Queens II
1. Description
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
2. Example
Example 1
Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.
Example 2
Input: n = 1
Output: 1
3. Constraints
- 1 <= n <= 9
4. Solutions
Backtracking
n = board_size
Time complexity : O(n!)
Space complexity : O(n)
class Solution {
public:
int totalNQueens(int n) {
int columns = 0, first_diagonals = 0, second_diagonals = 0;
int count = 0;
fill_queens(n, 0, columns, first_diagonals, second_diagonals, count);
return count;
}
private:
void fill_queens(
const int n,
int row,
int columns,
int first_diagonals,
int second_diagonals,
int &count) {
if (row == n) {
++count;
} else {
for (int i = 0; i < n; ++i) {
if ((columns & (1 << i)) == 0 && (first_diagonals & (1 << 9 + row - i)) == 0 &&
(second_diagonals & (1 << row + i)) == 0) {
fill_queens(
n,
row + 1,
columns | 1 << i,
first_diagonals | 1 << (9 + row - i),
second_diagonals | 1 << (row + i),
count);
}
}
}
}
};