51. N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

 【解决思路】DFS加回溯

在每一行中先确定第一个元素位置，然后到第二行找一个位置，以此类推，直到在当前行无法找到一个合适的位置就进行回溯，或者在最后一行找到了一个合适位置那么就将结果进行保存。

看下方代码，下面这个代码完全就是套用了DFS这块的模板代码。

    vector> temp;vector>> res;void dfs(int n, int row){if(row==n){    // 如果到了最后一行加一的位置就停止并将这一组数据放入res.push_back(temp);}for(int col = 0; col < n; ++col){if(isvalied(row, col)){temp.emplace_back(row, col);dfs(n, row+1);temp.pop_back();}}}

 对于当前行皇后位置的判断：

    bool isvalied(int row, int col){for(auto e : temp){// 遍历之前所有的皇后，如果当前行列与之前一个皇后冲突，返回falseif(col == e.second || e.first-e.second==row-col || e.first+e.second==row+col)return false;}return true;}

首先根据我们回溯的过程是一行一行的进行，所以在一行内肯定不会有第二个位置，所以只需要判断一列、和俩个斜线位置有没有之前的皇后。

列的判断只需要对比当前col与之前每一个皇后的列号

而斜线位置的元素都有共同点，

从左上往右下他们的行列号加和相同

从左下往右上他们的行列号差值相同

 

最后就是对结果的整理，需要返回vector>的数组

注意e与i分别代表的元素，e是棋盘结果集合中每一个棋盘结果，而i是每一个棋盘中皇后的位置键值对。使用Result保存结果，然后使用一个临时vector数组存放每一个棋盘，使用键值对str_temp[i.first][i.second] = 'Q';来对每一个皇后位置进行更新为'Q'之后将这个临时string类型数组存入Result中，当把所有的棋盘结果遍历完成之后，就可以返回Result。

    vector> transeResult(int n){vector> Result;for(auto e : res){vector str_temp(n, string(n, '.'));for(auto i : e){str_temp[i.first][i.second] = 'Q';}Result.push_back(str_temp);}return Result;}

源码：

class Solution {
public:vector> temp;    // 存放当前所有皇后位置vector>> res; // 存放所有满足条件的棋盘结果void dfs(int n, int row){if(row==n){   // 当遍历到最后一行的下一个位置res.push_back(temp);}for(int col = 0; col < n; ++col){if(isvalied(row, col)) // 当前列满足条件，才会放入temp中{temp.emplace_back(row, col);dfs(n, row+1); // 确定好这一行位置后，处理下一行位置temp.pop_back();    // 回溯，比如 最后一行第一列访问结束，开始访问最后一行第二列位置。}}}bool isvalied(int row, int col){for(auto e : temp){   //列号与之前皇后冲突、行列之差与之前皇后相等、行列之和与之前皇后相等// 遍历之前所有的皇后，如果当前行列与之前一个皇后冲突，返回falseif(col == e.second || e.first-e.second==row-col || e.first+e.second==row+col)return false;}return true;}vector> transeResult(int n){vector> Result;  // 返回结果for(auto e : res)       // 对于res中没一组皇后位置{vector str_temp(n, string(n, '.')); // 创建一个棋盘，并用当前皇后位置组数据初始化皇后位置。for(auto i : e){str_temp[i.first][i.second] = 'Q';}Result.push_back(str_temp);}return Result;}vector> solveNQueens(int n) {dfs(n, 0);return transeResult(n);}
};