实验案例--八皇后问题C++(模板类实现)
作者:
AmbitionX
,
2022-05-06 15:45:54
,
所有人可见
,
阅读 223
/*
1.初始化k = 0,初始化解向量x[n] = {-1};
2.重复执行下述操作,拜访皇后k
2.1 把皇后k摆放在下一列的位置,即x[k]++;
2.2 如果皇后k摆放在x[k]位置发生冲突,x[k]++试探下一列,直到不冲突或x[k]出界
2.3 如果x[k]没出界且所有的皇后都摆放完毕,则输出一个解
2.4 如果x[k]没出界但尚有皇后没摆放,则k++,转2.1摆放下一个皇后
2.5 如果x[k]出界,则回溯,x[k] = -1, k--, 转2.1重现摆放皇后k
*/
#include <iostream>
#include <cstring>
using namespace std;
class Queen
{
public:
Queen(int n);
~Queen();
int SetQueen(); // 填写n皇后
void PrintQueen(); // 打印皇后的位置
private:
int Place(int k); // 判断皇后k是否冲突
int *x;
int num; // 皇后的个数
};
Queen :: Queen(int n)
{
x = new int[n];
memset(x, -1, n); // -1表示皇后未放置
num = n;
}
Queen :: ~Queen()
{
delete [] x;
}
int Queen :: SetQueen()
{
int k = 0, count = 0; // count 存储解的个数
while (k >= 0) // 摆放皇后k,注意0<=k<n
{
x[k]++; //在下一列摆放皇后k
while (x[k] < num && Place(k) == 1) x[k]++; // 发生冲突时候,皇后k试探下一列
if (x[k] < num && k == num - 1) // 得到一个解 输出
{
cout << "第" << ++count << "个解是: ";
PrintQueen();
}
else if (x[k] < num && k < num - 1) k += 1;// 尚有皇后未摆放, 准备摆放下一个皇后
else x[k --] = -1; // 重置x[k], 回溯, 重新摆放皇后k
}
return count;
}
// 判断皇后k是否冲突
int Queen :: Place(int k)
{
for (int i = 0; i < k; i++)
if (x[i] == x[k] || abs(i - k) == abs(x[i] - x[k])) // 违法约束 条件 该约束条件推导得来 不同行 不同列 不同斜
return 1; // 冲突返回1
return 0; // 不冲突 返回0
}
void Queen :: PrintQueen() // 打印n皇后的一个解
{
for (int i = 0; i < num; i++)
cout << x[i] + 1 << "\t"; // 数组下标0开始,打印的列号从1开始
cout << endl;
}
int main()
{
int n;
cout << "请输入皇后的个数(n>=4) :" << endl;;
cin >> n;
Queen Q{n};
int res = Q.SetQueen();
cout << "所有解的个数为: " << res << endl;
return 0;
}