C++基于回溯法解决八皇后问题示例_C++基于回溯法解决八皇后资源-CSDN下载

八皇后问题

137 浏览量 2020-12-31 01:08:42 上传评论 1 收藏 73KB PDF 举报

资源推荐

资源详情

资源评论

C++基于回溯法解决八皇后问题示例基于回溯法解决八皇后问题示例

本文实例讲述了C++基于回溯法解决八皇后问题的方法。分享给大家供大家参考，具体如下：

回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相

当大的问题。

回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结

点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继

续按深度优先策略搜索。

回溯法指导思想——走不通，就掉头。设计过程：确定问题的解空间；确定结点的扩展规则；搜索。

n皇后问题皇后问题

要在n*n的国际象棋棋盘中放n个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的

任意棋子。求所有的解。n=8是就是著名的八皇后问题了。

设八个皇后为xi，分别在第i行(i=1，2，3，4……，8)；

问题的解状态：可以用(1,x1)，(2,x2)，……，(8,x8)表示8个皇后的位置；

由于行号固定，可简单记为：(x1,x2,x3,x4,x5,x6,x7,x8)；

问题的解空间：(x1,x2,x3,x4,x5,x6,x7,x8)，1≤xi≤8(i=1，2，3，4……，8)，共88个状态；

约束条件：八个(1,x1),(2,x2) ,(3,x3),(4,x4) ,(5,x5), (6,x6) , (7,x7), (8,x8)不在同一行、同一列和同一对角线上。

盲目的枚举算法：通过8重循环模拟搜索空间中的88个状态，从中找出满足约束条件的“答案状态”。程序如下：

/*

*作者：侯凯

*说明：八皇后——盲目迭代法

*日期：2013-12-18

*/

#include <iostream>

using namespace std;

bool check_1(int a[],int n)

{

for(int i=2;i<=n;i++)

{

for(int j=1;j<=i-1;j++)

{

if ((a[i]==a[j])||(abs(a[i]-a[j])==i-j))

{

return false;

}

}

}

return true;//不冲突

}

void queens_1()

{

int a[9];

int count = 0;

for(a[1]=1;a[1]<=8;a[1]++)

{

for(a[2]=1;a[2]<=8;a[2]++)

{

for(a[3]=1;a[3]<=8;a[3]++)

{

for(a[4]=1;a[4]<=8;a[4]++)

{

for(a[5]=1;a[5]<=8;a[5]++)

{

for(a[6]=1;a[6]<=8;a[6]++)

{

for(a[7]=1;a[7]<=8;a[7]++)

{

for(a[8]=1;a[8]<=8;a[8]++)

{

if(!check_1(a,8))

continue;

else

{

for(int i=1;i<=8;i++)

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余3页未读，立即下载

内容反馈

weixin_38671048

粉丝: 4

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip