51. N 皇后
51. N 皇后
题目
The n-queens puzzle is the problem of placing n
queens on an n x n
chessboard such that no two queens attack each other.
Given an integer n
, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q'
and '.'
both indicate a queen and an empty space, respectively.
Example 1:
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2:
Input: n = 1
Output: [["Q"]]
Constraints:
1 <= n <= 9
题目大意
按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n
个皇后放置在 n×n
的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n
,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q'
和 '.'
分别代表了皇后和空位。
解题思路
可以采用递归和回溯来解决,通过检查每一行、每一列和每一对角线上是否存在其他皇后,来保证 N 皇后的问题得到解。最后,将符合条件的结果进行格式化,返回最终的答案。
使用一个一维数组
queens
来表示每一行皇后所在的列位置。其中queens[i]
表示第i
行的皇后所在的列。使用回溯法,逐行放置皇后。在每一行,尝试将皇后放在该行的每一列,检查在当前位置
(row, col)
放置皇后是否满足不互相攻击的条件:queens[i] === col
:检查同一列上是否有其他皇后;queens[i] - i === col - row
:通过检查横坐标减去纵坐标的差是否相等,检查在左上至右下的对角线上是否有其他皇后;queens[i] + i === col + row
:通过检查横坐标加上纵坐标的和是否相等,检查在左下至右上的对角线上是否有其他皇后;- 如果以上三个条件都不满足,说明当前位置是安全的,找到了一个合适的位置。
如果找到一个合适的位置,将该位置的列坐标存入
queens
数组中,并递归调用下一行的放置皇后操作。如果在某一行无法找到合适的位置,则需要回溯,即回到上一行,尝试在上一行的其他列放置皇后,继续递归搜索。
当成功放置 N 个皇后时,将当前
queens
数组的拷贝加入结果数组中。最后,将符合条件的结果进行格式化,返回最终的答案。
代码
/**
* @param {number} n
* @return {string[][]}
*/
var solveNQueens = function (n) {
let res = [];
let queens = new Array(n).fill(-1);
const valid = (row, col) => {
for (let i = 0; i < row; i++) {
if (
// 检查同一列上是否有其他皇后
queens[i] == col ||
// 检查在左上至右下的对角线上是否有其他皇后
queens[i] - i == col - row ||
// 检查在左下至右上的对角线上是否有其他皇后
queens[i] + i == col + row
) {
return false;
}
}
return true;
};
const backtrack = (row) => {
if (row == n) {
// 找到一个成功解
res.push([...queens]);
return;
}
for (let col = 0; col < n; col++) {
if (valid(row, col)) {
// 在当前位置放置皇后
queens[row] = col;
// 继续尝试下一行
backtrack(row + 1);
// 回溯,清空当前行状态
queens[row] = -1;
}
}
};
backtrack(0);
return res.map((arr) =>
arr.map((col) => '.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1))
);
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
52 | N 皇后 II | [✓] | 回溯 | |
1001 | 网格照明 | 数组 哈希表 |