void TuiLi::SD_in()
{
//获取题目信息
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);//获得系统当前时间
printf("\n找到一个数独解获取时间为：%d年%d月%d日%d时%d分%d秒\n",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("\n");
}
printf("\n");
}
int TuiLi::ok_sd() //解数独用剪枝函数
{
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;
}
//不允许行重复
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;
}
//不允许列重复
return 0;
}
int TuiLi::go_sd() //解数独入口函数
{
int i,c=0;
//获取题目信息
SD_in();
//回溯根节点初始值，调整这个值能调整回溯进度
if(!sudu_ji[0])sudu[0]=1;
i=0;
while(1)
{
//sd_print();
//Sleep(10);
if(sudu[i]<=9)
{
//回溯点取值在正常范围内
if(ok_sd())
{
//如果和剪枝条件冲突，尝试下一个可用值
if(!sudu_ji[i])sudu[i]++;
continue;
}
if(i>=80)
{
//已经到了最后一个节点也就是找到了一个解先输出它
sd_print();
//然后尝试找到其它的解
if(!sudu_ji[80])sudu[80]++;
c++;
if(c>=10)
{
printf("此题解太多只输出前面10个解!\n\n");
return 0;
}
continue;
}
//回溯点值没有产生冲突扩展他尝试开始下一个节点
i++;
if(!sudu_ji[i])sudu[i]=1;
}else
{
//超过回溯点取值范围
//此回溯点已死复位
if(!sudu_ji[i])sudu[i]=0;
//退回前一回溯点
i--;
if(sudu_ji[i]) i--;//回溯后的当前回溯节点是题目已经标记过的就在往前回溯一步
if(i<0)
{
printf("已经找出数独所有解共有：%d个解！\n",c);
return 1;
}
//尝试对上一回溯点进行扩展
if(!sudu_ji[i])sudu[i]++;
continue;
}
}
return 0;
}
void TuiLi::hh_init()
{
//数据初始化
int i,j;
printf("请输入皇后问题的解题规模：");
scanf("%d",&N);
printf("\n");
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;
}
}
void TuiLi::hh_out()
{
//刷新棋盘数据
int i,j,z=0;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
HH[i][j]=hh[z];
z++;
}
}
}
void TuiLi::hh_print()
{
//输出问题解
int i,j;
for(i=0;i<N;i++)
{
printf(" ");
for(j=0;j<N;j++)
{
if(HH[i][j]==0) printf("+ ");
else if(HH[i][j]==1) printf("W ");
}
printf("\n");
}
printf("\n");
}
int TuiLi::ok_hh(int m)
{
int i,j,x,y;
x=0;
for(i=0;i<N;i++)
for(j=0,x=0;j<N;j++)
{
x+=HH[i][j];
if(x>=2) return 1;
}
//不允许行重复
for(i=0;i<N;i++)
for(j=0,x=0;j<N;j++)
{
x+=HH[j][i];
if(x>=2) return 1;
}
//不允许列重复
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;
}
}
//不允许斜线重复
return 0;
}
int TuiLi::ok_hh_sc()
{
//最后判断解是否合法
int i,j,x=0;
for(i=0;i<N;i++)
for(j=0;j<N;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();
//回溯根节点初始值，调整这个值能调整回溯进度
hh[0]=1;
hh_out();
i=0;
while(1)
{
if(hh[i]>=0)
{
//回溯点取值在正常范围内
if(ok_hh(i))
{
//如果和剪枝条件冲突，尝试下一个可用值
hh[i]--;
hh_out();
continue;
}
if(i>=(N*N-1))
{
//已经到了最后一个节点也就是找到了一个解先输出它
if(ok_hh_sc()){if(c<=100)hh_print();c++;}
//然后尝试找到其它的解
hh[(N*N-1)]--;
hh_out();
continue;
}
//回溯点值没有产生冲突扩展他尝试开始下一个节点
i++;
hh[i]=1;
hh_out();
}else
{
//超过回溯点取值范围
//此回溯点已死复位
hh[i]=0;
hh_out();
//退回前一回溯点
i--;
if(i<0)
{
printf("已经找出%d皇后问题所有解共有：%d个解！\n",N,c);
printf("\n如果皇后问题解太多的话就只输出前面100个！\n");
return 1;
}
//尝试对上一回溯点进行扩展
hh[i]--;
hh_out();
continue;
}
}
return 0;
}