LeetCode 题解:51. N 皇后,回溯 + 哈希表,JavaScript,详细注释
发布于: 2020 年 12 月 03 日
原题链接:https://leetcode-cn.com/problems/n-queens/
解题思路:
皇后可以攻击同行、同列,以及两个斜边上的所有棋子。
要找到n个皇后,其实就是要在每一行上找到一个皇后,并且所有皇后之间都无法互相攻击。
逐行遍历棋盘,在每一行取一个位置放皇后,将其可攻击的列和斜边信息保存到
Set
中。然后查看她是否会和已在棋盘的皇后互相攻击,查看方式就是看她的列和斜边信息是否已在
Set
中保存。通过递归重复2、3步骤,即可找到所有可能的皇后位置。
根据找到的皇后位置,按要求生成棋盘图案即可。
/** * @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
版权声明: 本文为 InfoQ 作者【Lee Chen】的原创文章。
原文链接:【http://xie.infoq.cn/article/458198627381bc55585f72da0】。文章转载请联系作者。
Lee Chen
关注
还未添加个人签名 2018.08.29 加入
还未添加个人简介
评论