题解 | #N皇后问题#

描述

N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后，
要求：任何两个皇后不同行，不同列也不在同一条斜线上，
求给一个整数 n ，返回 n 皇后的摆法数。

数据范围: 1 \le n \le 91≤n≤9

要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n!)O(n!)

例如当输入4时，对应的返回值为2，

对应的两种四皇后摆位如下图所示：

class Solution {
  public:
    /**
     *
     * @param n int整型 the n
     * @return int整型
     */

    int a[10];//保存第几行的皇后在哪，如a[6]=2表示第6行的皇后在第2列
    int cnt = 0;//计数器

    //判断该该位置能否插入皇后
    bool check(int row, int i) {
        for (int j = 1; j <= row; ++j) {
            if (a[j] == i) return false;//同一列不行
            if (a[j] + j == (row + i)) return false;//反斜线不行
            if (a[j] - j == i - row) return false;//正斜线不行
        }
        return true;
    }

    //深度优先搜索
    void dfs(int row,int n) {
        //当行数超过n，则摆法数+1
        if (row == n + 1) {
            cnt++;
            return;
        }

        //对当前行的每一列进行判断
        for (int i = 1; i <= n; ++i) {
            if (check(row, i)) {
                a[row] = i;
                dfs(row + 1,n);
                a[row] = 0;
            }
        }
    }

    int Nqueen(int n) {
        dfs(1,n);
        return cnt;
    }
};