
程序代码:
/*
Author: Sun Kai (S.K)
E-mail: sunkai [at] msn [dot] com
QICQ : 674456991
*/
/*
欢迎光临:http://program.*/
/*
通过pascal.h头文件可以成功编译并运行通过本程序
此代码直接编译无法通过,只是一个伪代码(类C-Pascal描述)
若转载请先得到本人允许,请勿抄袭
原创代码,本人保留本代码最终解释权
代码仅提供参考,代码中无核心删减,但部分注释和中文已略
*/
#include"pascal.h" /*类pascal代码支持*/
#include<stdio.h>
#include<string.h>
#include<time.h>
program sudoku;
/*#define user*/
struct
begin
integer ok[10];
integer num;
integer left;
end x[10][10];
integer s[3][10][10];
integer v[10][10];
integer work(integer i,integer j)
begin
integer k,l;
if(x[i][j].num)
begin
for(k=1;k<10;inc(k))
begin
if(x[i][k].ok[x[i][j].num])
begin
x[i][k].ok[x[i][j].num]=0;
dec(x[i][k].left);
end
if(x[k][j].ok[x[i][j].num])
begin
x[k][j].ok[x[i][j].num]=0;
dec(x[k][j].left);
end
end
for(k=(i-1)/3*3+1;k<(i-1)/3*3+4;inc(k))
for(l=(j-1)/3*3+1;l<(j-1)/3*3+4;inc(l))
begin
if(x[k][l].ok[x[i][j].num])
begin
x[k][l].ok[x[i][j].num]=0;
dec(x[k][l].left);
end
end
x[i][j].left=0;
end
end
integer cuts()
begin
integer i,j,k;
fillchar(s,0,sizeof(s));
for(i=1;i<10;inc(i))
begin
for(j=1;j<10;inc(j))
for(k=1;k<10;inc(k))
begin
if(x[i][j].ok[k])
begin
inc(s[0][i][k]);
inc(s[1][j][k]);
inc(s[2][(i-1)/3*3+(j-1)/3+1][k]);
end
end
end
end
integer search()
begin
integer i,j,k,l,m,n,o,p,q; /* Temp var */
integer count;
integer flag=0;
integer list[3];
integer r[2][10];
cpas(flag);
for(i=1;i<10;inc(i))
begin
for(j=1;j<10;inc(j))
for(k=1;k<j;inc(k))
begin
if(x[i][j].left==2 && x[i][k].left==2 && memcmp(x[i][k].ok,x[i][j].ok,sizeof(x[i][k].ok))==0)
begin
for(l=1;l<10;inc(l))
if(x[i][j].ok[l])
begin
for(m=1;m<10;inc(m))
begin
if(x[i][m].ok[l] && m!=j && m!=k)
begin
x[i][m].ok[l]=0;
dec(x[i][m].left);
write("由于数%d是[%c,%d],[%c,%d]只存在两个相同的后选数中的一个,由此数%d不可能在[%c,%d]\n",l,i+'A'-1,k,i+'A'-1,j,l,i+'A'-1,m);
inc(flag);
end
end
#ifdef user
if(flag) return flag;
#endif
end
end
if(x[j][i].left==2 && x[k][i].left==2 && memcmp(x[j][i].ok,x[k][i].ok,sizeof(x[j][i].ok))==0)
begin
for(l=1;l<10;inc(l))
if(x[j][i].ok[l])
begin
for(m=1;m<10;inc(m))
begin
if(x[m][i].ok[l] && m!=j && m!=k)
begin
x[m][i].ok[l]=0;
dec(x[m][i].left);
write("由于数%d是[%c,%d],[%c,%d]只存在两个相同的后选数中的一个,由此数%d不可能在[%c,%d]\n",l,k+'A'-1,i,j+'A'-1,i,l,m+'A'-1,i);
inc(flag);
end
end
#ifdef user
if(flag) return flag;
#endif
end
end
end
end
for(i=0;i<9;i+=3)
for(j=0;j<9;j+=3)
begin
for(k=1;k<4;inc(k))
for(l=1;l<4;inc(l))
for(m=1;m<=k;inc(m))
for(n=1;n<=l;inc(n))
begin
if(x[i+k][j+l].left==2 && x[i+m][j+n].left==2 && memcmp(x[i+k][j+l].ok,x[i+m][j+n].ok,sizeof(x[i+k][j+l].ok))==0 && !(k==m && l==n))
begin
for(o=1;o<10;inc(o))
begin
if(x[i+k][j+l].ok[o])
begin
for(p=1;p<4;inc(p))
for(q=1;q<4;inc(q))
begin
if(x[i+p][j+q].ok[o] && !(p==m && q==n) && !(p==k && q==l))
begin
x[i+p][j+q].ok[o]=0;
dec(x[i+p][j+q].left);
write("由于数%d是[%c,%d],[%c,%d]只存在两个相同的后选数中的一个,由此数%d不可能在[%c,%d]\n",o,i+m+'A'-1,j+n,i+k+'A'-1,j+l,o,i+p+'A'-1,j+q);
inc(flag);
end
end
end
end
#ifdef user
if(flag) return flag;
#endif
end
end
end
for(i=1;i<10;inc(i))
begin
for(m=0;m<9;m+=3)
begin
fillchar(r,0,sizeof(r));
for(j=1+m;j<4+m;inc(j))
begin
for(k=1;k<10;inc(k))
begin
if(x[i][j].ok[k])
inc(r[0][k]);
if(x[j][i].ok[k])
inc(r[1][k]);
end
end
for(j=1;j<10;inc(j))
begin
if(r[0][j]==s[0][i][j] && r[0][j]!=0 && r[0][j]!=s[2][(i-1)/3*3+(m)/3+1][j])
begin
for(k=(i-1)/3*3+1;k<(i-1)/3*3+4;inc(k))
begin
for(l=1+m;l<4+m;inc(l))
begin
if(k!=i)
begin
if(x[k][l].ok[j])
begin
x[k][l].ok[j]=0;
dec(x[k][l].left);
write("由于%c行与同本行相交的第%d个九宫的公共区域是本行有且只有可能填%d的区域,由此数%d不可能在[%c,%d]\n",i+'A'-1,m/3+1,j,j,k+'A'-1,l);
inc(flag);
end
end
end
end
#ifdef user
if(flag) return flag;
#endif
end
if(r[0][j]==s[2][(i-1)/3*3+(m)/3+1][j] && r[0][j]!=0 && r[0][j]!=s[0][i][j])
begin
for(k=1;k<10;inc(k))
begin
if(k<=m || k>m+3)
begin
if(x[i][k].ok[j])
begin
x[i][k].ok[j]=0;
dec(x[i][k].left);
write("由于%c行与同本行相交的第%d个九宫的公共区域是此九宫中有且只有可能填%d的区域,由此数%d不可能在[%c,%d]\n",i+'A'-1,m/3+1,j,j,i+'A'-1,k);
inc(flag);
end
end
end
#ifdef user
if(flag) return flag;
#endif
end
if(r[1][j]==s[1][i][j] && r[1][j]!=0 && r[1][j]!=s[2][(m)/3*3+(i-1)/3+1][j])
begin
for(k=(i-1)/3*3+1;k<(i-1)/3*3+4;inc(k))
begin
for(l=1+m;l<4+m;inc(l))
begin
if(k!=i)
begin
if(x[l][k].ok[j])
begin
x[l][k].ok[j]=0;
dec(x[l][k].left);
write("由于%d列与同本列相交的第%d个九宫的公共区域是本列有且仅有可能填%d的区域,由此数%d不可能在[%c,%d]\n",i,m/3+1,j,j,l+'A'-1,k);
inc(flag);
end
end
end
end
#ifdef user
if(flag) return flag;
#endif
end
if(r[1][j]==s[2][(m)/3*3+(i-1)/3+1][j] && r[1][j]!=0 && r[1][j]!=s[1][i][j])
begin
for(k=1;k<10;inc(k))
begin
if(k<=m || k>m+3)
begin
if(x[k][i].ok[j])
begin
x[k][i].ok[j]=0;
dec(x[k][i].left);
write("由于%d列与同本列相交的第%d个九宫的公共区域是此九宫中有且仅有可能填%d的区域,由此数%d不可能在[%c,%d]\n",i,m/3+1,j,j,k+'A'-1,i);
inc(flag);
end
end
end
#ifdef user
if(flag) return flag;
#endif
end
end
end
end
for(i=1;i<10;inc(i))
begin
for(j=1;j<10;inc(j))
begin
if(x[i][j].left==1)
begin
for(k=1;k<10;inc(k)) if(x[i][j].ok[k]) break;
x[i][j].num=k;
inc(flag); work(i,j);
write("在[%c,%d]中只能填%d\n",i+'A'-1,j,k);
#ifdef user
if(flag) return flag;
#endif
end
else
begin
for(k=1;k<10;inc(k))
begin
list[0]=s[0][i][k];
list[1]=s[1][j][k];
list[2]=s[2][(i-1)/3*3+(j-1)/3+1][k];
for(l=0;l<3;inc(l))
if(list[l]==1 && x[i][j].ok[k])
begin
fillchar(x[i][j].ok,0,sizeof(x[i][j].ok));
x[i][j].num=k; x[i][j].ok[k]=-1;
inc(flag); work(i,j);
write("在[%c,%d]所在的%s仅可填 %d\n",i+'A'-1,j,l==0 ? "行" : l==1 ? "列" : "九宫",k);
#ifdef user
if(flag) return flag;
#endif
goto next;
end
end
end
next: ;
end
end
return flag;
end
integer can(integer a,integer b)
begin
integer i,j;
integer ta,tb;
ta=(a-1)/3*3;
tb=(b-1)/3*3;
for(i=1;i<10;inc(i))
begin
if(x[i][b].num==x[a][b].num && i!=a) return 0;
if(x[a][i].num==x[a][b].num && i!=b) return 0;
end
for(i=ta+1;i<ta+4;inc(i))
for(j=tb+1;j<tb+4;inc(j))
if(x[i][j].num==x[a][b].num && !(i==a && j==b)) return 0;
return 1;
end
integer dfs(integer a,integer b)
begin
integer i,j,t;
if(a==10)
begin
return 1;
end
if(!x[a][b].num)
begin
for(i=1;i<10;inc(i))
begin
if(x[a][b].ok[i])
begin
x[a][b].num=i;
if(can(a,b))
begin
if(dfs(a+b/9,b%9+1))
begin
return 1;
end
end
x[a][b].num=0;
end
end
end
else
if(dfs(a+b/9,b%9+1)) return 1;
return 0;
end
void output(integer ok,integer s_ok,integer black)
begin
integer i,j,k,l;
char number[10][3]=begin "0","1","2","3","4","5","6","7","8","9"end ;
if(black)
begin
for(i=0;i<20;inc(i))
begin
write("\n");
end
end
write(" ");
for(j=1;j<10;inc(j))
write("%d ",j);
write("\n\n");
for(i=1;i<10;inc(i))
begin
write("%c ",'A'+i-1);
for(j=1;j<10;inc(j))
write("%s ",number[x[i][j].num]);
write("\n");
/*输出可能情况*/
if(ok)
begin
write(" ");
for(j=1;j<10;inc(j))
begin
l=0;
for(k=1;k<10;inc(k))
if(x[i][j].ok[k])
begin
write("%d",k);
inc(l);
end
for(k=0;k<8-l;inc(k)) write(" ");
end
write("\n\n");
end
end
if(s_ok)
begin
for(i=0;i<3;inc(i))
begin
write("s[%d]:\n",i);
for(j=1;j<10;inc(j))
begin
for(k=1;k<10;inc(k)) write("%d ",s[i][j][k]);
write("\n");
end
end
end
end
integer main(void)
begin
integer i,j,k,l;
longint runtime,flag;
fillchar(x,0,sizeof(x));
for(i=1;i<10;inc(i))
begin
for(j=1;j<10;inc(j))
begin
read("%1d",&x[i][j].num);
if(!x[i][j].num)
fillchar(x[i][j].ok,-1,sizeof(x[i][j].ok));
end
end
runtime=clock();
for(i=1;i<10;inc(i))
for(j=1;j<10;inc(j)) work(i,j);
for(i=1;i<10;inc(i))
for(j=1;j<10;inc(j))
begin
x[i][j].left=0;
for(l=1;l<10;inc(l))
if(x[i][j].ok[l]) inc(x[i][j].left);
end
do
begin
#ifdef user
getch();
output(1,0,1);
#endif
cuts();
end while(search());
/*=================================*/
/*输出部分*/
write("结束\n");
flag=1;
for(i=1;i<10;inc(i))
for(j=1;j<10;inc(j))
if(!x[i][j].num) begin flag=0; break; end
write("推理解答%s\n",flag ? "成功" : "失败");
if(!flag)
begin
write("继推理后进行搜索解答\n");
if(dfs(1,1)) write("搜索解答成功\n");
else write("搜索解答失败\n");
end
output(0,0,0);
runtime=clock()-runtime;
write("Total time: %dms\n",runtime);
/*=================================*/
while(1);
return 0;
end