数独求解算法

/***********************************************************************************************************************/ /*********************************************************************************************************************** 作者 : 熊 能 2014年01月08号 QQ:1157052375 邮箱:xiongneng_0204@sina.cn 此算法有BUG可能是解决有唯一解的那种数独 方法Detection_JiuGongGe()有问题 ***********************************************************************************************************************/ #include<stdio.h> void Input_ShuDu(); void Traverse_ShuDu(); void Update_ShuDu(int x,int y); void Output_ShuDu(); int Detection_JiuGongGe(); int Detection_Hang(); int Detection_Lie(); void Output_y1(); void Output_y2(); void Output_y3(); int a[9][9]={ {0,0,0, 0,0,3, 0,0,0}, {0,4,8, 5,0,0, 0,9,0}, {2,9,0, 7,0,0, 0,3,6}, {9,0,4, 1,0,7, 0,6,2}, {0,0,2, 0,0,0, 3,0,0}, {8,1,0, 3,0,2, 7,0,9}, {1,5,0, 0,0,9, 0,4,8}, {0,2,0, 0,0,8, 9,7,0}, {0,0,0, 6,0,0, 0,0,0} },y0[9],y1[3][3][9],y2[9][9],y3[9][9],y4[9][9],count; int main(){ printf("**************************************\n"); Input_ShuDu(); printf("**************************************\n"); Output_ShuDu(); printf("**************************************\n"); /* printf("\n %d , %d ,%d\n",Detection_JiuGongGe(),Detection_Hang(),Detection_Lie()); if( Detection_JiuGongGe() & Detection_Hang() & Detection_Lie()){ */ while(1){ Traverse_ShuDu(); if(count==0)break; } /* }else{ printf(" 您输入的数独无解！"); } printf("**************************************\n"); Output_y1(); printf("**************************************\n"); Output_y2(); printf("**************************************\n"); Output_y3(); */ Output_ShuDu(); return 0; } void Traverse_ShuDu(){ int i,j;count=0; for(i=0;i<9;i++){ for(j=0;j<9;j++){ if(a[i][j]==0){ Update_ShuDu(i,j); count++; } } } } void Update_ShuDu(int x,int y){ int i,temp,n=0; for(i=0;i<9;i++){ y0[i] = y1[x/3][y/3][i] | y2[x][i] | y3[y][i]; if(y0[i]==1){ n++; }else{ temp=i+1; } } if(n==8){ a[x][y]=temp; y1[x/3][y/3][a[x][y]-1]=1; y2[x][a[x][y]-1]=1; y3[y][a[x][y]-1]=1; //printf("a[%d][%d]=%d ",x+1,y+1,a[x][y]); } } void Input_ShuDu(){ int i,j; for(i=0;i<9;i++){ for(j=0;j<9;j++){ if(a[i][j]!=0){ y1[i/3][j/3][a[i][j]-1]=1; y2[i][a[i][j]-1]=1; y3[j][a[i][j]-1]=1; y4[i][j]=1; }else{ y4[i][j]=0; } } } } void Output_ShuDu(){ int i,j; for(i=0;i<9;i++){ if(i%3==0)printf("\n "); for(j=0;j<9;j++){ if(j%3==0)printf(" "); printf("%d ",a[i][j]); } printf("\n "); } printf("\n"); } int Detection_JiuGongGe(){ int i; for(i=0;i<9;i++){ if( !((y1[i/3][i%3][0]+y1[i/3][i%3][1]+y1[i/3][i%3][2]+y1[i/3][i%3][3]+y1[i/3][i%3][4]+y1[i/3][i%3][5]+y1[i/3][i%3][6]+y1[i/3][i%3][7]+y1[i/3][i%3][8]) == (y4[i/3+0][i%3+0]+y4[i/3+0][i%3+1]+y4[i/3+0][i%3+2]+ y4[i/3+1][i%3+0]+y4[i/3+1][i%3+1]+y4[i/3+1][i%3+2]+ y4[i/3+2][i%3+0]+y4[i/3+2][i%3+1]+y4[i/3+2][i%3+2])) ) return 0; } return 1; } int Detection_Hang(){ int i; for(i=0;i<9;i++){ if( !((y2[i][0]+y2[i][1]+y2[i][2]+y2[i][3]+y2[i][4]+y2[i][5]+y2[i][6]+y2[i][7]+y2[i][8]) == (y4[i][0]+y4[i][1]+y4[i][2]+y4[i][3]+y4[i][4]+y4[i][5]+y4[i][6]+y4[i][7]+y4[i][8])) ) return 0; } return 1; } int Detection_Lie(){ int i; for(i=0;i<9;i++){ if( !((y3[i][0]+y3[i][1]+y3[i][2]+y3[i][3]+y3[i][4]+y3[i][5]+y3[i][6]+y3[i][7]+y3[i][8]) == (y4[0][i]+y4[1][i]+y4[2][i]+y4[3][i]+y4[4][i]+y4[5][i]+y4[6][i]+y4[7][i]+y4[8][i])) ) return 0; } return 1; } void Output_y1(){ int i,j,k; printf("y1:\n"); for(i=0;i<3;i++){ for(j=0;j<3;j++){ for(k=0;k<9;k++){ if(k%3==0)printf(" "); printf("%d ",y1[i][j][k]); } printf("\n"); } printf("\n"); } } void Output_y2(){ int i,j; printf("y2:\n"); for(i=0;i<9;i++){ if(i%3==0)printf("\n"); for(j=0;j<9;j++){ if(j%3==0)printf(" "); printf("%d ",y2[i][j]); } printf("\n"); } } void Output_y3(){ int i,j; printf("y3:\n"); for(i=0;i<9;i++){ if(i%3==0)printf("\n"); for(j=0;j<9;j++){ if(j%3==0)printf(" "); printf("%d ",y3[i][j]); } printf("\n"); } }