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:
分析： 著名的N皇后问题，可以采用一位数组来代替二维数组，利用回溯，注意皇后行走的条件
class Solution {
public:
bool isOk(int start,int value, const vector<int>& array){
for(int i =start-1; i>=0; i--)
if((array[i]==value) || (abs(array[i]-value)==abs(start-i)))
return false;
if(abs(array[start-1]-value)==1)
return false;
return true;
}
void Queen(int start, vector<int>& array, vector<vector<int>> & res ){
//cout << start <<endl;
if(start == array.size()){
res.push_back(array);
return;
}
for(int i =0; i< array.size(); i++){
if(isOk(start, i, array)){
// cout <<"hello"<<endl;
array[start] =i;
Queen(start+1, array, res);
}
}
return;
}
void convert(const vector<vector<int>> res, vector<vector<string>>& str){
for(vector<int> t: res){
int n = t.size();
vector<string> strlist;
for(int i=0; i<n; i++){
string s(n,'.');
s[t[i]] = 'Q';
strlist.push_back(s);
}
str.push_back(strlist);
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<int>> res;
vector<vector<string>> str;
if(n==0)
return str;
vector<int> array(n,0);
for(int i =0; i< n; i++){
array[0] =i;
Queen(1,array,res);
}
convert(res,str);
return str;
}
};