class Solution { public: vector<vector<string>> result; int N;// 皇后的个数 int *X;// 当前解 long sum; vector<vector<string>> solveNQueens(int n) { //Queen X; //初始化X N=n; sum=0; int *p=new int[n+1]; for(int i=0;i<=N;i++) p[i]=0; X=p; Backtrack(1); delete []p; return result; }; bool Place(int k){ for(int i=1;i<k;i++){ if((abs(k-i)==abs(X[i]-X[k])) || (X[i]==X[k])) return false; } return true; }; void Backtrack(int t){ if(t>N){ sum++; auto str=vector<string>(); for(int i=N;i>=1;i--) { string temp=string(N,'.'); temp[X[i]-1]='Q'; str.push_back(temp); } result.push_back(str); //result[sum-1]=str; } else{ for(int i=1;i<=N;i++){ X[t]=i; if(Place(t)) Backtrack(t+1); } } } };
