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 board_size) {
board_size_ = board_size;
vector<string> board(board_size, string(board_size, '.'));
vector<bool> use_column(board_size);
vector<bool> use_lrdiagonal(board_size + board_size - 1);
vector<bool> use_rldiagonal(board_size + board_size - 1);
int result = 0;
solve_(board, 0, use_column, use_lrdiagonal, use_rldiagonal, result);
return result;
}
private:
int board_size_;
void solve_(
vector<string> &board,
int line,
vector<bool> &use_column,
vector<bool> &use_lrdiagonal,
vector<bool> &use_rldiagonal,
int &result) {
if (line == board_size_) {
++result;
} else {
for (int i = 0; i < board_size_; ++i) {
if (!use_column[i] && !use_lrdiagonal[line - i + board_size_ - 1] &&
!use_rldiagonal[line + i]) {
use_column[i] = use_lrdiagonal[line - i + board_size_ - 1] =
use_rldiagonal[line + i] = true;
board[line][i] = 'Q';
solve_(board, line + 1, use_column, use_lrdiagonal, use_rldiagonal, result);
board[line][i] = '.';
use_column[i] = use_lrdiagonal[line - i + board_size_ - 1] =
use_rldiagonal[line + i] = false;
}
}
}
}
};