回朔算法2

{
//獲取題目信息
int data[]={0,5,0,0,3,0,0,0,0,
0,0,1,6,0,0,9,0,8,
3,0,0,0,0,0,0,0,0,
0,0,0,8,0,0,0,0,0,
0,0,0,0,0,0,7,0,0,
0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0};
int i,j,z=0;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
{
SD[i][j]=data[z];
z++;
}
sd_in();

}

void TuiLi::sd_out()
{
int i,j,z=0;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
{
SD[i][j]=sudu[z];
z++;
}
}

void TuiLi::sd_print()
{
int i,j,z=0;
sd_out();
GetLocalTime(&TIME);//獲得系統(tǒng)當(dāng)前時(shí)間
printf("找到一個(gè)數(shù)獨(dú)解獲取時(shí)間為：%d年%d月%d日%d時(shí)%d分%d秒",TIME.wYear,TIME.wMonth,TIME.wDay,TIME.wHour,TIME.wMinute,TIME.wSecond);
for(i=0;i<9;i++)
{
printf(" ");
for(j=0;j<9;j++)
{
printf("%d ",SD[i][j]);

}
printf("");
}
printf("");
}

int TuiLi::ok_sd() //解數(shù)獨(dú)用剪枝函數(shù)
{
int i,j,x;
sd_out();

for(x=0;x<9;x++)
for(i=0;i<9;i++)
for(j=i+1;j<9;j++)
{
if(SD[x][i]==SD[x][j]&&SD[x][i]!=0) return 1;
}
//不允許行重復(fù)

for(x=0;x<9;x++)
for(i=0;i<9;i++)
for(j=i+1;j<9;j++)
{
if(SD[i][x]==SD[j][x]&&SD[i][x]!=0) return 1;
}
//不允許列重復(fù)

return 0;
}

int TuiLi::go_sd() //解數(shù)獨(dú)入口函數(shù)
{
int i,c=0;
//獲取題目信息
SD_in();
//回溯根節(jié)點(diǎn)初始值，調(diào)整這個(gè)值能調(diào)整回溯進(jìn)度
if(!sudu_ji[0])sudu[0]=1;
i=0;
while(1)
{
//sd_print();
//Sleep(10);
if(sudu[i]<=9)
{
//回溯點(diǎn)取值在正常范圍內(nèi)
if(ok_sd())
{
//如果和剪枝條件沖突，嘗試下一個(gè)可用值
if(!sudu_ji[i])sudu[i]++;
continue;
}
if(i>=80)
{
//已經(jīng)到了最后一個(gè)節(jié)點(diǎn)也就是找到了一個(gè)解先輸出它
sd_print();
//然后嘗試找到其它的解
if(!sudu_ji[80])sudu[80]++;
c++;
if(c>=10)
{
printf("此題解太多只輸出前面10個(gè)解!");
return 0;
}
continue;
}
//回溯點(diǎn)值沒(méi)有產(chǎn)生沖突擴(kuò)展他嘗試開(kāi)始下一個(gè)節(jié)點(diǎn)
i++;
if(!sudu_ji[i])sudu[i]=1;
}else
{
//超過(guò)回溯點(diǎn)取值范圍
//此回溯點(diǎn)已死復(fù)位
if(!sudu_ji[i])sudu[i]=0;
//退回前一回溯點(diǎn)
i--;
if(sudu_ji[i]) i--;//回溯后的當(dāng)前回溯節(jié)點(diǎn)是題目已經(jīng)標(biāo)記過(guò)的就在往前回溯一步

if(i<0)
{
printf("已經(jīng)找出數(shù)獨(dú)所有解共有：%d個(gè)解！",c);
return 1;
}
//嘗試對(duì)上一回溯點(diǎn)進(jìn)行擴(kuò)展
if(!sudu_ji[i])sudu[i]++;
continue;
}
}

return 0;
}

void TuiLi::hh_init()
{
//數(shù)據(jù)初始化
int i,j;
printf("請(qǐng)輸入皇后問(wèn)題的解題規(guī)模：");
scanf("%d",&N);
printf("");
for(i=0;i<1024;i++)
{
hh[i]=0;
}
for(i=0;i<30;i++)
for(j=0;j<30;j++)
{
HH[i][j]=0;
}
}