NQueens问题
N-Queens I
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
For example, There exist two distinct solutions to the 4-queens puzzle:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
代码
class Solution {
private:
vector<vector<string>> res;
public:
vector<vector<string>> solveNQueens(int n) {
vector<int> colOfRaw(n,-1);
solver(colOfRaw, 0);
return res;
}
void solver(vector<int> &colOfRow,int row){
int n = (int)colOfRow.size();
if(n == row){
vector<string> temp(n,string(n,'.'));
for(int i = 0;i<n;i++){
temp[i][colOfRow[i]] = 'Q';
}
res.push_back(temp);
return;
}
else{
for(int col = 0;col<n;col++){
if(isValid(colOfRow, row, col)){
colOfRow[row] = col;
solver(colOfRow, row+1);
colOfRow[row] = -1;
}
}
}
}
bool isValid(vector<int> &colOfRow,int row,int col){
for(int i = 0;i < row;i++){
if(col == colOfRow[i] || abs(col - colOfRow[i]) == abs(row-i))
return false;
}
return true;
}
};
N-Queens II
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
代码
class Solution {
private:
int res;
public:
int totalNQueens(int n) {
res = 0;
vector<int> colOfRaw(n,-1);
solver(colOfRaw, 0);
return res;
}
void solver(vector<int> &colOfRow,int row){
int n = (int)colOfRow.size();
if(n == row){
res++;
return;
}
else{
for(int col = 0;col<n;col++){
if(isValid(colOfRow, row, col)){
colOfRow[row] = col;
solver(colOfRow, row+1);
colOfRow[row] = -1;
}
}
}
}
bool isValid(vector<int> &colOfRow,int row,int col){
for(int i = 0;i < row;i++){
if(col == colOfRow[i] || abs(col - colOfRow[i]) == abs(row-i))
return false;
}
return true;
}
};
