题解 | #N皇后问题#

class Solution {
    int res=0;
public:
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    bool isValid(vector<string>& board,int i,int j,int n){
        if(i<0 ||j<0 || i>=n || j>=n){
            cout<<"out bound"<<endl;
            return false;
        }
        //行
        for(int col=j-1;col>=0;col--){
            if(board[i][col]=='Q'){
                return false;
            }
        }
        for(int row=i-1;row>=0;row--){
            if(board[row][j]=='Q'){
                return false;
            }
        }
        for(int row=i-1,col=j-1; row>=0&&col>=0;row--,col--){
            if(board[row][col]=='Q'){
                return false;
            }
        }
        for(int row=i-1,col=j+1; row>=0&&col>=0;row--,col++){
            if(board[row][col]=='Q'){
                return false;
            }
        }
        return true;
    }
    void backtraking(vector<string>& board,int row,int n){
        if(row==n){
            res++;
            return ;
        }
        for(int i=0;i<n;i++){
            if(isValid(board,row,i,n)){
                board[row][i]='Q';
                backtraking(board,  row+1,  n);
                board[row][i]='.';
            }
        }
    }
    int Nqueen(int n) {
        // write code here
        vector<string> board(n,string(n,'.'));
        backtraking(board,0,n);
        return res;
    }
};

首先是一行的初始化，要使用string，和vector初始化的方法类似，不过string的元素为char没有显式表达

vector path(n,string(n,'.'));

N皇后的行是通过backTracking函数进行选取的，而列是通过for循环选取的，进行回溯操作时注意j从0到n, row=row+1;

递归终止条件

if(row==n){

  res++;

  return ;

  }

检查有个小技巧，从当前点出发进行判断，而不从边界点出发进行判断。

不需要进行行的判断，因为每行只有一个，插入就换下一行