题解 | #N皇后问题#通俗理解

• 这里的关键就是判断当前的位置是否合法，这里给处最通俗的解释：判断函数输入的row和col表示当前位置的坐标，n是棋盘的大小，我们判断只需要判断当前坐标位置之前的位置知否合法即可，至于接下来的位置，我们等走到了再判断即可，给个图示就通俗了：

如上图所示，只检查箭头的方向，至于下面标红的我们等遍历到对应的位置自然会处理它，暂时不用管

所在行是不用检测的，因为我们递归中，每次只要在当前行放置一个皇后，立马就会走到下一行，这样自然就保证了每一行必然只有一个皇后存在的情况

class Solution {
private:
    int res = 0;
    bool isValid(vector<string>& chessboard, int row, int col ,int n){
      	// 检查列中是否有冲突的
        for(int i = 0; i<row; i++){
            if(chessboard[i][col] == 'Q') return false;
        }
      	// 检查45度角
        for(int i = row-1, j = col-1; i>=0 && j>=0; i--, j--){
            if(chessboard[i][j] =='Q') return false;
        }
        // 检查135度角
        for(int i = row-1, j = col+1; i>=0 && j<n; i--, j++){
            if(chessboard[i][j] =='Q') return false;
        }
        return true;
    }
    void backTracking(vector<string>& chessboard, int row, int n){
        if(row >= n){
            res++;
            return;
        }
        
        for(int col = 0; col<n; col++){
          	// 如果当前位置合法
            if(isValid(chessboard, row, col, n)){
              	// 就往当前位置放置一个皇后
                chessboard[row][col] = 'Q';
              	// 放置好了后，直接进入下一层了，因此我们的判断合法中无需检测同一行冲突的情况
                backTracking(chessboard, row+1, n);
              	// 回溯有来有回，路走完了回来要擦除痕迹
                chessboard[row][col] = '.';
            }
        }
    }
    
public:
    int Nqueen(int n) {
        vector<string> chessboard(n, string(n, '.'));
        backTracking(chessboard, 0, n);
        return res;
    }
};