用C++编写八皇后问题,输出有n行,每行输出对应一个输入。输出应是一个正整数,是对应于b的皇后串并给出详细代码
时间: 2024-03-10 12:43:27 浏览: 61
好的,以下是用 C++ 编写八皇后问题的代码,可输出 n 个测试用例的解:
```c++
#include <iostream>
#include <vector>
using namespace std;
// 判断当前位置是否能放置皇后
bool canPlace(vector<int>& board, int row, int col) {
for (int i = 0; i < row; ++i) {
// 检查同一列是否有皇后
if (board[i] == col) {
return false;
}
// 检查对角线是否有皇后
if (abs(row - i) == abs(col - board[i])) {
return false;
}
}
return true;
}
// 回溯求解八皇后问题
void backtrack(vector<int>& board, int row, int& count) {
if (row == board.size()) { // 找到一个解
count++;
return;
}
for (int col = 0; col < board.size(); ++col) {
if (canPlace(board, row, col)) {
board[row] = col;
backtrack(board, row + 1, count);
board[row] = -1; // 恢复现场
}
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
int size = 8;
vector<int> board(size, -1);
int count = 0; // 可行解的数量
backtrack(board, 0, count);
cout << count << endl;
}
return 0;
}
```
对于每个测试用例,我们创建一个大小为 8 的向量 `board`,初始值均为 -1,表示棋盘上每个位置都没有放置皇后。然后从第一行开始,依次尝试在每个位置放置皇后,如果能放置就递归到下一行,否则继续尝试下一个位置。当放置完最后一行时,我们就找到了一个可行解,将计数器 `count` 加 1,然后返回上一行继续尝试其他位置。最终,我们输出计数器的值即可。
阅读全文