N-Queens
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.."]
]
思路： 简单题。全排列。（注意各行各列不同可以直接确定住）
void getSolution(veor<int> &r, vector<vector<string> > &vec) {
int n = r.size();
vector<string> vec2;
for(int i = 0; i < n; ++i) {
vec2.push_back(string(n, '.'));
vec2[i][r[i]] = 'Q';
}
vec.push_back(vec2);
}
bool judge(vector<int> &r) {
for(size_t i = 0; i < r.size(); ++i)
for(size_t j = i+1; j < r.size(); ++j)
if(j-i == r[j]-r[i] || j-i == r[i]-r[j])
return false;
return true;
}
void getPosition(int cur, vector<int> &r, vector<vector<string> > &vec) {
if(cur == r.size()) {
if(judge(r))
getSolution(r, vec);
return;
}
for(int e = cur; e < r.size(); ++e) {
int t = r[cur];
r[cur] = r[e];
r[e] = t;
getPosition(cur+1, r, vec);
r[e] = r[cur];
r[cur] = t;
}
}
class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
vector<vector<string> > vec;
if(n <= 0) return vec;
vector<int> r(n);
for(int i = 0; i < n; ++i) r[i] = i;
getPosition(0, r, vec);
return vec;
}
};
N-Queens II
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
思路： 比上题好像更简单一些。
bool judge(vector<int> &r) {
for(size_t i = 0; i < r.size(); ++i)
for(size_t j = i+1; j < r.size(); ++j)
if(j-i == r[j]-r[i] || j-i == r[i]-r[j])
return false;
return true;
}
void getPosition(int cur, vector<int> &r, int &cnt) {
if(cur == r.size()) {
if(judge(r))
++cnt;
return;
}
for(int e = cur; e < r.size(); ++e) {
int t = r[cur];
r[cur] = r[e];
r[e] = t;
getPosition(cur+1, r, cnt);
r[e] = r[cur];
r[cur] = t;
}
}
class Solution {
public:
int totalNQueens(int n) {
if(n <= 0) return 0;
int cnt = 0;
vector<int> r(n);
for(int i = 0; i < n; ++i) r[i] = i;
getPosition(0, r, cnt);
return cnt;
}
};
可参考剑指 offer:题28