c++回溯法解决四皇后代码
时间: 2023-07-16 22:13:15 浏览: 47
下面是使用回溯法解决四皇后问题的C++代码:
```cpp
#include <iostream>
using namespace std;
const int N = 4; // 棋盘大小为4x4
int col[N]; // 列标记数组,col[i]表示第i列是否已经放置了皇后
int diagonal1[2 * N - 1]; // 主对角线标记数组,diagonal1[i]表示主对角线(i-N+1)是否已经放置了皇后
int diagonal2[2 * N - 1]; // 副对角线标记数组,diagonal2[i]表示副对角线(i)是否已经放置了皇后
void dfs(int row, int &res) {
if (row == N) { // 找到一组解
res++;
return;
}
for (int i = 0; i < N; i++) { // 枚举当前行可以放置皇后的列
if (!col[i] && !diagonal1[row - i + N - 1] && !diagonal2[row + i]) {
col[i] = diagonal1[row - i + N - 1] = diagonal2[row + i] = 1; // 标记当前位置已经放置皇后
dfs(row + 1, res); // 继续搜索下一行
col[i] = diagonal1[row - i + N - 1] = diagonal2[row + i] = 0; // 回溯,恢复标记
}
}
}
int main() {
int res = 0;
dfs(0, res);
cout << "总共有" << res << "种放置方法" << endl;
return 0;
}
```
在上面的代码中,我们用三个数组col、diagonal1和diagonal2来标记哪些位置已经放置了皇后。对于每一行,我们枚举当前可以放置皇后的列,如果该位置还没有被占据,且不在同一主副对角线上,就把皇后放在该位置,并递归搜索下一行。如果搜到最后一行,说明找到了一组解,计数器res加1。最后输出总共有多少种放置方法即可。