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..”] ]
经典的N后问题，深搜 这里面有几个问题的处理条件需要注意： 1、如何记录中间结果？ 一开始我所想是用一个vector< string> &temp,来维护一个类似于二维数组，每次对step行填充皇后，并保证noConflict。 也即
if(noConflict()){ temp[i][j]='Q'; dfs(.... temp[i][j]='.'; }不过看了参考答案发现他是用一个vector< int> &temp这个一维数组来完成的，temp[i]表示在i行的temp[i]位置放置皇后。 这种的辅助空间自然也就小了很多，等n行填满之后，只需要将整个棋盘复原出来 2、判断对角线冲突 abs(i-x)==abs(temp[i]-y) 即x1-x2,y1-y2的绝对值不相等。
class Solution { public: int n; vector<vector<string>> solveNQueens(int n) { vector<vector<string> > result; vector<int> temp(n,-1);//表示第i行皇后所在的位置编号 this->n=n; dfs(temp,0,result); return result; } void dfs(vector<int> &temp,int step,vector<vector<string> > &result){ if(step==n){ //将temp转化为字符串 vector<string> answer; for(int i=0;i<n;i++) { string s(n,'.'); for(int j=0;j<s.size();j++){ if(temp[i]==j) s[j]='Q'; } answer.push_back(s); } result.push_back(answer); return; } //尝试在i处放棋子 for(int i=0;i<n;i++){ //在这个位置放没有冲突 if(noConflict(step,i,temp)){ temp[step]=i; dfs(temp,step+1,result); temp[step]=-1; } } } //检测在x,y处放皇后不会冲突 bool noConflict(int x,int y,vector<int> &temp){ for(int i=0;i<x;i++){ //在同一列 if(temp[i]==y) return false; //在同一对角线 if(abs(i-x)==abs(temp[i]-y)) return false; } return true; } };N-Queens II 就没什么好说的了，稍微改改代码就能过，计算一个总的total就好了，找到解了也不需要存入result，直接total++
