折腾了一周时间，终于搞定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;
}
