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.."] ]
思路：八皇后是一个非常典型的DFS的例子。可用pos表示位于第pos行的皇后，used[i]=false表示第i列未被前pos-1个皇后占领。如果在(pos,i)设置一个皇后，需要判断左上和右上的皇后与(pos,i)是否在同一条线上，如果是则放弃(pos,i)位置，遍历(pos,i+1)的位置。
class Solution {
private:
vector<vector<string> > res;
vector<bool> used;
vector<vector<bool> > queen;
public:
vector<string> queenToString(vector<vector<bool> > Q,int n)
{
vector<string> aa;
int i,j;
for(i=0; i<n; ++i)
{
string str = "";
for(j=0; j<n; ++j)
{
if (Q[i][j])
{
str += 'Q';
}
else
{
str += '.';
}
}
aa.push_back(str);
}
return aa;
}
bool isAdj(int row, int col)
{
int n = queen.size();
int i,j;
i = row-1, j = col - 1;
while(i>=0 && j>=0)
{
if (queen[i][j])
{
return true;
}
i--,j--;
}
i = row - 1, j = col + 1;
while(i>=0 && j<n)
{
if (queen[i][j])
{
return true;
}
i--,j++;
}
return false;
}
void solveNQueensHelper(int pos,int n)
{
if (pos == n)
{
res.push_back(queenToString(queen,n));
return;
}
int i;
for(i=0; i<n; ++i)
{
if (!used[i] && !isAdj(pos,i))
{
used[i] = true;
queen[pos][i] = true;
solveNQueensHelper(pos+1,n);
used[i] = false;
queen[pos][i] = false;
}
}
}
vector<vector<string> > solveNQueens(int n) {
used.clear();
queen.clear();
res.clear();
if (n <= 0)
{
return res;
}
used.resize(n);
queen.resize(n);
int i,j;
for(i=0; i<n; ++i)
{
used[i] = false;
queen[i].resize(n);
for(j=0; j<n; ++j)
{
queen[i][j] = false;
}
}
solveNQueensHelper(0,n);
return res;
}
};
现在又尝试了一遍
class Solution {
vector<vector<string> > res;
vector<vector<bool> >used;
public:
int ABS(int a) {
return a>=0 ? a : (-1*a);
}
bool isAdj(int i, int n, int pos) {
int k,j;
for (k=0; k<pos; ++k) {
if (used[k][i]) { //同一列
return true;
}
for (j=0; j<n; ++j) { //同一对角线
if (ABS(k-pos)==ABS(j-i) && used[k][j]) {
return true;
}
}
}
return false;
}
vector<string> bool2str(vector<vector<bool> > &used) {
vector<string> res;
res.resize(used.size());
int i,j;
for (i=0; i<used.size(); ++i) {
res[i].resize(used[i].size());
for (j=0; j<used[i].size(); ++j) {
if (used[i][j]) {
res[i][j] = 'Q';
}
else {
res[i][j] = '.';
}
}
}
return res;
}
void helperFunc(int pos, int n, vector<vector<bool> > &used) {
if (pos == n) {
res.push_back(bool2str(used));
return;
}
int i;
for (i=0; i<n; ++i) {
if (!isAdj(i, n, pos)) {
used[pos][i] = true;
helperFunc(pos+1, n, used);
used[pos][i] = false;
}
}
}
vector<vector<string> > solveNQueens(int n) {
int i,j;
int pos = 0;
used.resize(n);
for (i=0; i<n; ++i) {
used[i].resize(n);
for (j=0; j<n; ++j) {
used[i][j] = false;
}
}
for (i=0; i<n; ++i) {
used[pos][i] = true;
helperFunc(pos+1, n, used);
used[pos][i] = false;
}
return res;
}
};