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++;
}
}