51. N 皇后
一句话套路逐行放皇后,cols / 两条 diag 三个标记
题目描述
按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
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
思路
时间
O(n!)空间
O(n)思路
一行放一个 -> 决策树只有 n 层,每层枚举列。
冲突检查三件事
同列、同主对角线(i-j)、同副对角线(i+j)。
用三个 bool 数组把检查降到 O(1):cols[j] / diag1[i-j+n-1] / diag2[i+j]。
变体
Q52 只要方案数 -> 不必存棋盘;位运算版本可以再快几倍。
图解
逐行放皇后,col / 两条对角线判冲突。回溯:放不下就换一列;一种解是一棵搜索树的叶子。
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0051 {
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ans;
if (n <= 0) return ans; // 否则 2*n-1 = -1 会变成巨大的 vector<bool> 尺寸
vector<string> board(n, string(n, '.'));
vector<bool> cols(n, false), diag1(2 * n - 1, false), diag2(2 * n - 1, false);
dfs(n, 0, board, cols, diag1, diag2, ans);
return ans;
}
private:
static void dfs(int n, int row, vector<string>& board, vector<bool>& cols, vector<bool>& d1,
vector<bool>& d2, vector<vector<string>>& ans) {
if (row == n) {
ans.push_back(board);
return;
}
for (int col = 0; col < n; ++col) {
int k1 = row - col + n - 1; // 主对角线编号(平移成非负)
int k2 = row + col; // 副对角线编号
if (cols[col] || d1[k1] || d2[k2]) continue;
board[row][col] = 'Q';
cols[col] = d1[k1] = d2[k2] = true;
dfs(n, row + 1, board, cols, d1, d2, ans);
board[row][col] = '.'; // 撤销
cols[col] = d1[k1] = d2[k2] = false;
}
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0051::Solution s;
auto g4 = s.solveNQueens(4);
vector<vector<string>> want4{{"..Q.", "Q...", "...Q", ".Q.."}, {".Q..", "...Q", "Q...", "..Q."}};
sort(g4.begin(), g4.end());
sort(want4.begin(), want4.end());
CHECK_EQ(g4, want4);
CHECK_EQ(s.solveNQueens(1), vector<vector<string>>({{"Q"}}));
CHECK_EQ(s.solveNQueens(2).size(), (size_t)0); // 2、3 皇后无解
CHECK_EQ(s.solveNQueens(3).size(), (size_t)0);
CHECK_EQ(s.solveNQueens(8).size(), (size_t)92);
CHECK_EQ(s.solveNQueens(0).size(), (size_t)0); // n=0 时 2*n-1 = -1,不守卫会抛 length_error