递推算法解决皇后问题
时间: 2023-11-24 19:12:25 浏览: 34
递推算法也可以用来解决n皇后问题,其基本思路是:从第一行开始,依次确定每一行的皇后位置,对于第i行,枚举该行的每一列,如果该列没有被之前的皇后占据,并且该列上下左右的对角线上也没有皇后,就将该列标记为已占据,并将该行的皇后位置记录下来;如果没有找到可用的列,就回溯到上一行重新选择位置。当找到一组可行的解时,将其记录下来,并回溯到上一行重新选择位置,直到找到所有的解。
具体实现时,可以使用三个数组分别记录列、对角线和反对角线是否被占用,初始状态都为false。对于每一行,枚举每一列,判断是否可以放置皇后,如果可以,就将该列和对角线、反对角线标记为已占据,并将该行记录下来;如果不能放置皇后,就继续枚举下一列。当所有列都尝试完毕,仍然没有找到可用的列,就回溯到上一行重新选择位置。当找到一组可行的解时,将其记录下来,然后回溯到上一行重新选择位置。
下面是n皇后问题的C++代码实现,供您参考:
```c++
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> solveNQueens(int n) {
vector<vector<int>> res;
vector<int> board(n, -1);
vector<bool> col(n, false);
vector<bool> diag1(2*n-1, false);
vector<bool> diag2(2*n-1, false);
int row = 0, col_idx = 0;
while (row >= 0) {
if (col_idx == n) { // 回溯到上一行
row--;
if (row >= 0) {
col_idx = board[row] + 1;
col[board[row]] = false;
diag1[row+board[row]] = false;
diag2[row-board[row]+n-1] = false;
}
} else if (!col[col_idx] && !diag1[row+col_idx] && !diag2[row-col_idx+n-1]) { // 判断是否冲突
board[row] = col_idx;
col[col_idx] = true;
diag1[row+col_idx] = true;
diag2[row-col_idx+n-1] = true;
if (row == n-1) { // 找到一个解,记录下来
res.push_back(board);
col[board[row]] = false;
diag1[row+board[row]] = false;
diag2[row-board[row]+n-1] = false;
col_idx = board[row] + 1;
row--;
} else {
row++;
col_idx = 0;
}
} else { // 继续尝试下一列
col_idx++;
}
}
return res;
}
int main() {
int n = 4;
vector<vector<int>> res = solveNQueens(n);
for (auto& sol : res) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (sol[i] == j) cout << "Q";
else cout << ".";
}
cout << endl;
}
cout << endl;
}
return 0;
}
```
希望这个代码能够帮助您理解递推算法解决n皇后问题的思路。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)