回朔算法2

void TuiLi::hh_out()
{
//刷新棋盤數(shù)據(jù)
int i,j,z=0;

for(i=0;i{
for(j=0;j{
HH[i][j]=hh[z];
z++;
}
}

}

void TuiLi::hh_print()
{
//輸出問題解
int i,j;

for(i=0;i{
printf(" ");
for(j=0;j{
if(HH[i][j]==0) printf("+ ");
else if(HH[i][j]==1) printf("W ");
}
printf("");
}
printf("");
}

int TuiLi::ok_hh(int m)
{
int i,j,x,y;
x=0;
for(i=0;ifor(j=0,x=0;j{
x+=HH[i][j];
if(x>=2) return 1;
}
//不允許行重復(fù)
for(i=0;ifor(j=0,x=0;j{
x+=HH[j][i];
if(x>=2) return 1;
}
//不允許列重復(fù)

for(y=0;y<=(N-1);y++)
{
for(i=y,j=(N-1),x=0;i>=0&&j>=0;i--,j--)
{
x+=HH[i][j];
if(x>=2) return 1;
}
}
for(y=(N-1);y>=0;y--)
{
for(i=y,j=0,x=0;i>=0&&j<=(N-1);i++,j++)
{
x+=HH[i][j];
if(x>=2) return 1;
}
}

for(y=0;y<=(N-1);y++)
{
for(i=y,j=0,x=0;i>=0&&j<=(N+1);i--,j++)
{
x+=HH[i][j];
if(x>=2) return 1;
}
}

for(y=(N-1);y>=0;y--)
{
for(i=y,j=(N-1),x=0;i<=(N-1)&&j>=0;i++,j--)
{
x+=HH[i][j];
if(x>=2) return 1;
}
}
//不允許斜線重復(fù)

return 0;
}

int TuiLi::ok_hh_sc()
{
//最后判斷解是否合法
int i,j,x=0;
for(i=0;ifor(j=0;j{
x+=HH[j][i];
}
if(x==N) return 1;else return 0;
}

int TuiLi::go_hh()
{
//解皇后問題
int i,c=0;

hh_init();
hh_out();
//回溯根節(jié)點(diǎn)初始值，調(diào)整這個值能調(diào)整回溯進(jìn)度
hh[0]=1;
hh_out();
i=0;
while(1)
{
if(hh[i]>=0)
{
//回溯點(diǎn)取值在正常范圍內(nèi)
if(ok_hh(i))
{
//如果和剪枝條件沖突，嘗試下一個可用值
hh[i]--;
hh_out();
continue;
}
if(i>=(N*N-1))
{
//已經(jīng)到了最后一個節(jié)點(diǎn)也就是找到了一個解先輸出它
if(ok_hh_sc()){if(c<=100)hh_print();c++;}
//然后嘗試找到其它的解
hh[(N*N-1)]--;
hh_out();
continue;
}
//回溯點(diǎn)值沒有產(chǎn)生沖突擴(kuò)展他嘗試開始下一個節(jié)點(diǎn)
i++;
hh[i]=1;
hh_out();

}else
{
//超過回溯點(diǎn)取值范圍
//此回溯點(diǎn)已死復(fù)位
hh[i]=0;
hh_out();
//退回前一回溯點(diǎn)
i--;
if(i<0)
{
printf("已經(jīng)找出%d皇后問題所有解共有：%d個解！",N,c);
printf("如果皇后問題解太多的話就只輸出前面100個！");

return 1;
}
//嘗試對上一回溯點(diǎn)進(jìn)行擴(kuò)展
hh[i]--;
hh_out();
continue;
}
}

return 0;
}