题解 | #N皇后问题#

方法：回溯+递归

按照题设可以得出：棋盘每一行有且只有一个皇后。根据该特性，使用数组res[n]记录每一行皇后所在的列数。从第一行开始，遍历每一列，判断不同列放置皇后是否有效（不能跟前面所放置的皇后 列数一样，不能处于对角线）；向下递归，当到达最后一行时，摆法加1，进行回溯。

时间复杂度：o(n! * n)。遍历皇后的位置需要o(n!)，有效性判断需要o(n)。

空间复杂度：o(n)。需要数组来记录每一行皇后所在的列数。

class Solution {
  public:
    int Nqueen(int n) {
        vector<int> res(n, 0);
        int num = 0;

        rescure(n, 0, res, num);
        return num;
    }

    void rescure(int n, int idx, vector<int>& res, int& num)  {
        if (idx == n) {
            num++;
            return;
        }

        for (int i = 0; i < n; i++) {
            if (isvalid(idx, i, res)) {
                res[idx] = i;
			  	//进入下一行
                rescure(n, idx + 1, res, num);
            }
        }
    }
	//判断有效性
    bool isvalid(int row, int col, vector<int>& res) {
        for (int i = 0; i < row; i++) {
            if (res[i] == col || row == i || abs(i - row) == abs(res[i] - col))
                return false;
        }
        return true;
    }
};