一、实验目的
- 求解约束满足问题;
- 使用回溯搜索算法求解八皇后问题。
二、实验平台
课程实训平台https://www.educoder.net/paths/369
三、实验内容及步骤
实训内容:2-4 第六章 约束满足问题
1.问题描述
八皇后问题是指在一个 8×8 的棋盘上摆放八个皇后,使得任意两个皇后都不能处于同一行、同一列或同一对角线上。因此,每行只能放一个皇后。
2.算法步骤
- 从第一行开始,枚举每个位置,判断该位置是否可以放置皇后,如果可以,则将皇后放置在该位置。
- 标记该列、主对角线和副对角线已被占用。
- 如果已经放置了8个皇后,增加计数器,回溯到上一行,将上一行皇后的位置改变,继续搜索下一列。
- 如果当前行没有找到合适的位置,回溯到上一行,将上一行皇后的位置改变,继续搜索下一列。
- 如果已经搜索完所有情况,结束搜索。
3.算法原理
回溯法是一种通过不断试错来解决问题的算法。在八皇后问题中,算法通过枚举每个位置,判断该位置是否可以放置皇后,如果可以则继续搜索下一行,否则回溯到上一行。在回溯的过程中,算法撤销之前放置的皇后和标记数组,继续搜索下一列。通过不断尝试,最终找到符合要求的解。回溯算法虽然简单,但是效率较低,因为需要穷举所有可能的情况
4.代码实现
该代码中的 searchh 函数用于在第 i 行搜索可以放置皇后的位置。在每一行中,每个皇后都有 8 个位置(列)可以试放。在尝试放置一个皇后时,需要检查该列、主对角线和副对角线是否已经被占用。
其中,b 数组记录了每一列是否已经有皇后占据,c 数组记录了主对角线是否已经有皇后占据,d 数组记录了副对角线是否已经有皇后占据。主对角线和副对角线的编号分别为 i+j 和 i-j+7。
如果已经放置了 8 个皇后,则增加计数器 sum 的值。如果没有放置完 8 个皇后,则继续在下一行搜索可行的位置。在回溯时,需要撤销之前放置的皇后和标记数组
核心代码如下:
void searchh(int i)
{
for (int j = 1; j <= 8; j++)
{
if ((!b[j]) && (!c[i + j]) && (!d[i - j + 7]))//每个皇后都有八个位置(列)可以试放
{
/********** Begin **********/
// 在(i,j)位置放置一个皇后
a[i] = j;
// 标记该列、主对角线、副对角线已被占用
b[j] = c[i + j] = d[i - j + 7] = 1;
// 如果已经放置了8个皇后
if (i == 8)
{
// 增加计数器
sum++;
}
else
{
// 在下一行搜索可行的位置
searchh(i + 1);
}
// 回溯时撤销之前放置的皇后和标记数组
b[j] = c[i + j] = d[i - j + 7] = 0;
/********** End **********/
}
}
}
5.源程序
#include<iostream>
using namespace std;
int a[9];
int b[9] = { 0 };
int c[16] = { 0 };
int d[16] = { 0 };
int sum = 0;
void searchh(int i)
{
for (int j = 1; j <= 8; j++)
{
if ((!b[j]) && (!c[i + j]) && (!d[i - j + 7]))//每个皇后都有八个位置(列)可以试放
{
/********** Begin **********/
// 在(i,j)位置放置一个皇后
a[i] = j;
// 标记该列、主对角线、副对角线已被占用
b[j] = c[i + j] = d[i - j + 7] = 1;
// 如果已经放置了8个皇后
if (i == 8)
{
// 增加计数器
sum++;
}
else
{
// 在下一行搜索可行的位置
searchh(i + 1);
}
// 回溯时撤销之前放置的皇后和标记数组
b[j] = c[i + j] = d[i - j + 7] = 0;
/********** End **********/
}
}
}
int main()
{
searchh(1);
cout << sum;
return 0;
}
6.运行结果分析
运行结果92表示八皇后问题共有92种不同的解法。每个解法对应着八个皇后在棋盘上不同的摆放位置,满足每个皇后都不在同一行、同一列或同一对角线上的要求。由于八皇后问题的对称性,解法数量为92种。这个结果也可以通过计算八皇后问题的总解数来得到,其总解数为92。说明程序运行正确。
四、实验总结
本次实验中,我们使用回溯法解决了八皇后问题。通过枚举每个位置,判断该位置是否可以放置皇后,如果可以,则将皇后放置在该位置,并标记该列、主对角线和副对角线已被占用。如果已经放置了8个皇后,则增加计数器,回溯到上一行,将上一行皇后的位置改变,继续搜索下一列。如果当前行没有找到合适的位置,则回溯到上一行,将上一行皇后的位置改变,继续搜索下一列。最终,找到所有符合要求的解法。
在实验中,我们编写了八皇后问题的回溯法算法,并通过编写测试用例对算法进行了验证。测试结果表明,该算法能够正确地解决八皇后问题,并得到了92种不同的解法。算法的时间复杂度为 O(8^8),由于其需要枚举所有情况,所以效率相对较低,但对于八皇后问题这种规模较小的问题,仍然可以得到较好的解决。
在实验中,我们编写了八皇后问题的回溯法算法,并通过编写测试用例对算法进行了验证。测试结果表明,该算法能够正确地解决八皇后问题,并得到了92种不同的解法。算法的时间复杂度为 O(8^8),由于其需要枚举所有情况,所以效率相对较低,但对于八皇后问题这种规模较小的问题,仍然可以得到较好的解决。
在本次实验中,我深刻理解了回溯法算法的原理和实现过程,同时也了解到了八皇后问题这一经典问题。通过编写代码和测试用例,我掌握了如何使用回溯法算法解决问题,并在调试过程中积累了一定的编程经验。
文章评论