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.."]
]
分析： The classic recursive problem.
1. Use a int vector to store the current state, A[i]=j refers that the ith row and jth column is placed a queen.
2. Valid state: not in the same column, which is A[i]!=A[current], not in the same diagonal direction: abs(A[i]-A[current]) != r-i
3. Recursion:
Start: placeQueen(0,n)
if current ==n then print result
else
for each place less than n,
place queen
if current state is valid, then place next queen place Queen(cur+1,n)
end for
end if
class Solution {
public:
void record(vector<int> row)
{
vector<string> temp;
for(int i = ; i< n ; i++)
{
string str(n,'.');
str[row[i]] = 'Q';
temp.push_back(str);
}
res.push_back(temp) ;
}
bool isValid(vector<int> row, int curRow)
{
for(int i = ; i< curRow; i++)
if(row[i] == row[curRow] || abs(row[i] - row[curRow]) == curRow - i)
return false;
return true;
}
void nqueue(vector<int> row,int curRow)
{
if(curRow == n)
{
record(row);
return ;
}
for(int i = ; i< n ;i++)
{
row[curRow] = i;
if(isValid(row,curRow))
nqueue(row,curRow+);
}
}
vector<vector<string> > solveNQueens(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
res.clear();
if( n < ) return res;
this->n = n;
vector<int> row(n,-);
nqueue(row, );
return res;
}
private:
int n;
vector<vector<string> > res;
};
http://yucoding.blogspot.com/2013/01/leetcode-question-59-n-queens.html