专注电子技术学习与研究
当前位置:单片机教程网 >> MCU设计实例 >> 浏览文章

回溯算法1

作者:佚名   来源:本站原创   点击数:  更新时间:2013年12月23日   【字体:

int TuiLi::OK()//根据约束条件剪枝的剪枝函数
{
int i,j;
if(
(Fz[0].ys==Fz[1].ys&&Fz[0].ys!=0)||(Fz[0].ys==Fz[2].ys&&Fz[0].ys!=0)
||(Fz[0].ys==Fz[3].ys&&Fz[0].ys!=0)||(Fz[0].ys==Fz[4].ys&&Fz[0].ys!=0)
||(Fz[1].ys==Fz[2].ys&&Fz[1].ys!=0)
||(Fz[1].ys==Fz[3].ys&&Fz[1].ys!=0)||(Fz[1].ys==Fz[4].ys&&Fz[1].ys!=0)
||(Fz[2].ys==Fz[3].ys&&Fz[2].ys!=0)||(Fz[2].ys==Fz[4].ys&&Fz[2].ys!=0)
||(Fz[3].ys==Fz[4].ys&&Fz[3].ys!=0)||


(Fz[0].gj==Fz[1].gj&&Fz[0].gj!=0)||(Fz[0].gj==Fz[2].gj&&Fz[0].gj!=0)
||(Fz[0].gj==Fz[3].gj&&Fz[0].gj!=0)||(Fz[0].gj==Fz[4].gj&&Fz[0].gj!=0)
||(Fz[1].gj==Fz[2].gj&&Fz[1].gj!=0)
||(Fz[1].gj==Fz[3].gj&&Fz[1].gj!=0)||(Fz[1].gj==Fz[4].gj&&Fz[1].gj!=0)
||(Fz[2].gj==Fz[3].gj&&Fz[2].gj!=0)||(Fz[2].gj==Fz[4].gj&&Fz[2].gj!=0)
||(Fz[3].gj==Fz[4].gj&&Fz[3].gj!=0)||

(Fz[0].cw==Fz[1].cw&&Fz[0].cw!=0)||(Fz[0].cw==Fz[2].cw&&Fz[0].cw!=0)
||(Fz[0].cw==Fz[3].cw&&Fz[0].cw!=0)||(Fz[0].cw==Fz[4].cw&&Fz[0].cw!=0)
||(Fz[1].cw==Fz[2].cw&&Fz[1].cw!=0)
||(Fz[1].cw==Fz[3].cw&&Fz[1].cw!=0)||(Fz[1].cw==Fz[4].cw&&Fz[1].cw!=0)
||(Fz[2].cw==Fz[3].cw&&Fz[2].cw!=0)||(Fz[2].cw==Fz[4].cw&&Fz[2].cw!=0)
||(Fz[3].cw==Fz[4].cw&&Fz[3].cw!=0)||

(Fz[0].yl==Fz[1].yl&&Fz[0].yl!=0)||(Fz[0].yl==Fz[2].yl&&Fz[0].yl!=0)
||(Fz[0].yl==Fz[3].yl&&Fz[0].yl!=0)||(Fz[0].yl==Fz[4].yl&&Fz[0].yl!=0)
||(Fz[1].yl==Fz[2].yl&&Fz[1].yl!=0)
||(Fz[1].yl==Fz[3].yl&&Fz[1].yl!=0)||(Fz[1].yl==Fz[4].yl&&Fz[1].yl!=0)
||(Fz[2].yl==Fz[3].yl&&Fz[2].yl!=0)||(Fz[2].yl==Fz[4].yl&&Fz[2].yl!=0)
||(Fz[3].yl==Fz[4].yl&&Fz[3].yl!=0)||

(Fz[0].yp==Fz[1].yp&&Fz[0].yp!=0)||(Fz[0].yp==Fz[2].yp&&Fz[0].yp!=0)
||(Fz[0].yp==Fz[3].yp&&Fz[0].yp!=0)||(Fz[0].yp==Fz[4].yp&&Fz[0].yp!=0)
||(Fz[1].yp==Fz[2].yp&&Fz[1].yp!=0)
||(Fz[1].yp==Fz[3].yp&&Fz[1].yp!=0)||(Fz[1].yp==Fz[4].yp&&Fz[1].yp!=0)
||(Fz[2].yp==Fz[3].yp&&Fz[2].yp!=0)||(Fz[2].yp==Fz[4].yp&&Fz[2].yp!=0)
||(Fz[3].yp==Fz[4].yp&&Fz[3].yp!=0)

) return 1;


for(i=0;i<5;i++)
if(Fz[i].gj==2&&Fz[i].ys!=1&&Fz[i].ys>0) return 1;
//英国人住红色房子
for(i=0;i<5;i++)
if(Fz[i].gj==5&&Fz[i].cw!=1&&Fz[i].cw>0) return 1;
//瑞典人养狗
for(i=0;i<5;i++)
if(Fz[i].gj==4&&Fz[i].yl!=1&&Fz[i].yl>0) return 1;
//丹麦人喝茶

for(i=0;i<5;i++)
{
if(Fz[i].ys==5)
{
for(j=0;j<5;j++)
{
if(Fz[j].ys==3) if(i }
}
}
//绿色房子在白色房子左面

for(i=0;i<5;i++)
if(Fz[i].ys==3&&Fz[i].yl!=3&&Fz[i].yl>0) return 1;
//绿色房子主人喝咖啡

for(i=0;i<5;i++)
if(Fz[i].yp==4&&Fz[i].cw!=4&&Fz[i].cw>0) return 1;
//抽Pall Mall 香烟的人养鸟


for(i=0;i<5;i++)
if(Fz[i].ys==2&&Fz[i].yp!=3&&Fz[i].yp>0) return 1;
//黄色房子主人抽、Dunhill 香烟

if(Fz[2].yl!=2&&Fz[2].yl!=0) return 1;
//住在中间房子的人喝牛奶

if(Fz[0].gj!=1&&Fz[0].gj!=0) return 1;
//挪威人住第一间房

for(i=0;i<5;i++)
{
if(Fz[i].yp==1){
if(i==0)if(Fz[1].cw!=2&&Fz[1].cw!=0) return 1;
if(i==4)if(Fz[3].cw!=2&&Fz[3].cw!=0) return 1;
if((Fz[i].yp==1)&&((Fz[i-1].cw!=2&&Fz[i-1].cw!=0)&&(Fz[i+1].cw!=2&&Fz[i+1].cw!=0))) return 1;
}
}
//抽Blends香烟的人住在养猫的人隔壁

for(i=0;i<5;i++)
{
if(Fz[i].yp==3){
if(i==0)if(Fz[1].cw!=5&&Fz[1].cw!=0) return 1;
if(i==4)if(Fz[3].cw!=5&&Fz[3].cw!=0) return 1;
if((Fz[i].yp==3)&&((Fz[i-1].cw!=5&&Fz[i-1].cw!=0)&&(Fz[i+1].cw!=5&&Fz[i+1].cw!=0))) return 1;
}
}
//抽Dunhill 香烟的人住养马的人隔壁

for(i=0;i<5;i++)
if(Fz[i].yp==2&&Fz[i].yl!=4&&Fz[i].yl>0) return 1;
//抽Blue Master的人喝啤酒

for(i=0;i<5;i++)
if(Fz[i].yp==5&&Fz[i].gj!=3&&Fz[i].gj>0) return 1;
//德国人抽Prince香烟


for(i=0;i<5;i++)
{
if(Fz[i].gj==1){
if(i==0)if(Fz[1].ys!=4&&Fz[1].cw!=0) return 1;
if(i==4)if(Fz[3].ys!=4&&Fz[3].cw!=0) return 1;
if((Fz[i].gj==1)&&((Fz[i-1].ys!=4&&Fz[i-1].ys!=0)&&(Fz[i+1].ys!=4&&Fz[i+1].ys!=0))) return 1;
}
}
//挪威人住蓝色房子隔壁

for(i=0;i<5;i++)
{
if(Fz[i].yp==1){
if(i==0)if(Fz[1].yl!=5&&Fz[1].cw!=0) return 1;
if(i==4)if(Fz[3].yl!=5&&Fz[3].cw!=0) return 1;
if((Fz[i].yp==1)&&((Fz[i-1].yl!=5&&Fz[i-1].yl!=0)&&(Fz[i+1].yl!=5&&Fz[i+1].yl!=0))) return 1;
}
}
//抽Blends香烟的人有一个喝水的邻居
return 0;
}

int TuiLi::go()//推理类执行入口点
{
int i,c=0;
for(i=0;i<25;i++)sz[i]=0;
//回溯根节点初始值,调整这个值能调整回溯进度
sz[0]=1;
gx();
i=0;
while(1)
{
if(sz[i]<=5)
{
//回溯点取值在正常范围内
if(OK())
{
//如果和剪枝条件冲突,尝试下一个可用值
sz[i]++;
gx();
continue;
}
if(i>=24)
{
//已经到了最后一个节点
print();
//然后尝试找到其它的解
sz[24]++;
gx();
c++;
continue;
}
//回溯点值没有产生冲突扩展他尝试开始下一个节点
i++;
sz[i]=1;
gx();

}else
{
//超过回溯点取值范围
//此回溯点已死复位
sz[i]=0;
gx();
//退回前一回溯点
i--;
if(i<0)
{
printf("已经找出推理题所有解共有:%d个解!\n",c);
return 1;
}
//尝试对上一回溯点进行扩展
sz[i]++;
gx();
continue;
}
}

return 0;

}
void TuiLi::sd_in()
{
int i,j,z=0;
for(i=0;i<81;i++)sudu_ji[i]=0;
for(i=0;i<81;i++)sudu[i]=0;

for(i=0;i<9;i++)
for(j=0;j<9;j++)
{
sudu[z]=SD[i][j];
if(SD[i][j]!=0)
{
sudu_ji[z]=1;
}
z++;
}
}

关闭窗口

相关文章