n皇后问题的回溯算法c++
时间: 2024-06-19 19:03:34 浏览: 19
n皇后问题是一个经典的回溯算法问题。问题描述如下:在n*n的棋盘上放置n个皇后,使得任意两个皇后不在同一行、同一列或同一斜线上。以下是n皇后问题的回溯算法c++实现:
```
#include <iostream>
#include <vector>
using namespace std;
void backtrack(vector<vector<int>>& board, int row, int n, vector<bool>& cols, vector<bool>& diags, vector<bool>& rev_diags, vector<vector<int>>& res) {
if (row == n) {
res.push_back(board);
return;
}
for (int col = 0; col < n; ++col) {
int diag = row - col + n - 1;
int rev_diag = row + col;
if (cols[col] || diags[diag] || rev_diags[rev_diag]) {
continue;
}
board[row][col] = 1;
cols[col] = true;
diags[diag] = true;
rev_diags[rev_diag] = true;
backtrack(board, row + 1, n, cols, diags, rev_diags, res);
board[row][col] = 0;
cols[col] = false;
diags[diag] = false;
rev_diags[rev_diag] = false;
}
}
vector<vector<int>> solveNQueens(int n) {
vector<vector<int>> res;
vector<vector<int>> board(n, vector<int>(n));
vector<bool> cols(n);
vector<bool> diags(2 * n - 1);
vector<bool> rev_diags(2 * n - 1);
backtrack(board, 0, n, cols, diags, rev_diags, res);
return res;
}
int main() {
int n = 4;
vector<vector<int>> res = solveNQueens(n);
for (auto& board : res) {
for (auto val : board) {
for (int i = 0; i < n; ++i) {
cout << val << " ";
}
cout << endl;
}
cout << endl;
}
return 0;
}
```
该算法使用了回溯法来解决n皇后问题。在代码实现中,我们使用一个二维数组board来表示棋盘,其中board[i][j]表示第i行第j列是否放置了皇后。同时,我们使用三个vector来表示哪些列、哪些正对角线和哪些反对角线已经被占用。在回溯过程中,我们枚举每一行的皇后放置位置,并检查该位置是否合法。如果合法,则将该位置标记为已经占用,并进入下一行的回溯过程。如果不合法,则跳过该位置并尝试下一个位置。当所有行都被占用时,将当前棋盘状态加入结果集中。最后返回结果集即可。
相关推荐
![](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)