51. N-Queens
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 all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens' placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively.
2. Example
Example 1:
Input: n = 4
Output: [[".Q..","…Q",“Q…”,"..Q."],["..Q.",“Q…”,"…Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2:
Input: n = 1
Output: [[“Q”]]
3. Constraints
- 1 <= n <= 9
4. Solutions
Backtracking
n = board_size
Time complexity : O(n!)
Space complexity : O(n)
class Solution {
public:
vector<vector<string>> solveNQueens(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);
vector<vector<string>> result;
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,
vector<vector<string>> &result) {
if (line == board_size_) {
result.push_back(board);
} 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;
}
}
}
}
};