LeetCode题解：52. N皇后 II，回溯+哈希表，JavaScript，详细注释

[chencl1986]

原题链接：https://leetcode-cn.com/problems/n-queens-ii/

解题思路：

1. 皇后可以攻击同行、同列，以及两个斜边上的所有棋子。
2. 要找到n个皇后，其实就是要在每一行上找到一个皇后，并且所有皇后之间都无法互相攻击。
3. 逐行遍历棋盘，在每一行取一个位置放皇后，将其可攻击的列和斜边信息保存到Set中。
4. 然后查看她是否会和已在棋盘的皇后互相攻击，查看方式就是看她的列和斜边信息是否已在Set中保存。
5. 通过递归重复2、3步骤，即可找到所有可能的皇后位置，之后统计数量返回即可。

/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function (n) {
  // 最终递归输出的结果
  let count = 0; // 统计棋盘数量

  let colSet = new Set(); // 保存当前皇后可能攻击的列
  // 保存当前皇后可能攻击的从右上角到左下角的对角线
  // 在一个正方形的棋盘中，右上角到左下角的点横竖轴的值相加的值相等
  let trToBlSet = new Set();
  // 保存当前皇后可能攻击的从左上角到右下角的对角线
  // 在一个正方形的棋盘中，左上角到右下角的点横竖轴的值相减的值相等
  let tlToBrSet = new Set();

  // 固定当前行，查找当前行所有不会被其他皇后攻击的位置
  function dfs(row) {
    // 递归终止条件
    // 当遍历完所有行时，表示每行都已找到可以放置皇后的位置
    // 统计棋盘数量，并退出递归
    if (row === n) {
      count++;
      return;
    }

    // 遍历当前列对应的行，通过for循环输出每一列不被攻击的皇后位置
    for (let col = 0; col < n; col++) {
      // 行索引加列索引之和，如果该值已在Set中保存过
      // 就表示该位置可被之前存在的皇后从右上角到左下角的对角线攻击
      const colPlusRow = col + row;
      // 行索引减列索引之差，如果该值已在Set中保存过
      // 就表示该位置可被之前存在的皇后从左上角到右下角的对角线攻击
      const colSubtractRow = col - row;

      // 查看当前位置的皇后是否会被攻击，如果会则跳过此位置
      // 由于皇后之间可以互相攻击，因此即使之前的行匹配到的Set中状态较少，也不会出现遗漏
      if (
        // 查看当前位置可被其他皇后从列攻击
        colSet.has(col) ||
        // 查看当前位置是否可被其他皇后从右上角到左下角的对角线攻击
        trToBlSet.has(colPlusRow) ||
        // 查看当前位置是否可被其他皇后从左上角到右下角的对角线攻击
        tlToBrSet.has(colSubtractRow)
      ) {
        // 如果当前位置可被攻击，就继续匹配下一个位置
        continue;
      }

      // 当前递归逻辑
      // 如果当前位置不可被攻击，那么当前位置可以放置一个皇后，那么就要存储当前皇后可攻击的列和对角线
      // 当前皇后可攻击当前列的其他皇后，将当前列索引存储
      colSet.add(col);
      // 当前行列索引之和，表示从右上角到左下角的对角线
      trToBlSet.add(colPlusRow);
      // 当前行列索引之差，表示从左上角到右下角的对角线
      tlToBrSet.add(colSubtractRow);

      // 下探到下层递归
      // 每次下探都会因为for循环的存在继续生成更多状态
      // 由于每在一行取一列之后，都会直接下探到下一行，因此不会出现当前行被取两列的情况
      // 也就是说，每行只会有一个皇后，因此不会出现互相攻击的状况
      dfs(row + 1);

      // 清除递归状态
      // 运行到此处时，已经完整进行了一次递归，可以清除所有中间状态，供下一个递归使用
      colSet.delete(col);
      trToBlSet.delete(colPlusRow);
      tlToBrSet.delete(colSubtractRow);
    }
  }
  dfs(0); // 从第一行开始递归

  // 返回棋盘图案数量
  return count;
};