51.N 皇后

N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

示例 1：

输入：n = 4
输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]

示例 2：

输入：n = 1
输出：[[“Q”]]

提示：

• 1 <= n <= 9

解析

经典回溯问题，逐行放置皇后，用集合记录已占用的列和对角线。

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
  const result = [];
  const cols = new Set();
  const diag1 = new Set(); // 主对角线 row - col
  const diag2 = new Set(); // 副对角线 row + col
  const board = Array.from({ length: n }, () => ".".repeat(n));

  function backtrack(row) {
    if (row === n) {
      result.push([...board]);
      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);
      board[row] = ".".repeat(col) + "Q" + ".".repeat(n - col - 1);
      backtrack(row + 1);
      board[row] = ".".repeat(n);
      cols.delete(col);
      diag1.delete(row - col);
      diag2.delete(row + col);
    }
  }

  backtrack(0);
  return result;
};

用 row - col 和 row + col 分别标记两个方向的对角线，是判断斜线冲突的经典技巧。