LeetCode 52. N皇后 II【递归、回溯】

难度： 困难

题目描述

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

[外链图片转存失败(img-k1ZXc9xM-1569454544680)(media/15683482588571/8-queens.png)] 上图为 8 皇后问题的一种解法。

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

示例:

输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

思路

和第51题基本一样，只是给函数加上了返回值，用来计算个数。

代码

class Solution {
          
   
public:
    int totalNQueens(const int n) {
          
   
        bool used[n + 1] = {
          
   };  // 第i行是否有皇后
        int permutation[n + 1] = {
          
   };  // 当前排列

        function<int(int, int, int)> n_queens;
        n_queens = [&used, &permutation, &n_queens](int n, int index, int cnt)-> int {
          
   
            if (index == n + 1)  // 找到一个合法方案
                return cnt + 1;

            for (int x = 1; x <= n; ++x) {
          
     // 第x行
                if (not used[x]) {
          
   
                    bool flag = true;  // 表示当前皇后不会和之前皇后冲突
                    for (int pre = 1; pre < index; ++pre) {
          
   
                        if (abs(index - pre) == abs(x - permutation[pre])) {
          
     // 与之前的皇后在一条对角线上
                            flag = false;
                            break;
                        }
                    }
                    if (flag) {
          
   
                        permutation[index] = x;
                        used[x] = true;
                        cnt = n_queens(n, index + 1, cnt);
                        used[x] = false;
                    }
                }
            }

            return cnt;
        };

        return n_queens(n, 1, 0);
    }
};