/**
* @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;
};
评论