完成了这个可以解任意数独的程序
耗费了4，5天时间，总算是完成了。本想好好的给注释下，但现在实在是太累了 ，看见那些代码就发晕……
最近毕设开题了 ，等过段时间再仔细注释……
基本思路就是先用 显式唯一法，隐式唯一法，显式数对法 进行逻辑推导。
一般的简单数独在此刻已经解开了，
对于较难的数独，此时进行填数尝试，直到尝试成功为止。
目前对于多解数独只能得出一个解（要得到全解，只要将程序少许修改即可）
其他任何数独都可结算出结果
程序代码：#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int how_many_nums (int (*p)[9][10]);
void check_finish(int (*p)[9][10]);
void try (int (*p)[9][10],int which_num);
void check (int (*p)[9][10],int turn);
void naked_pair (int (*p)[9][10],int turn);
void scan_small_box (int (*p)[9][10],int start_y,int start_x,int turn);
void hidden_single (int (*p)[9][10],int turn);
void naked_single (int (*p)[9][10],int turn);
void clean_num (int (*p)[9][10],int n,int turn);
void display (int (*p)[9][10]);
int char_to_num (char *p);
int ensered_num=1,flag=1,circle_loop=0,is_same=0;
int i,j,k;
void check_finish (int (*p)[9][10])
{
int known_num=0;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(p[i][j][0]==1)
++known_num;
}
}
if(known_num>79)
{
printf("\n\n...DONE...\n\n尝试的次数为%d次\n\n",circle_loop);
display(p);
exit(0);
}
return;
}
void display (int (*p)[9][10])
{
for(i=0;i<9;i++)
{
if(i==3 || i==6)
printf("-----------------------------\n");
for(j=0;j<9;j++)
{
if(j==3 || j==6) printf("|");
if(p[i][j][0]==1)
{
for(k=1;k<10;k++)
{
if(p[i][j][k]) break;
}
printf(" %d ",p[i][j][k]);
}
else printf(" . ");
}
printf("\n");
}
printf("\n");
return;
}
int char_to_num (char *p)
{
char ch;
ch=*(p+j);
switch(ch)
{
case '0':return 0;
case '1':return 1;
case '2':return 2;
case '3':return 3;
case '4':return 4;
case '5':return 5;
case '6':return 6;
case '7':return 7;
case '8':return 8;
case '9':return 9;
default:printf("Input Error\n");
exit(1);
}
}
void check (int (*p)[9][10],int turn)
{
while(ensered_num)
{
ensered_num=0;
while(flag)
{flag=0;
naked_single(p,turn);
}
hidden_single(p,turn);
naked_pair(p,turn);
hidden_single(p,turn);
}
return;
}
int main ()
{
int box[9][9][10];
int source[10]={9,1,2,3,4,5,6,7,8,9};
char input[9];
int num,whole_nums,seleted_num;
int (*addr)[9][10]=box;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
memcpy(box[i][j],source,sizeof(source));
}
printf("输入数独，一行输完后按回车确认，待确定数用‘0’代替\n");
for(i=0;i<9;i++)
{
scanf("%s",input);
for(j=0;j<9;j++)
{
num=char_to_num(input);
if(num)
{
box[i][j][0]=1;
for(k=1;k<10;k++)
{
if(k!=num) box[i][j][k]=0;
}
}
}
}
display(addr);
printf("\n现在开始计算\n");
check(addr,1);
check_finish(addr);
whole_nums=how_many_nums(addr);
for(seleted_num=1;seleted_num<=whole_nums;seleted_num++)
try(addr,seleted_num);
}
void try(int (*p)[9][10],int which_num)
{
printf("NOW Trying...");
++circle_loop;
if(circle_loop>1000) {printf("尝试次数超过了1000次，请检查你的输入\n");exit(1);}
int isthis=0,keep_k,whole_nums,seleted_num;
int A[9][9][10];
int (*A_addr)[9][10]=A;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
for(k=0;k<10;k++)
A[i][j][k]=p[i][j][k];
}
}
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(A[i][j][0]>1)
{isthis=1;break;}
}
if(isthis) break;
}
for(k=1;k<10;k++)
{
if(A[i][j][k])
{
if(which_num==1) {keep_k=A[i][j][k];break;}
if(which_num==2) {which_num=1;continue;}
if(which_num==3) {which_num=2;continue;}
if(which_num==4) {which_num=3;continue;}
if(which_num==5) {which_num=4;continue;}
if(which_num==6) {which_num=5;continue;}
if(which_num==7) {which_num=6;continue;}
if(which_num==8) {which_num=7;continue;}
if(which_num==9) {which_num=8;continue;}
}
}
for(k=1;k<10;k++)
{
if(k!=keep_k) A[i][j][k]=0;
}
A[i][j][0]=1;
printf("假定第%d行第%d列 为%d\n",i+1,j+1,keep_k);
flag=1;ensered_num=1;
check(A_addr,0);
if(is_same)
{
is_same=0;
printf("Error\n");
return;
}
check_finish(A_addr);
whole_nums=how_many_nums(A_addr);
for(seleted_num=1;seleted_num<=whole_nums;seleted_num++)
try(A_addr,seleted_num);
return;
}
int how_many_nums(int (*p)[9][10])
{
int sum=0,break_ok=0;
int i,j;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(p[i][j][0]>1) {break_ok=1;break;}
}
if(break_ok) break;
}
for(k=1;k<10;k++) {if(p[i][j][k]) ++sum;}
return (sum);
}
void naked_single(int (*p)[9][10],int turn)
{
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(p[i][j][0]==1)
{
for(k=1;k<10;k++)
{
if(p[i][j][k]) clean_num(p,k,turn);
if(is_same) return;
}
}
}
}
return;
}
void clean_num (int (*p)[9][10],int n,int turn)
{
int line,col,unit_line,unit_col;
int circle_a,circle_b;
int comb_line,comb_col,loop_k;
int contain[9]={0},cc=0,tt,loop_num;
for(col=0;col<9;col++)
{
if(col!=j)
{
if(p[i][col][n])
{
--p[i][col][0];
p[i][col][n]=0;
if(p[i][col][0]==1)
{flag=1;
ensered_num=1;
for(loop_k=1;loop_k<10;loop_k++)
{if(p[i][col][loop_k]) break;}
if(turn) printf("显式唯一法确定第%d行第%d列 为:%d\n",i+1,col+1,p[i][col][loop_k]);
}
}
}
}
if(turn==0)
{
memset(contain,0,sizeof(contain));
cc=0;
for(loop_num=0;loop_num<9;loop_num++)
{
if(p[i][loop_num][0]==1)
{
for(loop_k=1;loop_k<10;loop_k++)
{
if(p[i][loop_num][loop_k]) break;
}
contain[cc]=p[i][loop_num][loop_k];
cc++;
}
}
for(cc=0;cc<8;cc++)
{
if(contain[cc]==0) break;
for(tt=cc+1;tt<9;tt++)
{
if(contain[cc]==contain[tt])
{is_same=1;return;}
}
}
}
for(line=0;line<9;line++)
{
if(line!=i)
{
if(p[line][j][n])
{
--p[line][j][0];
p[line][j][n]=0;
if(p[line][j][0]==1)
{flag=1;
ensered_num=1;
for(loop_k=1;loop_k<10;loop_k++)
{if(p[line][j][loop_k]) break;}
if(turn) printf("显式唯一法确定第%d行第%d列 为:%d\n",line+1,j+1,p[line][j][loop_k]);
}
}
}
}
if(turn==0)
{
memset(contain,0,sizeof(contain));
cc=0;
for(loop_num=0;loop_num<8;loop_num++)
{
if(p[loop_num][j][0]==1)
{
for(loop_k=1;loop_k<10;loop_k++)
{
if(p[loop_num][j][loop_k]) break;
}
contain[cc]=p[loop_num][j][loop_k];
cc++;
}
}
for(cc=0;cc<8;cc++)
{
if(contain[cc]==0) break;
for(tt=cc+1;tt<9;tt++)
{
if(contain[cc]==contain[tt])
{is_same=1;return;}
}
}
}
if(i<=2) unit_line=0;
else if(i>=3 && i<=5) unit_line=3;
else unit_line=6;
if(j<=2) unit_col=0;
else if(j>=3 && j<=5) unit_col=3;
else unit_col=6;
for(circle_a=0;circle_a<3;circle_a++)
{
comb_line=unit_line+circle_a;
for(circle_b=0;circle_b<3;circle_b++)
{
comb_col=unit_col+circle_b;
if(comb_line!=i || comb_col!=j)
{
if(p[comb_line][comb_col][n])
{
--p[comb_line][comb_col][0];
p[comb_line][comb_col][n]=0;
if(p[comb_line][comb_col][0]==1)
{flag=1;
ensered_num=1;
for(k=1;k<10;k++)
{if(p[comb_line][comb_col][k]) break;}
if(turn) printf("显式唯一法确定第%d行第%d列 为:%d\n",comb_line+1,comb_col+1,p[comb_line][comb_col][k]);
}
}
}
}
}
if(turn==0)
{memset(contain,0,sizeof(contain));
cc=0;
for(circle_a=0;circle_a<3;circle_a++)
{
comb_line=unit_line+circle_a;
for(circle_b=0;circle_b<3;circle_b++)
{
comb_col=unit_col+circle_b;
if(p[comb_line][comb_col][0]==1)
{
for(loop_k=1;loop_k<10;loop_k++)
{if(p[comb_line][comb_col][loop_k]) break;}
contain[cc]=p[comb_line][comb_col][loop_k];
cc++;
}
}
}
for(cc=0;cc<8;cc++)
{
if(contain[cc]==0) break;
for(tt=cc+1;tt<9;tt++)
{
if(contain[cc]==contain[tt])
{is_same=1;return;}
}
}
}
return;
}
void hidden_single (int (*p)[9][10],int turn)
{
int only_posi,only_k,only_num=0;
for(i=0;i<9;i++)
{
for(k=1;k<10;k++)
{
for(j=0;j<9;j++)
{
if(p[i][j][0]>1)
{
if(p[i][j][k])
{
only_posi=j;only_k=k;++only_num;
}
}
}
if(only_num==1)
{flag=1;
ensered_num=1;
p[i][only_posi][0]=1;
if(turn) printf("隐式唯一法确定第%d行第%d列 为:%d\n",i+1,only_posi+1,only_k);
for(k=1;k<10;k++)
{if(k!=only_k) p[i][only_posi][k]=0;}
}
only_num=0;
}
}
while(flag)
{flag=0;
naked_single(p,turn);
}
if(is_same) return;
for(j=0;j<9;j++)
{
for(k=1;k<10;k++)
{
for(i=0;i<9;i++)
{
if(p[i][j][0]>1)
{
if(p[i][j][k])
{
only_posi=i;only_k=k;++only_num;
}
}
}
if(only_num==1)
{flag=1;
ensered_num=1;
p[only_posi][j][0]=1;
if(turn) printf("隐式唯一法确定第%d行第%d列 为:%d\n",only_posi+1,j+1,only_k);
for(k=1;k<10;k++)
{if(k!=only_k) p[only_posi][j][k]=0;}
}
only_num=0;
}
}
while(flag)
{flag=0;
naked_single(p,turn);
}
if(is_same) return;
for(i=0;i<3;i++)
{for(j=0;j<3;j++)
scan_small_box(p,i*3,j*3,turn);
}
return;
}
void scan_small_box (int (*p)[9][10],int start_y,int start_x,int turn)
{
int loop_a,loop_b;
int now_line,now_col;
int only_posi_i,only_posi_j,only_k,only_num;
for(k=1;k<10;k++)
{for(loop_a=0;loop_a<3;loop_a++)
{
now_line=start_y+loop_a;
for(loop_b=0;loop_b<3;loop_b++)
{
now_col=start_x+loop_b;
if(p[now_line][now_col][0]>1)
{
if(p[now_line][now_col][k])
{
only_posi_i=now_line;only_posi_j=now_col;only_k=k;++only_num;
}
}
}
}
if(only_num==1)
{flag=1;
ensered_num=1;
p[only_posi_i][only_posi_j][0]=1;
if(turn) printf("隐式唯一法确定第%d行第%d列 为:%d\n",only_posi_i+1,only_posi_j+1,only_k);
for(k=1;k<10;k++)
{if(k!=only_k) p[only_posi_i][only_posi_j][k]=0;}
}
only_num=0;
}
while(flag)
{flag=0;
naked_single(p,turn);
}
if(is_same) return;
}
void naked_pair (int (*p)[9][10],int turn)
{
int temp[27]={0};
int data[36]={0};
int m,t,change,mark;
int exist_num_1,exist_num_2;
int box_line,box_col,loop_a,loop_b,now_i,now_j,this_i,this_j;
for(i=0;i<9;i++)
{
memset(temp,0,sizeof(temp));
t=0;change=1;mark=0;
for(j=0;j<9;j++)
{
if(p[i][j][0]==2)
{
temp[t]=j;
for(k=1;k<10;k++)
{
if(p[i][j][k])
{
if(change)
{
change=0;
temp[t+1]=p[i][j][k];
}
else temp[t+2]=p[i][j][k];
}
}
t+=3;
change=1;
}
}
t=1;
while(temp[t])
{
m=t+3;
while(temp[m])
{
if(temp[t]==temp[m] && temp[t+1]==temp[m+1])
{mark=1;break;}
else m+=3;
}
if(mark) break;
t+=3;
}
if(mark)
{
exist_num_1=temp[t];
exist_num_2=temp[t+1];
for(j=0;j<9;j++)
{
if(j==temp[t-1] || j==temp[m-1]) continue;
else
{
if(p[i][j][0]>1)
{
if(p[i][j][exist_num_1])
{
--p[i][j][0];
p[i][j][exist_num_1]=0;
}
if(p[i][j][exist_num_2])
{
--p[i][j][0];
p[i][j][exist_num_2]=0;
}
if(p[i][j][0]==1)
{
ensered_num=1;
flag=1;
for(k=1;k<10;k++)
{if(p[i][j][k]) break;}
if(turn) printf("显式数对法确定第%d行第%d列 为:%d\n",i+1,j+1,p[i][j][k]);
}
}
}
}
}
}
while(flag)
{flag=0;
naked_single(p,turn);
}
if(is_same) return;
for(j=0;j<9;j++)
{
memset(temp,0,sizeof(temp));
t=0;change=1;mark=0;
for(i=0;i<9;i++)
{
if(p[i][j][0]==2)
{
temp[t]=i;
for(k=1;k<10;k++)
{
if(p[i][j][k])
{
if(change)
{
change=0;
temp[t+1]=p[i][j][k];
}
else temp[t+2]=p[i][j][k];
}
}
t+=3;
change=1;
}
}
t=1;
while(temp[t])
{
m=t+3;
while(temp[m])
{
if(temp[t]==temp[m] && temp[t+1]==temp[m+1])
{mark=1;break;}
else m+=3;
}
if(mark) break;
t+=3;
}
if(mark)
{
exist_num_1=temp[t];
exist_num_2=temp[t+1];
for(i=0;i<9;i++)
{
if(i==temp[t-1] || i==temp[m-1]) continue;
else
{
if(p[i][j][0]>1)
{
if(p[i][j][exist_num_1])
{
--p[i][j][0];
p[i][j][exist_num_1]=0;
}
if(p[i][j][exist_num_2])
{
--p[i][j][0];
p[i][j][exist_num_2]=0;
}
if(p[i][j][0]==1)
{
ensered_num=1;
flag=1;
for(k=1;k<10;k++)
{if(p[i][j][k]) break;}
if(turn) printf("显式数对法确定第%d行第%d列 为:%d\n",i+1,j+1,p[i][j][k]);
}
}
}
}
}
}
while(flag)
{flag=0;
naked_single(p,turn);
}
if(is_same) return;
for(i=0;i<3;i++)
{
box_line=i*3;
for(j=0;j<3;j++)
{
box_col=j*3;
memset(data,0,sizeof(data));
t=0;change=1;mark=0;
for(loop_a=0;loop_a<3;loop_a++)
{
this_i=box_line+loop_a;
for(loop_b=0;loop_b<3;loop_b++)
{
this_j=box_col+loop_b;
if(p[this_i][this_j][0]==2)
{
data[t]=this_i;
data[t+1]=this_j;
for(k=1;k<10;k++)
{
if(p[this_i][this_j][k])
{
if(change)
{
change=0;
data[t+2]=k;
}
else data[t+3]=k;
}
}
t+=4;change=1;
}
}
}
t=2;
while(data[t])
{
m=t+4;
while(data[m])
{
if(data[t]==data[m] && data[t+1]==data[m+1])
{mark=1;break;}
else m+=4;
}
if(mark) break;
t+=4;
}
if(mark)
{
exist_num_1=data[t];
exist_num_2=data[t+1];
for(loop_a=0;loop_a<3;loop_a++)
{now_i=box_line+loop_a;
for(loop_b=0;loop_b<3;loop_b++)
{now_j=box_col+loop_b;
if((now_i==data[t-2] && now_j==data[t-1])||(now_i==data[m-2] && now_j==data[m-1])) continue;
else
{
if(p[now_i][now_j][0]>1)
{
if(p[now_i][now_j][exist_num_1])
{
--p[now_i][now_j][0];
p[now_i][now_j][exist_num_1]=0;
}
if(p[now_i][now_j][exist_num_2])
{
--p[now_i][now_j][0];
p[now_i][now_j][exist_num_2]=0;
}
if(p[now_i][now_j][0]==1)
{
ensered_num=1;
flag=1;
for(k=1;k<10;k++)
{if(p[now_i][now_j][k]) break;}
if(turn) printf("显式数对法确定第%d行第%d列 为:%d\n",now_i+1,now_j+1,p[now_i][now_j][k]);
}
}
}
}
}
}
}
}
while(flag)
{flag=0;
naked_single(p,turn);
}
if(is_same) return;
return;
}
这是一个解17数独的过程
（17数独是数独上能存在的最少的已知数）
输入数独，一行输完后按回车确认，待确定数用‘0’代替
. . 6 | . . . | . . .
. . . | . . 7 | 1 . .
. . 1 | . . . | . . .
-----------------------------
. . . | . 2 . | . . .
. . . | 6 . . | 4 . .
7 8 . | . . . | 9 . .
-----------------------------
. . . | 4 . . | . . 2
. 5 . | . . 9 | . 3 .
3 . . | . . . | . . 6
现在开始计算
隐式唯一法确定第6行第8列 为:6
隐式唯一法确定第3行第7列 为:6
隐式唯一法确定第2行第5列 为:6
隐式唯一法确定第6行第3列 为:2
隐式唯一法确定第8行第1列 为:6
隐式唯一法确定第4行第2列 为:6
隐式唯一法确定第7行第6列 为:6
隐式唯一法确定第1行第7列 为:2
隐式唯一法确定第5行第8列 为:2
隐式唯一法确定第7行第5列 为:3
隐式唯一法确定第8行第4列 为:2
隐式唯一法确定第3行第6列 为:2
隐式唯一法确定第4行第7列 为:3
隐式唯一法确定第9行第2列 为:2
隐式唯一法确定第2行第1列 为:2
NOW Trying...假定第1行第1列 为4
Error
NOW Trying...假定第1行第1列 为5
NOW Trying...假定第1行第2列 为3
NOW Trying...假定第1行第4列 为1
Error
NOW Trying...假定第1行第4列 为8
Error
NOW Trying...假定第1行第2列 为4
NOW Trying...假定第1行第4列 为1
NOW Trying...假定第1行第5列 为8
Error
NOW Trying...假定第1行第5列 为9
Error
NOW Trying...假定第1行第4列 为8
Error
NOW Trying...假定第1行第4列 为9
Error
NOW Trying...假定第1行第2列 为7
NOW Trying...假定第1行第4列 为1
NOW Trying...假定第1行第5列 为4
NOW Trying...假定第2行第2列 为3
Error
NOW Trying...假定第2行第2列 为4
Error
NOW Trying...假定第2行第2列 为9
Error
NOW Trying...假定第1行第5列 为8
NOW Trying...假定第1行第6列 为3
Error
NOW Trying...假定第1行第6列 为4
Error
NOW Trying...假定第1行第5列 为9
NOW Trying...假定第1行第6列 为3
NOW Trying...假定第1行第8列 为4
Error
NOW Trying...假定第1行第8列 为8
Error
NOW Trying...假定第1行第6列 为4
NOW Trying...假定第2行第2列 为3
Error
NOW Trying...假定第2行第2列 为4
NOW Trying...假定第10行第10列 为1
NOW Trying...假定第2行第2列 为9
Error
NOW Trying...假定第1行第6列 为8
Error
NOW Trying...假定第1行第4列 为3
NOW Trying...假定第2行第2列 为3
NOW Trying...假定第10行第10列 为1
NOW Trying...假定第2行第2列 为4
NOW Trying...假定第10行第10列 为1
NOW Trying...假定第1行第4列 为8
NOW Trying...假定第1行第5列 为1
Error
NOW Trying...假定第1行第5列 为4
Error
NOW Trying...假定第1行第5列 为9
Error
NOW Trying...假定第1行第4列 为9
Error
NOW Trying...假定第1行第2列 为9
Error
NOW Trying...假定第1行第1列 为8
NOW Trying...假定第1行第2列 为3
Error
NOW Trying...假定第1行第2列 为4
NOW Trying...假定第2行第2列 为3
NOW Trying...假定第10行第10列 为1
NOW Trying...假定第10行第10列 为1
NOW Trying...假定第2行第2列 为9
NOW Trying...假定第10行第10列 为1
NOW Trying...假定第10行第10列 为1
NOW Trying...假定第1行第2列 为7
Error
NOW Trying...假定第1行第2列 为9
Error
NOW Trying...假定第1行第1列 为9
NOW Trying...假定第1行第2列 为3
NOW Trying...假定第1行第4列 为1
NOW Trying...假定第10行第10列 为1
NOW Trying...假定第10行第10列 为1
NOW Trying...假定第10行第10列 为1
NOW Trying...假定第1行第4列 为5
Error
NOW Trying...假定第1行第4列 为8
Error
NOW Trying...假定第1行第2列 为4
Error
NOW Trying...假定第1行第2列 为7
NOW Trying...假定第1行第4列 为1
NOW Trying...假定第1行第5列 为4
NOW Trying...假定第1行第8列 为5
Error
NOW Trying...假定第1行第8列 为8
Error
NOW Trying...假定第1行第5列 为5
NOW Trying...假定第1行第6列 为3
Error
NOW Trying...假定第1行第6列 为4
Error
NOW Trying...假定第1行第6列 为8
Error
NOW Trying...假定第1行第5列 为8
NOW Trying...假定第1行第6列 为3
Error
NOW Trying...假定第1行第6列 为4
Error
NOW Trying...假定第1行第6列 为5
Error
NOW Trying...假定第1行第4列 为3
Error
NOW Trying...假定第1行第4列 为5
NOW Trying...假定第1行第5列 为1
...DONE...
尝试的次数为77次
9 7 6 | 5 1 4 | 2 8 3
2 4 8 | 3 6 7 | 1 5 9
5 3 1 | 8 9 2 | 6 7 4
-----------------------------
4 6 5 | 9 2 8 | 3 1 7
1 9 3 | 6 7 5 | 4 2 8
7 8 2 | 1 4 3 | 9 6 5
-----------------------------
8 1 7 | 4 3 6 | 5 9 2
6 5 4 | 2 8 9 | 7 3 1
3 2 9 | 7 5 1 | 8 4 6
