52.n-queens-ii.md

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

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

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/n-queens-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

依次枚举每一行皇后的位置

• 每一列只有一个皇后 col[N]
• 每一条斜线只有一个皇后 d[2N -1], ud[2N -1] 两种斜线 斜率为 1，d[x + y] 斜率为-1 , ud[x - y + N]

---

/**
 * @param {number} n
 * @return {string[][]}
 */
var totalNQueens = function (n) {
  let ans = 0;
  let col = new Array(n).fill(false); // 列
  let d = new Array(2 * n - 1).fill(false); // 斜率为1; d[x+y]
  let ud = new Array(2 * n - 1).fill(false); // 斜率为-1; d[x-y+n]
  function setPos(i, j, flag) {
    col[j] = flag;
    d[i + j] = flag;
    ud[i - j + n] = flag;
  }
  for (let i = 0; i < n; i++) {
    setPos(0, i, true);
    dfs(1);
    setPos(0, i, false); // 回溯
  }

  function dfs(i) {
    if (i == n) {
      ans++;
      return;
    }
    for (let j = 0; j < n; j++) {
      if (!col[j] && !d[i + j] && !ud[i - j + n]) {
        setPos(i, j, true);
        dfs(i + 1);
        setPos(i, j, false);
      }
    }
  }
  return ans;
};

class Solution {

    vector<vector<char >> V;
    int count = 0;
    int N;

    vector<bool> col, d, ud;

public:
    int totalNQueens(int n) {
        N = n;
        col = vector<bool>(n);
        d = vector<bool>(2 * n);
        ud = vector<bool>(2 * n);

        dfs(V, 0);
        return count;
    }

    void dfs(vector<vector<char >> V, int i) {
        if (i == N) {
            count++;
            return;
        }
        for (int j = 0; j < N; j++) {
            if (!col[j] && !d[i + j] && !ud[i - j + N]) {
                col[j] = d[i + j] = ud[i - j + N] = true;
                dfs(V, i + 1);
                col[j] = d[i + j] = ud[i - j + N] = false;
            }
        }
    }
};