写点什么

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

用户头像
Lee Chen
关注
发布于: 2020 年 12 月 03 日
LeetCode题解:51. N 皇后,回溯+哈希表,JavaScript,详细注释

原题链接: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();
};



发布于: 2020 年 12 月 03 日阅读数: 44
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:51. N 皇后,回溯+哈希表,JavaScript,详细注释