题目描述
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给你一个整数 n，返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ’.’ 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[".Q..","…Q","Q…","..Q."],["..Q.","Q…","…Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：[["Q"]]
思路&js代码
1、回溯
问：本题和 46. 全排列 的关系是什么？ 答：由于每行恰好放一个皇后，记录每行的皇后放在哪一列，可以得到一个 [0,n−1] 的排列 queens。示例 1 的两个图，分别对应排列 [1,3,0,2] 和 [2,0,3,1]。所以我们本质上是在枚举列号的全排列。
问：如何 O(1) 判断两个皇后互相攻击？ 答：由于我们保证了每行每列恰好放一个皇后，所以只需检查斜方向。对于 ↗ 方向的格子，行号加列号是不变的。对于 ↖ 方向的格子，行号减列号是不变的。如果两个皇后，行号加列号相同，或者行号减列号相同，那么这两个皇后互相攻击。
问：如何 O(1) 判断当前位置被之前放置的某个皇后攻击到？ 答：额外用两个数组 diag1和 diag2分别标记之前放置的皇后的行号加列号，以及行号减列号。如果当前位置的行号加列号在 diag1中（标记为 true），或者当前位置的行号减列号在 diag2中（标记为 true），那么当前位置被之前放置的皇后攻击到，不能放皇后。
var solveNQueens = function(n) {
const ans = [];
const queens = Array(n).fill(0); // 皇后放在 (r,queens[r])
const col = Array(n).fill(false);
const diag1 = Array(n * 2 - 1).fill(false);
const diag2 = Array(n * 2 - 1).fill(false);
function dfs(r) {
if (r === n) {
ans.push(queens.map(c => '.'.repeat(c) + 'Q' + '.'.repeat(n - 1 - c)));
return;
}
// 在 (r,c) 放皇后
for (let c = 0; c < n; c++) {
const rc = r - c + n - 1;
if (!col[c] && !diag1[r + c] && !diag2[rc]) { // 判断能否放皇后
queens[r] = c; // 直接覆盖，无需恢复现场
col[c] = diag1[r + c] = diag2[rc] = true; // 皇后占用了 c 列和两条斜线
dfs(r + 1);
col[c] = diag1[r + c] = diag2[rc] = false; // 恢复现场
}
}
}
dfs(0);
return ans;
};