You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
223 lines
3.9 KiB
223 lines
3.9 KiB
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <time.h>
|
|
void shuchu(int a[9][9]){
|
|
for(int i=0;i<9;i++){
|
|
if(i%3==0){
|
|
printf("|");
|
|
for(int j=0;j<23;j++){
|
|
printf("-");
|
|
}
|
|
printf("|\n");
|
|
}
|
|
for(int j=0;j<9;j++){
|
|
if(j%3==0) printf("| ");
|
|
printf("%d ",a[i][j]);
|
|
if(j==8) printf("| ");
|
|
}
|
|
printf("\n");
|
|
if(i==8){
|
|
printf("|");
|
|
for(int j=0;j<23;j++){
|
|
printf("-");
|
|
}
|
|
printf("|");
|
|
}
|
|
}
|
|
printf("\n");
|
|
}
|
|
|
|
void MakeRand(int arr[],int count){
|
|
srand((unsigned int)time(NULL));
|
|
for (int i = 0; i<count; i++)
|
|
{
|
|
int num = i + rand() % (count - i);
|
|
int temp = arr[i];
|
|
arr[i] = arr[num];
|
|
arr[num] = temp;
|
|
}
|
|
}
|
|
|
|
int shudu(int a[9][9]){
|
|
int flag=0;
|
|
int z=0;
|
|
int i,j,k,l;
|
|
int count[10]={0};
|
|
int m[9];
|
|
for(i=0;i<9;i++){
|
|
int count[10]={0};
|
|
for(j=0;j<9;j++){
|
|
if(a[i][j]!=0) count[a[i][j]]++;
|
|
}
|
|
for(j=0;j<9;j++){
|
|
if(count[j+1]>=2){
|
|
flag=1;
|
|
z=j+1;
|
|
break;
|
|
}
|
|
}
|
|
if(flag==1) break;
|
|
}
|
|
if(flag==1){
|
|
return 0;
|
|
}
|
|
for(i=0;i<9;i++){
|
|
int count[10]={0};
|
|
for(j=0;j<9;j++){
|
|
if(a[j][i]!=0) count[a[j][i]]++;
|
|
}
|
|
for(j=0;j<9;j++){
|
|
if(count[j+1]>=2){
|
|
flag=1;
|
|
z=j+1;
|
|
break;
|
|
}
|
|
}
|
|
if(flag==1) break;
|
|
}
|
|
if(flag==1){
|
|
return 0;
|
|
}
|
|
for(i=0;i<3;i++){
|
|
for(j=0;j<3;j++){
|
|
for(k=0;k<3;k++){
|
|
for(l=0;l<3;l++){
|
|
m[k*3+l]=a[j*3+k][i*3+l];
|
|
}
|
|
}
|
|
for(k=0;k<9;k++) count[k]=0;
|
|
for(k=0;k<9;k++){
|
|
if(m[k]!=0) count[m[k]]++;
|
|
}
|
|
for(k=0;k<9;k++){
|
|
if(count[k]>=2){
|
|
flag=1;
|
|
z=k;
|
|
break;
|
|
}
|
|
}
|
|
if(flag==1) break;
|
|
}
|
|
if(flag==1) break;
|
|
}
|
|
if(flag==1){
|
|
return 0;
|
|
}
|
|
return 1;
|
|
}
|
|
|
|
void pd(int a[9][9]){
|
|
int flag=0;
|
|
int z=0;
|
|
int i,j,k,l;
|
|
int count[10]={0};
|
|
int m[9];
|
|
for(i=0;i<9;i++){
|
|
int count[10]={0};
|
|
for(j=0;j<9;j++){
|
|
if(a[i][j]!=0) count[a[i][j]]++;
|
|
}
|
|
for(j=0;j<9;j++){
|
|
if(count[j+1]>=2){
|
|
flag=1;
|
|
z=j+1;
|
|
break;
|
|
}
|
|
}
|
|
if(flag==1) break;
|
|
}
|
|
if(flag==1){
|
|
printf("False:Invalid initial Sudoku matrix!\nThe number %d in the row %d has been used!",z,i+1);
|
|
return ;
|
|
}
|
|
for(i=0;i<9;i++){
|
|
int count[10]={0};
|
|
for(j=0;j<9;j++){
|
|
if(a[j][i]!=0) count[a[j][i]]++;
|
|
}
|
|
for(j=0;j<9;j++){
|
|
if(count[j+1]>=2){
|
|
flag=1;
|
|
z=j+1;
|
|
break;
|
|
}
|
|
}
|
|
if(flag==1) break;
|
|
}
|
|
if(flag==1){
|
|
printf("False:Invalid initial Sudoku matrix!\nThe number %d in the col %d has been used!",z,i+1);
|
|
return ;
|
|
}
|
|
for(i=0;i<3;i++){
|
|
for(j=0;j<3;j++){
|
|
for(k=0;k<3;k++){
|
|
for(l=0;l<3;l++){
|
|
m[k*3+l]=a[j*3+k][i*3+l];
|
|
}
|
|
}
|
|
for(k=0;k<9;k++) count[k]=0;
|
|
for(k=0;k<9;k++){
|
|
if(m[k]!=0) count[m[k]]++;
|
|
}
|
|
for(k=0;k<9;k++){
|
|
if(count[k]>=2){
|
|
flag=1;
|
|
z=k;
|
|
break;
|
|
}
|
|
}
|
|
if(flag==1) break;
|
|
}
|
|
if(flag==1) break;
|
|
}
|
|
if(flag==1){
|
|
printf("False:Invalid initial Sudoku matrix!\nThe number %d in the block %d has been used!",z,i+1);
|
|
return ;
|
|
}
|
|
else printf("True:Valid initial Sudoku matrix!");
|
|
}
|
|
|
|
|
|
void dg(int x,int y,int a[9][9])
|
|
{
|
|
if(x==9){
|
|
printf("The solution of Sudoku matrix:\n");
|
|
shuchu(a);
|
|
return;
|
|
}
|
|
if(y==9)dg(x+1,0,a);
|
|
else
|
|
{
|
|
if(a[x][y])dg(x,y+1,a);
|
|
else{
|
|
for(int i=1;i<=9;i++)
|
|
{
|
|
a[x][y]=i;
|
|
if(shudu(a))
|
|
{
|
|
dg(x,y+1,a);
|
|
a[x][y]=0;
|
|
}
|
|
}
|
|
a[x][y]=0;
|
|
}
|
|
}
|
|
}
|
|
|
|
int main(){
|
|
int board0[9][9] = {{5, 2, 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}};
|
|
|
|
pd(board0);
|
|
printf("\n");
|
|
dg(0,0,board0);
|
|
|
|
}
|