完成n-皇后程序c++
时间: 2024-03-10 18:44:24 浏览: 58
用C++实现的n皇后问题
好的,下面是一个简单的 n-皇后问题的程序示例,使用 C++ 语言编写:
```c++
#include <iostream>
#include <vector>
using namespace std;
void dfs(int n, vector<int>& cols, vector<vector<string>>& res) {
if (cols.size() == n) {
vector<string> board(n, string(n, '.'));
for (int i = 0; i < n; i++) {
board[i][cols[i]] = 'Q';
}
res.push_back(board);
return;
}
for (int col = 0; col < n; col++) {
bool ok = true;
for (int i = 0; i < cols.size(); i++) {
if (cols[i] == col || cols[i] - i == col - cols.size() || cols[i] + i == col + cols.size()) {
ok = false;
break;
}
}
if (ok) {
cols.push_back(col);
dfs(n, cols, res);
cols.pop_back();
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<int> cols;
dfs(n, cols, res);
return res;
}
int main() {
int n;
cin >> n;
vector<vector<string>> res = solveNQueens(n);
for (auto board : res) {
for (auto row : board) {
cout << row << endl;
}
cout << endl;
}
return 0;
}
```
其中,程序使用一个递归函数 dfs 来搜索所有可能的解法。每一个递归层次表示已经摆放了前 i 行的皇后,cols 数组表示每一行皇后所在的列数。在每一层递归中,程序枚举当前行的每一列,检查是否可以放置皇后。具体来说,程序使用一个布尔变量 ok 来表示当前列是否可以放置皇后,遍历已经放置的每一个皇后,检查是否在同一列,同一对角线上,如果是,则将 ok 设置为 false,并且跳出循环。如果 ok 为 true,表示当前列可以放置皇后,程序将当前列加入 cols 数组中,继续递归搜索下一层,搜索完毕后,需要将当前列从 cols 数组中弹出,以便于搜索其他解法。
程序最终输出所有的解法,每一个解法是一个 n*n 的棋盘,其中 Q 表示皇后,. 表示空格。
注意:本程序没有进行输入数据的合法性检查,实际应用中需要进行更加严格的输入数据处理。此外,当 n 比较大时,程序的搜索时间会比较长,因此需要使用更加高效的算法来解决问题。
阅读全文