在 n×n 的方格棋盘上,放置 n 个皇后,要求每个皇后不同行、不同列、不 同左右对角线 用c++语言递归求解,写出相关代码
时间: 2024-05-13 22:17:21 浏览: 22
以下是使用C++语言递归求解n皇后问题的代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
void solveNQueens(int n, vector<int>& board, vector<vector<string>>& result) {
if (board.size() == n) { // 递归终止条件
vector<string> solution(n, string(n, '.'));
for (int i = 0; i < n; i++) {
solution[i][board[i]] = 'Q';
}
result.push_back(solution);
return;
}
for (int i = 0; i < n; i++) {
bool canPlace = true;
for (int j = 0; j < board.size(); j++) {
if (board[j] == i || abs(board[j] - i) == abs(j - board.size())) {
canPlace = false;
break;
}
}
if (canPlace) {
board.push_back(i);
solveNQueens(n, board, result);
board.pop_back();
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> result;
vector<int> board;
solveNQueens(n, board, result);
return result;
}
int main() {
int n = 4;
vector<vector<string>> result = solveNQueens(n);
for (int i = 0; i < result.size(); i++) {
for (int j = 0; j < n; j++) {
cout << result[i][j] << endl;
}
cout << endl;
}
return 0;
}
```
其中,solveNQueens函数是递归函数,用于求解n皇后问题。它的参数包括n,当前放置的棋子位置board,和存储结果的result。递归终止条件是所有皇后都已经放置完毕,此时将当前的棋盘状态存储到result中。否则,对于每一列,判断该列是否可以放置皇后,如果可以,则将该位置添加到board中,继续递归求解。最后,将board中的最后一个元素弹出,回溯到上一层递归。
在主函数中,调用solveNQueens函数求解n皇后问题,并输出结果。