理解回溯后感觉八皇后不过如此

听师兄说，去年面试华为，上来就让手撕八皇后，结果师兄二话不说搞定，直接30W+，慕了！

八皇后问题就是在一个8x8的棋盘上面放置8个棋子，每个棋子的上、下、左、右、左上、左下、右上、右下8个方向不能有其他的皇后。

之前看着一道题的时候，感觉十分麻烦，总感觉细节太多了，然后只知道大的层面用一个dfs（by the way，个人理解，回溯是算法思想，DFS更多是实现工具，最根本的实现方法是递归）

基本思路：
  可以认为的控制一行一行的进行皇后放置，首先在第一行进行放置，然后在第二行进行放置…，最后每一行都放置完了，这一种方案就进行到底了；

问题1：如何将方案存储下来呢？
答：可以采用一个数组，存储下每一行皇后放置的列数，最终将相应位置的‘.’置换为‘Q’

for(int i=0;i<n;++i){
   
	string rowString(n,'.');
	rowString[columnValue[i]]='Q';
	solutionString.push_back(rowString);
}

问题2：如何判断一个位置是否可以放置皇后？
答：可以采用坐标的判断方法，具体来说就是采用几个循环，亦可以为了减少时间复杂度，用哈希表存储搜索；

哈希表1存储列数；
哈希表2存储行列差（为了判断左上右下方向，行列同时递增，y=x+k，所以差是一个定值）
哈希表3存储行列和（为了判断左下右上方向，行列一个增一个减，y+x=k，所以和是一个定值）

完整代码：

class Solution {
   
private:
    vector<int> columnValue;
    unordered_set<int> Column;
    unordered_set<int> leftUp;
    unordered_set<int> rightDown;
    void GenerateBoard(vector<vector<string>>& Ans,int n){
   
        vector<string> solutionString;
        for(int i=0;i<n;++i){
   
            string rowString(n,'.');
            rowString[columnValue[i]]='Q';
            solutionString.push_back(rowString);
        }
        Ans.push_back(solutionString);
    }
    void GenerateNqueen(vector<vector<string>>& Ans,int n,int row){
   
        //最后一行放置成功后就返回
        if(n==row){
   
            //Ans push
            GenerateBoard(Ans,n);
        }
        for(int j=0;j<n;++j){
   //对于每一行来说，每一个位置都有可能放置皇后
            //确保列的方向上不冲突
            if(Column.count(j)) continue;
            //确保左上方向不冲突（差相等）同时增
            int Value1=row-j;
            if(leftUp.count(Value1)) continue;
            //确保右上方向不冲突（和相等）一增一减
            int Value2=row+j;
            if(rightDown.count(Value2)) continue;
            //放置皇后以及后续操作
            Column.insert(j);
            leftUp.insert(Value1);
            rightDown.insert(Value2);
            columnValue.push_back(j);
            GenerateNqueen(Ans,n,row+1);
            //回溯
            Column.erase(j);
            leftUp.erase(Value1);
            rightDown.erase(Value2);
            columnValue.pop_back();
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
   
        //从上到下依次确定每一行的皇后位置，然后回溯（将刚刚做的变化还原）
        //如何判断该位置是否可以放置皇后，可以采用三个哈希集合来判断（常数时间复杂度）
        vector<vector<string>> Ans;
        GenerateNqueen(Ans,n,0);
        return Ans;
    }
};

细节总结：

1. 一定要将三个方向判断完再将数据insert到哈希集合里面去，最开始我写的是判断完，如果没有continue就将新的元素放到哈希表里面去，结果row一直没有到达n，！！！

for(int j=0;j<n;++j){
   //对于每一行来说，每一个位置都有可能放置皇后
            //确保列的方向上不冲突
            if(Column.count(j)) continue;
            Column.insert(j);
            //确保左上方向不冲突（差相等）同时增
            int Value1=row-j;
            if(leftUp.count(Value1)) continue;
            leftUp.insert(Value1);
            //确保右上方向不冲突（和相等）一增一减
            int Value2=row+j;
            if(rightDown.count(Value2)) continue;
            rightDown.insert(Value2);
            //放置皇后以及后续操作 
            columnValue.push_back(j);
            GenerateNqueen(Ans,n,row+1);
            //回溯
            Column.erase(j);
            leftUp.erase(Value1);
            rightDown.erase(Value2);
            columnValue.pop_back();
        }

2. string的初始化为n个一样的字符
   

string tmp(n,'.');

End