n后问题分支限界法剪枝函数c++实现
时间: 2024-06-13 12:09:57 浏览: 14
以下是n后问题分支限界法剪枝函数的C++实现:
```c++
#include <iostream>
#include <cmath>
using namespace std;
int n; // n皇后问题中的n
int cnt = 0; // 解的个数
int* x; // 当前解
bool* col; // 列是否被占用
bool* d1; // 对角线是否被占用
bool* d2; // 反对角线是否被占用
// 判断当前位置是否可以放置皇后
bool place(int k, int i) {
return !col[i] && !d1[k - i + n - 1] && !d2[k + i];
}
// 输出当前解
void output() {
cout << "Solution " << ++cnt << ":" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (x[i] == j) {
cout << "Q ";
} else {
cout << ". ";
}
}
cout << endl;
}
cout << endl;
}
// 分支限界法求解n皇后问题
void queen(int k) {
if (k == n) { // 找到一个解
output();
return;
}
for (int i = 0; i < n; i++) {
if (place(k, i)) { // 当前位置可以放置皇后
x[k] = i;
col[i] = true;
d1[k - i + n - 1] = true;
d2[k + i] = true;
queen(k + 1); // 继续搜索下一行
col[i] = false;
d1[k - i + n - 1] = false;
d2[k + i] = false;
}
}
}
int main() {
cout << "Please enter the number of queens: ";
cin >> n;
x = new int[n];
col = new bool[n];
d1 = new bool[2 * n - 1];
d2 = new bool[2 * n - 1];
for (int i = 0; i < n; i++) {
col[i] = false;
}
for (int i = 0; i < 2 * n - 1; i++) {
d1[i] = false;
d2[i] = false;
}
queen(0);
cout << "Total solutions: " << cnt << endl;
return 0;
}
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)