[52. N皇后 II

52. N皇后 II

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

示例 1：

输入：n = 4输出：2解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1输出：1

提示：

• 1 <= n <= 9

思路：

​经典N皇后，没有变化，

class Solution {public:    int sum=0;//方案数    int totalNQueens(int n) {        //N皇后 从返回解法变成了返回解决方案数量用'.'表示棋盘  'Q'表示棋子        vector<string>board(n,string(n,'.'));        backtrack(board,0);        return  sum;    }    void  backtrack(vector<string>&board,int i){        if(i==board.size()){            sum++;            return;        }        for(int j=0;j<board.size();j++){            if(!isValid(board,i,j)){//如果该棋子放进去非法 就不选                continue;            }            //做选择            board[i][j]='Q';            backtrack(board,i+1);            //撤销选择            board[i][j]='.';        }    }    bool  isValid(vector<string>&board,int row,int col){        int n=board.size();        //检查列         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 < n; i--, j++) {            if (board[i][j] == 'Q')                return false;        }        //检查左上        for (int i = row - 1, j = col - 1;             i >= 0 && j >= 0; i--, j--) {            if (board[i][j] == 'Q')                return false;        }        return true;    }};