52.N皇后 II

N皇后 II

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

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

示例 1：

输入：n = 4
输出：2

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 9

解析

与第 51 题类似，只需要计数而不需要记录具体方案。

var totalNQueens = function (n) {
  let count = 0;
  const cols = new Set();
  const diag1 = new Set();
  const diag2 = new Set();

  function backtrack(row) {
    if (row === n) { count++; return; }
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;
      cols.add(col); diag1.add(row - col); diag2.add(row + col);
      backtrack(row + 1);
      cols.delete(col); diag1.delete(row - col); diag2.delete(row + col);
    }
  }
  backtrack(0);
  return count;
};