一、问题详情:
按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n
个皇后放置在 n×n
的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n
,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q'
和 '.'
分别代表了皇后和空位。
示例 1:
输入:n = 4 输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:
输入:n = 1 输出:[["Q"]]
提示:
1 <= n <= 9
二、我的答案:
/**
* @param {number} n
* @return {number}
*/
var totalNQueens = function(n) {
let count = 0;
const cols = new Set(); // 列上是否有皇后
const diagonals1 = new Set(); // 左上到右下对角线上是否有皇后
const diagonals2 = new Set(); // 右上到左下对角线上是否有皇后
function backtrack(row) {
if (row === n) {
// 找到一个解决方案
count++;
return;
}
for (let col = 0; col < n; col++) {
const diagonal1 = row - col;
const diagonal2 = row + col;
if (!cols.has(col) && !diagonals1.has(diagonal1) && !diagonals2.has(diagonal2)) {
cols.add(col);
diagonals1.add(diagonal1);
diagonals2.add(diagonal2);
backtrack(row + 1); // 继续下一行的回溯
cols.delete(col);
diagonals1.delete(diagonal1);
diagonals2.delete(diagonal2);
}
}
}
backtrack(0); // 从第一行开始回溯
return count;
};