leetcode 51题 N 皇后
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例1
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例2
输入：n = 1
输出：[["Q"]]
思路
回溯算法
代码
/**
* @param {number} n
* @return {string[][]}
*/
function solveNQueens(n) {
// col 列集合
// dia1 左上右下方向斜线集合（行坐标与列坐标相减结果相等，如[0, 0], [1, 1]）
// dia2 右上左下斜线斜线集合 (行坐标与列坐标相加结果相等，如[8, 0], [7, 1])
// row 皇后
// res 结果
const col = new Set(), dia1 = new Set(), dia2 = new Set(), row = [], res = [];
putQueen(n, 0, col, dia1, dia2, row, res);
return res;
}
function putQueen(n, index, col, dia1, dia2, row, res) {
if (index === n) {
res.push(generateBoard(n, row));
return;
}
for (let i=0; i<n; i++) {
if (col.has(i)) {
continue;
}
const d1 = i - index;
if (dia1.has(d1)) {
continue;
}
const d2 = i + index;
if (dia2.has(d2)) {
continue;
}
row.push(i);
col.add(i);
dia1.add(d1);
dia2.add(d2);
putQueen(n, index+1, col, dia1, dia2, row, res);
col.delete(i);
dia1.delete(d1);
dia2.delete(d2);
row.pop();
}
}
function generateBoard(n, row) {
const board = new Array(n).fill(new Array(n).fill(".").join(""));
for (let i=0; i<n; i++) {
const temp = board[i].split("");
temp[row[i]] = 'Q';
board[i] = temp.join("");
}
return board;
}
复杂度分析:
- 时间复杂度: O(N!)
- 空间复杂度：O(N)