按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例 1:
输入:n = 4
输出:[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:
输入:n = 1
输出:[[“Q”]]
提示:
1 <= n <= 9
思路
N皇后问题是在一个NxN的棋盘上放置N个皇后,使得它们不能互相攻击,即任何两个皇后都不能处于同一行、同一列或同一斜线上。
定义一个位集(bitset)来记录每一列以及两个对角线上是否已经放置了皇后。其中,vis1
用于记录列,vis2
和vis3
用于记录两个对角线。
在dfs
函数中,首先检查当前搜索的深度是否已经达到了棋盘的大小,如果达到了,说明已经找到了一种放置皇后的方式,将其添加到结果集中。然后,遍历当前行的每一列,检查放置皇后是否合法,即检查当前位置所在的列以及两个对角线上是否已经有皇后。如果合法,就在当前位置放置皇后,并标记当前位置所在的列和两个对角线,然后搜索下一行。搜索完后,需要进行回溯,即恢复当前位置的状态,以便进行下一次搜索。
AC代码
/** @lc app=leetcode.cn id=51 lang=cpp** [51] N 皇后*/// @lc code=start
class Solution {static const int N = 15;vector<vector<string>> ans;vector<string> tmp;bitset<N> vis1, vis2, vis3;void dfs(int i, int n) {// 递归出口if (i == n) {ans.push_back(tmp);return;}for (int j = 0; j < n; j++) {// 剪枝if (vis1[j] || vis2[i + j] || vis3[n + i - j]) {continue;}// 修改现场vis1[j] = 1;vis2[i + j] = 1;vis3[n + i - j] = 1;tmp[i][j] = 'Q';dfs(i + 1, n);// 恢复现场vis1[j] = 0;vis2[i + j] = 0;vis3[n + i - j] = 0;tmp[i][j] = '.';}}public:vector<vector<string>> solveNQueens(int n) {// 初始化vis1.reset();vis2.reset();vis3.reset();tmp.resize(n);for (auto &i : tmp) {i.resize(n, '.');}dfs(0, n);return ans;}
};
// @lc code=end