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

[chencl1986]

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

解题思路：

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

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
  // 最终递归输出的结果
  let queenPositions = []; // 保存所有解法中，皇后在棋盘中的位置

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

  // 固定当前行，查找当前行所有不会被其他皇后攻击的位置
  function dfs(row) {
    // 递归终止条件
    // 当遍历完所有行时，表示每行都已找到可以放置皇后的位置
    // 保存结果，并退出递归
    if (row >= n) {
      queenPositions.push(queenRow.slice());
      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);
      // 保存当前列对应的皇后的行位置
      queenRow.push(col);

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

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

  // 生成所有棋盘图案
  function generate() {
    let patterns = []; // 保存棋盘图案

    // 遍历当前已查找到的皇后位置，生成棋盘
    for (let i = 0; i < queenPositions.length; i++) {
      patterns.push([]); // 存入一个空棋盘，供放置图案

      // 遍历n行，生成行图案
      for (let row = 0; row < n; row++) {
        let rowPattern = ''; // 存储当前行的图案

        // 遍历当前列，生成图案
        for (let col = 0; col < n; col++) {
          if (col === queenPositions[i][row]) {
            // 如果遍历到的位置，与已存储的皇后位置相等，则保存Q图案
            rowPattern += 'Q';
          } else {
            // 否则保存.图案
            rowPattern += '.';
          }
        }

        // 将当前行的图案存入棋盘
        patterns[i].push(rowPattern);
      }
    }

    // 返回生成的所有图案
    return patterns;
  }

  // 生成所有棋盘图案并返回结果
  return generate();
};