题解 | #N皇后问题#

知识点：递归与回溯

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

如果是线型递归，子问题直接回到父问题不需要回溯，但是如果是树型递归，父问题有很多分支，我需要从子问题回到父问题，进入另一个子问题。因此回溯是指在递归过程中，从某一分支的子问题回到父问题进入父问题的另一子问题分支，因为有时候进入第一个子问题的时候修改过一些变量，因此回溯的时候会要求改回父问题时的样子才能进入第二子问题分支。

n个皇后，不同行不同列，那么肯定棋盘每行都会有一个皇后，每列都会有一个皇后。如果我们确定了第一个皇后的行号与列号，则相当于接下来在�−1n−1行中查找�−1n−1个皇后，这就是一个子问题，因此使用递归：

• 终止条件： 当最后一行都被选择了位置，说明n个皇后位置齐了，增加一种方案数返回。
• 返回值： 每一级要将选中的位置及方案数返回。
• 本级任务： 每一级其实就是在该行选择一列作为该行皇后的位置，遍历所有的列选择一个符合条件的位置加入数组，然后进入下一级。

具体做法：

• step 1：对于第一行，皇后可能出现在该行的任意一列，我们用一个数组pos记录皇后出现的位置，下标为行号，元素值为列号。
• step 2：如果皇后出现在第一列，那么第一行的皇后位置就确定了，接下来递归地在剩余的�−1n−1行中找�−1n−1个皇后的位置。
• step 3：每个子问题检查是否符合条件，我们可以对比所有已经记录的行，对其记录的列号查看与当前行列号的关系：即是否同行、同列或是同一对角线。

#include <vector>
class Solution {
public:
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    //row行号  col列号
    bool isVaild(vector<int> &pos,int row,int col)
    {
        for(int i = 0;i < row ; i++)
        {
            if(row == i || pos[i] == col || abs(row - i) == abs(col - pos[i]))
                return false;
        }
        return true;
    }
    //对每一行 查找一个符合条件位置
    void dfs(vector<int> &pos,int &count,int n,int row)
    {
        //如果全部行都成功选择出一个位置
        if(row == n)
        {
            count++;
            return;
        }
        //遍历所有列
        for(int i = 0;i<n;i++)
        {
            //检查该位置是否符合条件
            /*
            如果剩下的都不符合条件，则不会再次进入子递归，row也就不会到达n，此时就会逐渐回退，说明该点不符合条件，继续for循环，检测下一个点是否符合条件，与DFS的思想很接近
            一开始就是选取最近的可以找到的点，一直往里面深入，直到剩余的点都不符合条件就逐级回退，继续寻找
            */
            if(isVaild(pos, row, i))
            {
                pos[row] = i;
                dfs(pos,count,n,row+1);//递归查找下一行
            }
        }
    }
    int Nqueen(int n) {
        // write code here
        int count = 0;
        //下标为行号，元素为列号，记录皇后位置
        vector<int> pos(n,0);
        dfs(pos,count,n,0);//递归 逐行添加皇后位置
        return count;
    }
};