c 解数独（通用方法，适用于9×9 数独）

折腾了一周时间，终于搞定9×9数独通用方法

思路：1.生成每行空位的值，也就是1-9中除去非0的数。

2.用行，列，宫判断每行中每个空位的最小取值范围后再重新生成每行。

3.随机提取生成的9行，判断每列之和是否等于45。

4.如9列之和都等于45则数独找到。

刚试了一下，网上的9*9数独都可用此程序解出。经验证此程序对提示比较多的数独非常有效，对只有少量提示的数独运算量非常大，运算时间会很长。

对于提示很少的数独，要把生成的行数的下标改大，如1000。运算时间很长。

此程序的亮点是用struct表示空位的各种参数，以及生成各种二维，三维数组，以及各种循环判断。

灵活运用数组和struct,对于相同类型的数据用数组，如要存储不同类型的数据用struct.

 

程序：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>int main(void) {//判断len长的数组是否有相同元素int pd(int *i,int len) {           int n = 0;for (int a = 0; a < len; a++) {for (int b = a + 1; b <len ; b++) {if (i[a] == i[b]) {n = -1;goto aa;}}}n = 1;aa:return n;}//9位int数组中每位非空元素的值与下标int cxf0(int *i,int len,int (*o)[2]){int n=0;for(int a=0;a<len;a++){if(i[a]!=0){o[n][0]=a;o[n][1]=i[a];n++;}}return n;}//9位int 数组中所有空 元素取值范围int cxfw(int *i,int *o){int ls[]={1,2,3,4,5,6,7,8,9};for(int a=0;a<9;a++){if(i[a]!=0){ls[i[a]-1]=0;}}int n=0;for(int a=0;a<9;a++){if(ls[a]!=0){o[n]=ls[a];n++;}}return n;}//提取三个int 数组中相同的元素（也就是每位空元素的可能取值范围）int xt(int *i1,int *i2,int *i3,int len1,int len2,int len3,int *o){int n=0;int ls[9]={};for(int a=0;a<len1;a++){for(int b=0;b<len2;b++){if(i1[a]==i2[b]){ls[n]=i1[a];	n++;}}}int x=0;for(int a=0;a<n;a++){for(int b=0;b<len3;b++){if(ls[a]==i3[b]){o[x]=ls[a];	x++;}}}return x;}int s[9][9] = {{5, 3, 0,   0, 7, 0,   0, 0, 0},{6, 0, 0,   1, 9, 5,   0, 0, 0},{0, 9, 8,   0, 0, 0,   0, 6, 0},{8, 0, 0,   0, 6, 0,   0, 0, 3},{4, 0, 0,   8, 0, 3,   0, 0, 1},{7, 0, 0,   0, 2, 0,   0, 0, 6},{0, 6, 0,   0, 0, 0,   2, 8, 0},{0, 0, 0,   4, 1, 9,   0, 0, 5},{0, 0, 0,   0, 8, 0,   0, 7, 9}};int ls[9]={};//---------------------------------//每宫空元素的可能值int g0[9]={};memset(ls,0,36);ls[0]=s[0][0],ls[1]=s[0][1],ls[2]=s[0][2],ls[3]=s[1][0],ls[4]=s[1][1],ls[5]=s[1][2],ls[6]=s[2][0],ls[7]=s[2][1],ls[8]=s[2][2];int ng0=cxfw(ls,g0);int g1[9]={};memset(ls,0,36);ls[0]=s[0][3],ls[1]=s[0][4],ls[2]=s[0][5],ls[3]=s[1][3],ls[4]=s[1][4],ls[5]=s[1][5],ls[6]=s[2][3],ls[7]=s[2][4],ls[8]=s[2][5];int ng1=cxfw(ls,g1);int g2[9]={};memset(ls,0,36);ls[0]=s[0][6],ls[1]=s[0][7],ls[2]=s[0][8],ls[3]=s[1][6],ls[4]=s[1][7],ls[5]=s[1][8],ls[6]=s[2][6],ls[7]=s[2][7],ls[8]=s[2][8];int ng2=cxfw(ls,g2);int g3[9]={};memset(ls,0,36);ls[0]=s[3][0],ls[1]=s[3][1],ls[2]=s[3][2],ls[3]=s[4][0],ls[4]=s[4][1],ls[5]=s[4][2],ls[6]=s[5][0],ls[7]=s[5][1],ls[8]=s[5][2];int ng3=cxfw(ls,g3);int g4[9]={};memset(ls,0,36);ls[0]=s[3][3],ls[1]=s[3][4],ls[2]=s[3][5],ls[3]=s[4][3],ls[4]=s[4][4],ls[5]=s[4][5],ls[6]=s[5][3],ls[7]=s[5][4],ls[8]=s[5][5];int ng4=cxfw(ls,g4);int g5[9]={};memset(ls,0,36);ls[0]=s[3][6],ls[1]=s[3][7],ls[2]=s[3][8],ls[3]=s[4][6],ls[4]=s[4][7],ls[5]=s[4][8],ls[6]=s[5][6],ls[7]=s[5][7],ls[8]=s[5][8];int ng5=cxfw(ls,g5);int g6[9]={};memset(ls,0,36);ls[0]=s[6][0],ls[1]=s[6][1],ls[2]=s[6][2],ls[3]=s[7][0],ls[4]=s[7][1],ls[5]=s[7][2],ls[6]=s[8][0],ls[7]=s[8][1],ls[8]=s[8][2];int ng6=cxfw(ls,g6);int g7[9]={};memset(ls,0,36);ls[0]=s[6][3],ls[1]=s[6][4],ls[2]=s[6][5],ls[3]=s[7][3],ls[4]=s[7][4],ls[5]=s[7][5],ls[6]=s[8][3],ls[7]=s[8][4],ls[8]=s[8][5];int ng7=cxfw(ls,g7);int g8[9]={};memset(ls,0,36);ls[0]=s[6][6],ls[1]=s[6][7],ls[2]=s[6][8],ls[3]=s[7][6],ls[4]=s[7][7],ls[5]=s[7][8],ls[6]=s[8][6],ls[7]=s[8][7],ls[8]=s[8][8];int ng8=cxfw(ls,g8);int zg[9][9]={};memcpy(&(zg[0][0]),g0,36);memcpy(&(zg[1][0]),g1,36);memcpy(&(zg[2][0]),g2,36);memcpy(&(zg[3][0]),g3,36);memcpy(&(zg[4][0]),g4,36);memcpy(&(zg[5][0]),g5,36);memcpy(&(zg[6][0]),g6,36);memcpy(&(zg[7][0]),g7,36);memcpy(&(zg[8][0]),g8,36);int zng[9]={ng0,ng1,ng2,ng3,ng4,ng5,ng6,ng7,ng8};//--------------------------------------------------------//数独9行中每行的空元素的可能值int h0[9]={};             //第一行空位每位的可能值memcpy(ls,&(s[0][0]),36);int nh0=cxfw(ls,h0);        //空位个数int h1[9]={};             //第二行空位每位的可能值memset(ls,0,36);memcpy(ls,&(s[1][0]),36);int nh1=cxfw(ls,h1);        //空位个数int h2[9]={};             memset(ls,0,36);memcpy(ls,&(s[2][0]),36);int nh2=cxfw(ls,h2);        int h3[9]={};            memset(ls,0,36);memcpy(ls,&(s[3][0]),36);int nh3=cxfw(ls,h3);        int h4[9]={};            memset(ls,0,36);memcpy(ls,&(s[4][0]),36);int nh4=cxfw(ls,h4);int h5[9]={};            memset(ls,0,36);memcpy(ls,&(s[5][0]),36);int nh5=cxfw(ls,h5);int h6[9]={};            memset(ls,0,36);memcpy(ls,&(s[6][0]),36);int nh6=cxfw(ls,h6);int h7[9]={};            memset(ls,0,36);memcpy(ls,&(s[7][0]),36);int nh7=cxfw(ls,h7);int h8[9]={};            memset(ls,0,36);memcpy(ls,&(s[8][0]),36);int nh8=cxfw(ls,h8);int zh[9][9]={};memcpy(&(zh[0][0]),h0,36);memcpy(&(zh[1][0]),h1,36);memcpy(&(zh[2][0]),h2,36);memcpy(&(zh[3][0]),h3,36);memcpy(&(zh[4][0]),h4,36);memcpy(&(zh[5][0]),h5,36);memcpy(&(zh[6][0]),h6,36);memcpy(&(zh[7][0]),h7,36);memcpy(&(zh[8][0]),h8,36);int znh[9]={nh0,nh1,nh2,nh3,nh4,nh5,nh6,nh7,nh8};//每列空元素的可能值int s0[9]={};memset(ls,0,36);for(int a=0;a<9;a++){ls[a]=s[a][0];}int ns0=cxfw(ls,s0);int s1[9]={};memset(ls,0,36);for(int a=0;a<9;a++){ls[a]=s[a][1];}int ns1=cxfw(ls,s1);int s2[9]={};memset(ls,0,36);for(int a=0;a<9;a++){ls[a]=s[a][2];}int ns2=cxfw(ls,s2);int s3[9]={};memset(ls,0,36);for(int a=0;a<9;a++){ls[a]=s[a][3];}int ns3=cxfw(ls,s3);int s4[9]={};memset(ls,0,36);for(int a=0;a<9;a++){ls[a]=s[a][4];}int ns4=cxfw(ls,s4);int s5[9]={};memset(ls,0,36);for(int a=0;a<9;a++){ls[a]=s[a][5];}int ns5=cxfw(ls,s5);int s6[9]={};memset(ls,0,36);for(int a=0;a<9;a++){ls[a]=s[a][6];}int ns6=cxfw(ls,s6);int s7[9]={};memset(ls,0,36);for(int a=0;a<9;a++){ls[a]=s[a][7];}int ns7=cxfw(ls,s7);int s8[9]={};memset(ls,0,36);for(int a=0;a<9;a++){ls[a]=s[a][8];}int ns8=cxfw(ls,s8);int zs[9][9]={};memcpy(&(zs[0][0]),s0,36);memcpy(&(zs[1][0]),s1,36);memcpy(&(zs[2][0]),s2,36);memcpy(&(zs[3][0]),s3,36);memcpy(&(zs[4][0]),s4,36);memcpy(&(zs[5][0]),s5,36);memcpy(&(zs[6][0]),s6,36);memcpy(&(zs[7][0]),s7,36);memcpy(&(zs[8][0]),s8,36);int zns[9]={ns0,ns1,ns2,ns3,ns4,ns5,ns6,ns7,ns8};//-------------------------------------------------struct SD{int f0;int xb;int len;int fw[9];	};typedef struct SD sd;sd ss[9][9]={};              //9×9 数独81位的可能范围最小取值（已行，列，宫三方判定）for(int a=0;a<9;a++){        // 循环9行for(int b=0;b<9;b++){    //循环9列if(s[a][b]!=0){        //非空位ss[a][b].f0=1;ss[a][b].xb=b;ss[a][b].len=1;ss[a][b].fw[0]=s[a][b];}                                //下面是处理空位if((s[a][b]==0)&&(a<3)&&(b<3)){     //宫0 9位中的空位ss[a][b].f0=0;ss[a][b].xb=b;int lsh[9]={};memcpy(lsh,&(zh[a][0]),36);int lshn=znh[a];int lss[9]={};memcpy(lss,&(zs[b][0]),36);int lssn=zns[b];int o[9]={};ss[a][b].len=xt(lsh,lss,g0,lshn,lssn,ng0,o);memcpy(&(ss[a][b].fw[0]),o,ss[a][b].len*4);}if((s[a][b]==0)&&(a<3)&&(b<6)&&(b>=3)){    //宫1的9位中的空位ss[a][b].f0=0;ss[a][b].xb=b;int lsh[9]={};memcpy(lsh,&(zh[a][0]),36);int lshn=znh[a];int lss[9]={};memcpy(lss,&(zs[b][0]),36);int lssn=zns[b];int o[9]={};ss[a][b].len=xt(lsh,lss,g1,lshn,lssn,ng1,o);memcpy(&(ss[a][b].fw),o,ss[a][b].len*4);}if((s[a][b]==0)&&(a<3)&&(b>=6)){        //宫2的9位中的空位ss[a][b].f0=0;ss[a][b].xb=b;int lsh[9]={};memcpy(lsh,&(zh[a][0]),36);int lshn=znh[a];int lss[9]={};memcpy(lss,&(zs[b][0]),36);int lssn=zns[b];int o[9]={};ss[a][b].len=xt(lsh,lss,g2,lshn,lssn,ng2,o);memcpy(&(ss[a][b].fw),o,ss[a][b].len*4);	}if((s[a][b]==0)&&(a>=3)&&(a<6)&&(b<3)){        //宫3的9位中的空位--------------ss[a][b].f0=0;ss[a][b].xb=b;int lsh[9]={};memcpy(lsh,&(zh[a][0]),36);int lshn=znh[a];int lss[9]={};memcpy(lss,&(zs[b][0]),36);int lssn=zns[b];int o[9]={};ss[a][b].len=xt(lsh,lss,g3,lshn,lssn,ng3,o);memcpy(&(ss[a][b].fw),o,ss[a][b].len*4);	}if((s[a][b]==0)&&(a>=3)&&(a<6)&&(b>=3)&&(b<6)){        //宫4的9位中的空位ss[a][b].f0=0;ss[a][b].xb=b;int lsh[9]={};memcpy(lsh,&(zh[a][0]),36);int lshn=znh[a];int lss[9]={};memcpy(lss,&(zs[b][0]),36);int lssn=zns[b];int o[9]={};ss[a][b].len=xt(lsh,lss,g4,lshn,lssn,ng4,o);memcpy(&(ss[a][b].fw),o,ss[a][b].len*4);	}if((s[a][b]==0)&&(a>=3)&&(a<6)&&(b>=6)){        //宫5的9位中的空位ss[a][b].f0=0;ss[a][b].xb=b;int lsh[9]={};memcpy(lsh,&(zh[a][0]),36);int lshn=znh[a];int lss[9]={};memcpy(lss,&(zs[b][0]),36);int lssn=zns[b];int o[9]={};ss[a][b].len=xt(lsh,lss,g5,lshn,lssn,ng5,o);memcpy(&(ss[a][b].fw),o,ss[a][b].len*4);	}if((s[a][b]==0)&&(a>=6)&&(b<3)){        //宫6的9位中的空位ss[a][b].f0=0;ss[a][b].xb=b;int lsh[9]={};memcpy(lsh,&(zh[a][0]),36);int lshn=znh[a];int lss[9]={};memcpy(lss,&(zs[b][0]),36);int lssn=zns[b];int o[9]={};ss[a][b].len=xt(lsh,lss,g6,lshn,lssn,ng6,o);memcpy(&(ss[a][b].fw),o,ss[a][b].len*4);	}if((s[a][b]==0)&&(a>=6)&&(b>=3)&&(b<6)){        //宫7的9位中的空位ss[a][b].f0=0;ss[a][b].xb=b;int lsh[9]={};memcpy(lsh,&(zh[a][0]),36);int lshn=znh[a];int lss[9]={};memcpy(lss,&(zs[b][0]),36);int lssn=zns[b];int o[9]={};ss[a][b].len=xt(lsh,lss,g7,lshn,lssn,ng7,o);memcpy(&(ss[a][b].fw),o,ss[a][b].len*4);	}if((s[a][b]==0)&&(a>=6)&&(b>=6)){        //宫8的9位中的空位ss[a][b].f0=0;ss[a][b].xb=b;int lsh[9]={};memcpy(lsh,&(zh[a][0]),36);int lshn=znh[a];int lss[9]={};memcpy(lss,&(zs[b][0]),36);int lssn=zns[b];int o[9]={};ss[a][b].len=xt(lsh,lss,g8,lshn,lssn,ng8,o);memcpy(&(ss[a][b].fw),o,ss[a][b].len*4);	}}}
//-----数独每行的可能值-------------------------------------------------------------------------------------------int zo[9][100][9]={};        //9行，每行可能的范围最小的排列，第一个9代表9行序号 100代表每行最多有100种可能，最后的9代表每行的9位数int nn[9]={};for(int a=0;a<9;a++){          //9行循环int nx=0;for(int a0=0;a0<ss[a][0].len;a0++){      //每行的9列循环for(int a1=0;a1<ss[a][1].len;a1++){for(int a2=0;a2<ss[a][2].len;a2++){for(int a3=0;a3<ss[a][3].len;a3++){for(int a4=0;a4<ss[a][4].len;a4++){for(int a5=0;a5<ss[a][5].len;a5++){for(int a6=0;a6<ss[a][6].len;a6++){for(int a7=0;a7<ss[a][7].len;a7++){for(int a8=0;a8<ss[a][8].len;a8++){int z[]={ss[a][0].fw[a0],ss[a][1].fw[a1],ss[a][2].fw[a2],ss[a][3].fw[a3],ss[a][4].fw[a4],ss[a][5].fw[a5],ss[a][6].fw[a6],ss[a][7].fw[a7],ss[a][8].fw[a8]};if(pd(z,9)>0){memcpy(&(zo[a][nx][0]),z,36);nx++;}}}}}}}}}}nn[a]=nx;}/*	   for(int b=0;b<9;b++){printf("%d ;",zo[7][0][b]);}*/   int wzo[9][9]={};//int zo[9][100][9]={};for(int q0=0;q0<nn[0];q0++){for(int q1=0;q1<nn[1];q1++){for(int q2=0;q2<nn[2];q2++){for(int q3=0;q3<nn[3];q3++){for(int q4=0;q4<nn[4];q4++){for(int q5=0;q5<nn[5];q5++){for(int q6=0;q6<nn[6];q6++){for(int q7=0;q7<nn[7];q7++){for(int q8=0;q8<nn[8];q8++){int s0[9],s1[9],s2[9],s3[9],s4[9],s5[9],s6[9],s7[9],s8[9];memcpy(s0,&(zo[0][q0][0]),36);memcpy(s1,&(zo[1][q1][0]),36);memcpy(s2,&(zo[2][q2][0]),36);memcpy(s3,&(zo[3][q3][0]),36);memcpy(s4,&(zo[4][q4][0]),36);memcpy(s5,&(zo[5][q5][0]),36);memcpy(s6,&(zo[6][q6][0]),36);memcpy(s7,&(zo[7][q7][0]),36);memcpy(s8,&(zo[8][q8][0]),36);if((    s0[0]+s1[0]+s2[0]+s3[0]+s4[0]+s5[0]+s6[0]+s7[0]+s8[0]==45)&&(s0[1]+s1[1]+s2[1]+s3[1]+s4[1]+s5[1]+s6[1]+s7[1]+s8[1]==45)&&(s0[2]+s1[2]+s2[2]+s3[2]+s4[2]+s5[2]+s6[2]+s7[2]+s8[2]==45)&&(s0[3]+s1[3]+s2[3]+s3[3]+s4[3]+s5[3]+s6[3]+s7[3]+s8[3]==45)&&(s0[4]+s1[4]+s2[4]+s3[4]+s4[4]+s5[4]+s6[4]+s7[4]+s8[4]==45)&&(s0[5]+s1[5]+s2[5]+s3[5]+s4[5]+s5[5]+s6[5]+s7[5]+s8[5]==45)&&(s0[6]+s1[6]+s2[6]+s3[6]+s4[6]+s5[6]+s6[6]+s7[6]+s8[6]==45)&&(s0[7]+s1[7]+s2[7]+s3[7]+s4[7]+s5[7]+s6[7]+s7[7]+s8[7]==45)&&(s0[8]+s1[8]+s2[8]+s3[8]+s4[8]+s5[8]+s6[8]+s7[8]+s8[8]==45)){memcpy(&(wzo[0][0]),s0,36);memcpy(&(wzo[1][0]),s1,36);memcpy(&(wzo[2][0]),s2,36);memcpy(&(wzo[3][0]),s3,36);memcpy(&(wzo[4][0]),s4,36);memcpy(&(wzo[5][0]),s5,36);memcpy(&(wzo[6][0]),s6,36);memcpy(&(wzo[7][0]),s7,36);memcpy(&(wzo[8][0]),s8,36);}}}}}}}}}}for(int a=0;a<9;a++){for(int b=0;b<9;b++){printf("%d ,",wzo[a][b]);}puts("");}  return 0;}