力扣-51题 N皇后（C++）- 回溯

题目链接： 题目如下：

class Solution {
          
   
public:
    vector<vector<string>> solveNQueens(int n) {
          
   
        vector<string> board(n,string(n,.));//完成初始化一个空棋盘，因为在全局private中不能定义board中的内容，所以变成局部变量
        backtracking(n,0,board);//参数1为棋盘大小，参数2是表示第几行，参数3是表示当前棋盘
        return result;
    }
    void backtracking(int n,int startRow,vector<string>& board){
          
   
        if(startRow==n){
          
   
            result.push_back(board);
            return ;
        }

        for(int col=0;col<n;col++){
          
   
            if(isValid(startRow,col,board,n)){
          
   //判断当前位置是否可以存放
                board[startRow][col]=Q;
                backtracking(n,startRow+1,board);
                board[startRow][col]=.;
            }
        }
    }
    bool isValid(int row,int col,vector<string>& board,int n){
          
   
        //n皇后问题的皇后放置的要求：不能相互同行，同列，及同斜线
        //检查行
        for(int i=0;i<col;i++){
          
   
            if(board[row][i]==Q) return false;
        }
        //检查列
        for(int i=0;i<row;i++){
          
   
            if(board[i][col]==Q) return false;
        }

        //检查正斜
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
          
   
            if(board[i][j]==Q) return false;
        }
        //检查负斜
        for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
          
   
            if(board[i][j]==Q) return false;
        }

        return true;
    }
private:
    vector<vector<string>> result;
};