请老师帮忙看一下关于 N 皇后的一个问题
老师您好，我在做 leetcode 第 51 号 N 皇后 问题的时候，我的递归思路如下:
/**
* @param {number} n
* @return {string[][]}
*/
var solveNQueens = function(n) {
const res = [];
// 创建一个棋盘 初始值全是点儿
const checkerBoard = new Array(n).fill(undefined).map(i => new Array(n).fill('.'));
const _solveNQueens = (tmp, x, y, target, current) => {
if (current > target) {
// 如果当前下棋的数量已经超过 target 就直接 return
return;
} else if (current === target) {
// 如果当前下的棋子数正好等于目标的 n 那就找到了一个结果
res.push(tmp.map(i => i.join('')));
} else {
// 如果还没有下够 n 颗皇后
for (let j = 0; j < y; j++) {
// 第 0 到当前的行数 扫描第 x 列 如果某个棋盘有 Q 说明不能放这儿 直接 return
if (tmp[j][x] === 'Q') return;
}
let _x = x, _y = y;
while(true) {
// 扫描当前坐标的左上对角线
_x--;
_y--;
// 如果 _x 或者 _y 越界就 break
if (_x < 0 || _y < 0) break;
if (tmp[_y][_x] === 'Q') return;
}
_x = x, _y = y;
while(true) {
// 扫描当前坐标的右上对角线
_x++;
_y--;
// 如果 _x 或者 _y 越界就 break
if (_x >= n || _y < 0) break;
if (tmp[_y][_x] === 'Q') return;
}
// 复制一份儿棋盘 因为 array 是引类型 也是为了回溯时候能保证棋盘还是上一次的状态
const _tmp = tmp.map(item => [...item]);
// 暂时把皇后下到当前坐标
_tmp[y][x] = 'Q';
for (let i = 0; i < n; i++) {
// 从下一行的第 0 位开始挨个儿试
_solveNQueens(_tmp, i, y + 1, target, current + 1);
}
}
}
for (let i = 0; i < n; i++) {
// 第一次可能下在从左往右数第 i 个位置 下一步要下在第 0 行 目标是下 n 颗皇后, 当前已经下了 0 颗
_solveNQueens(checkerBoard, i, 0, n, 0);
}
console.log(res);
};
按照这个思路，我可以得到所有的正确答案，但是在 res 中每个答案都会有大量的重复，有点想不明为啥会有重复的。
能否麻烦老师帮忙分析一下？
谢谢老师~
664
收起
正在回答
1回答
当你成功在最后一行摆上了妻子周后，还会运行一遍：
for (let i = 0; i < n; i++) {
// 从下一行的第 0 位开始挨个儿试
_solveNQueens(_tmp, i, y + 1, target, current + 1);
}这一遍调用 solve 都会执行：
if (current === target) {
// 如果当前下的棋子数正好等于目标的 n 那就找到了一个结果
res.push(tmp.map(i => i.join('')));
}所以这个解会被放进去 n 次。
代码遇到 bug，不要想，要去调试。去实际看为什么会发生这个错误。自己的思维哪里错了。debug 非常非常重要，进步就发生在这个过程中。
加油！：）
0
有任何疑惑可以回复我~
