能用c++写个n皇后的解法吗 输入皇后的数量,返回存在的解法数量
时间: 2024-02-11 19:05:07 浏览: 16
当 n 为 1 或 2 时,不存在解法;当 n 为 3 或 4 时,解法也不唯一。以下是一个基于回溯法的 n 皇后问题的解法,可以求出 n 皇后问题的所有解法数量:
```
#include <iostream>
#include <vector>
using namespace std;
int cnt = 0;
bool check(vector<int>& pos, int row, int col) {
for (int i = 0; i < row; ++i) {
if (pos[i] == col || abs(pos[i] - col) == abs(i - row)) {
return false;
}
}
return true;
}
void dfs(vector<int>& pos, int row, int n) {
if (row == n) {
++cnt;
return;
}
for (int col = 0; col < n; ++col) {
if (check(pos, row, col)) {
pos[row] = col;
dfs(pos, row + 1, n);
}
}
}
int solveNQueens(int n) {
vector<int> pos(n);
dfs(pos, 0, n);
return cnt;
}
int main() {
int n;
cout << "请输入皇后的数量:";
cin >> n;
cout << "存在的解法数量为:" << solveNQueens(n) << endl;
return 0;
}
```
该程序使用了一个长度为 n 的一维数组 pos 来存储每一行皇后所在的列数。在 dfs 函数中,从第一行开始,枚举该行皇后所在的列数,检查是否满足条件,如果满足则继续递归下一行。当递归到第 n 行时,说明找到了一组合法的解法,将计数器 cnt 加 1。最终返回 cnt 即为存在的解法数量。