51.N皇后（回溯法）

解题思路：

回溯法

主函数
初始化一个全为’.'的二维数组，哪个位置可以放置皇后棋子，修改为’Q’即可。
axis数组用来存放已经放置棋子的坐标。

    //主函数
    vector<vector<string>> solveNQueens(int n) {
    
        vector<vector<string>>ans;
        vector<string>board(n,string(n,'.'));
        vector<vector<int>>axis;
        backtracking(ans,board,axis,0,n);
        return ans;
    }

辅助函数
判断[x,y]这个是否可以放置皇后棋子

    bool canPutQ(vector<vector<int>>&axis,int x,int y){
    
        for(auto& v:axis){
    
            int _x=v[0],_y=v[1];
            int d1=abs(x-_x),d2=abs(y-_y);
            if(d1==0||d2==0||d1==d2) return false;
        }
        return true;
    }

递归函数
进入递归
终止条件，行号=n
当本行有位置可以放置棋子，就进入下一行的搜索，注意要回该当前节点的状态。

void backtracking(vector<vector<string>> &ans,
                        vector<string> &board,
                        vector<vector<int>>&axis,
                        int row,int n)
    {
    
        if(row==n){
    
            ans.push_back(board);
            return;
        }

        for(int i=0;i<n;++i){
    
            //假如不能放置棋子，进入下一次循环
            if(!canPutQ(axis,row,i)){
    
                continue;
            }

            //修改当前节点状态
            board[row][i]='Q';
            axis.push_back({
    row,i});
            //递归子节点
            backtracking(ans,board,axis,row+1,n);
            //回改当前节点状态
            axis.pop_back();
            board[row][i]='.';   
        }
    }

完整代码如下

class Solution {
    
public:
    bool canPutQ(vector<vector<int>>&axis,int x,int y){
    
        for(auto& v:axis){
    
            int _x=v[0],_y=v[1];
            int d1=abs(x-_x),d2=abs(y-_y);
            if(d1==0||d2==0||d1==d2) return false;
        }
        return true;
    }

    //主函数
    vector<vector<string>> solveNQueens(int n) {
    
        vector<vector<string>>ans;
        vector<string>board(n,string(n,'.'));
        vector<vector<int>>axis;
        backtracking(ans,board,axis,0,n);
        return ans;
    }

    void backtracking(vector<vector<string>> &ans,
                        vector<string> &board,
                        vector<vector<int>>&axis,
                        int row,int n)
    {
    
        if(row==n){
    
            ans.push_back(board);
            return;
        }

        for(int i=0;i<n;++i){
    
            //假如不能放置棋子，进入下一次循环
            if(!canPutQ(axis,row,i)){
    
                continue;
            }

            //修改当前节点状态
            board[row][i]='Q';
            axis.push_back({
    row,i});
            //递归子节点
            backtracking(ans,board,axis,row+1,n);
            //回改当前节点状态
            axis.pop_back();
            board[row][i]='.';   
        }
    }
};