LeetCode——N皇后问题 C++

        想必大家耳熟能详的是八皇后问题，该问题是由国际象棋棋手马克斯·贝瑟尔于1848年提出。采用回溯法可以很轻松的解决，但是将其转变为N皇后之后则需要一点小小的改动。

        本文中采用的回溯法代码主体架构来源于代码随想录，其余具体实现为博主所写。

        解决N皇后问题主要需要解决棋子迭代问题以及判断是否合法的问题。

        题目描述：取自LeetCode题目描述

        棋子迭代问题可采用回溯法解决（递归遍历）。

        棋子的存储方式本方法采用int类型容器。其中的每个数字代表每行中棋子位置，因此该容器中数字的范围是0~n-1。如上图所示的两个棋盘中在本代码中的存储数据分别为：[1,3,0,2]，[2,0,3,1]。这样设计的好处是直接免去横方向的判断过程（因为不同的数字直接代表不同行）并且借助快排就可以只用一次循环判断纵向是否合法。

        关于斜向的判断可采用常规手段判断，该判断模块如下所示：

if(j+x[i]=0&&x[i]-j 
        在完成了存储、迭代、和棋盘合法性判断后，即可将所有代码整合到一起完成本题要求。
 
完整代码如下：
 
    vectorx;//存储当前棋盘形状
    vector>xx;//存储结果
    bool isok(vectorx){//检查棋盘是否合法
        vectora=x;
        sort(a.begin(),a.end());
        for(int i=1;i=0&&x[i]-j change(vectorx){//将int类型的棋盘转换为题目要求的类型
        string ss="";
        for(int i=0;is(x.size(),ss);
        for(int i=0;i> solveNQueens(int n) {//主要调用函数
        x.clear();
        xx.clear();
        NQueens(n);
        return xx;
    }