C++随机输入正整数n,求出n皇后问题的解法个数,输出至少2种如图的形式的放置方案。
时间: 2023-11-27 12:52:17 浏览: 66
应用C++实现N皇后问题的求解
5星 · 资源好评率100%
为了解决N皇后问题,我们需要使用回溯算法。回溯算法是一种经典的深度优先搜索算法,在搜索过程中,如果发现当前状态无法达到目标状态,则回溯到上一个状态进行进一步搜索。
以下是C++代码来解决N皇后问题并输出至少2种形式的放置方案:
```c++
#include <iostream>
#include <vector>
#include <string>
using namespace std;
void solveNQueens(vector<vector<string>>& res, vector<string>& board, int row, int n, vector<int>& cols, vector<int>& diag1, vector<int>& diag2) {
if (row == n) {
res.push_back(board);
return;
}
for (int col = 0; col < n; ++col) {
int id1 = col - row + n;
int id2 = col + row;
if (cols[col] || diag1[id1] || diag2[id2]) continue;
board[row][col] = 'Q';
cols[col] = diag1[id1] = diag2[id2] = 1;
solveNQueens(res, board, row+1, n, cols, diag1, diag2);
cols[col] = diag1[id1] = diag2[id2] = 0;
board[row][col] = '.';
}
}
vector<vector<string>> nQueens(int n) {
vector<vector<string>> res;
vector<string> board(n, string(n, '.'));
vector<int> cols(n, 0), diag1(2*n, 0), diag2(2*n, 0);
solveNQueens(res, board, 0, n, cols, diag1, diag2);
return res;
}
int main() {
int n;
cout << "请输入正整数n: ";
cin >> n;
vector<vector<string>> res = nQueens(n);
cout << "解法个数: " << res.size() << endl;
int count = 0;
for (auto& board : res) {
if (count >= 2) break;
cout << "第" << ++count << "种方案:" << endl;
for (auto& row : board) {
cout << row << endl;
}
cout << endl;
}
return 0;
}
```
这里我们定义了一个名为`nQueens()`的函数,它采用回溯算法来解决N皇后问题。我们使用一个二维字符串向量`board`来表示棋盘。每个元素都是`.`,表示空白,或者`Q`,表示皇后。我们还使用三个一维向量`cols`、`diag1`和`diag2`来表示列、正对角线和副对角线是否放置了皇后。在回溯过程中,我们检查当前位置是否可以放置皇后。如果可以,我们将皇后放置在棋盘上,并将其所在列、正对角线和副对角线标记为已使用。然后我们进入下一行继续搜索。如果搜索成功,我们将当前棋盘状态存储在结果向量`res`中。最后,我们输出至少2个形式的方案。
阅读全文