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.
146 lines
2.7 KiB
146 lines
2.7 KiB
#include<stdio.h>
|
|
#include<stdlib.h>
|
|
#include<time.h>
|
|
int a[10][10]={{0,0,0,0,0,0,0,0,0,0},
|
|
{0,5, 3, 0, 0, 7, 0, 0, 0, 0},
|
|
{0,6, 0, 0, 1, 9, 5, 0, 0, 0},
|
|
{0,0, 9, 8, 0, 0, 0, 0, 6, 0},
|
|
{0,8, 0, 0, 0, 6, 0, 0, 0, 3},
|
|
{0,4, 0, 0, 8, 0, 3, 0, 0, 1},
|
|
{0,7, 0, 0, 0, 2, 0, 0, 0, 6},
|
|
{0,0, 6, 0, 0, 0, 0, 2, 8, 0},
|
|
{0,0, 0, 0, 4, 1, 9, 0, 0, 5},
|
|
{0,0, 0, 0, 0, 8, 0, 0, 7, 9}};
|
|
int e,f,g,finish=0;
|
|
void format(int s[][10])
|
|
{
|
|
printf("-------------------------\n");
|
|
for(int i=1;i<10;i++)
|
|
{
|
|
printf("| ");
|
|
for(int j=1;j<10;j++)
|
|
{
|
|
|
|
printf("%d ",s[i][j]);
|
|
if(j%3==0) printf("| ");
|
|
}
|
|
printf("\n");
|
|
if(i%3==0) printf("-------------------------\n");
|
|
}
|
|
}
|
|
bool ok(int x,int y,int s[][10])
|
|
{
|
|
int b=s[x][y];
|
|
int a1=x,a2=y;
|
|
for(int j=1;j<=9;j++)
|
|
{
|
|
if(j==y) continue;
|
|
if(s[x][j]==b)
|
|
{
|
|
e=0;f=x;g=b;
|
|
return false;
|
|
}
|
|
}
|
|
for(int i=1;i<=9;i++)
|
|
{
|
|
if(i==x) continue;
|
|
if(s[i][y]==b)
|
|
{
|
|
e=1;f=y;g=b;
|
|
return false;
|
|
}
|
|
}
|
|
x=(x-1)/3*3;
|
|
y=(y-1)/3*3;
|
|
int block;
|
|
if(x+1==1)
|
|
{
|
|
if(y+1==1) block=1;
|
|
else if(y+1==4) block=2;
|
|
else if(y+1==7) block=3;
|
|
}
|
|
else if(x+1==4)
|
|
{
|
|
if(y+1==1) block=4;
|
|
else if(y+1==4) block=5;
|
|
else if(y+1==7) block=6;
|
|
}
|
|
else if(x+1==7)
|
|
{
|
|
if(y+1==1) block=7;
|
|
else if(y+1==4) block=8;
|
|
else if(y+1==7) block=9;
|
|
}
|
|
for(int i=x+1;i<x+4;i++)
|
|
{
|
|
for(int j=y+1;j<y+4;j++)
|
|
{
|
|
if(a1==i&&a2==j) continue;
|
|
if(s[i][j]==b)
|
|
{
|
|
e=2;f=block;g=b;
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
void dfs(int x,int y,int s[][10])
|
|
{
|
|
int c=0;
|
|
if(x==10&&y==1)
|
|
{
|
|
printf("The solution of Sudoku matrix:\n");
|
|
format(s);
|
|
finish=1;
|
|
return;
|
|
}
|
|
if(y==10)dfs(x+1,1,s);
|
|
else
|
|
{
|
|
if(s[x][y]) dfs(x,y+1,s);
|
|
else
|
|
{
|
|
for(int i=1;i<=9;i++)
|
|
{
|
|
s[x][y]=i;
|
|
if(ok(x,y,s))
|
|
{
|
|
c=1;
|
|
dfs(x,y+1,s);
|
|
s[x][y]=0;
|
|
}
|
|
}
|
|
s[x][y]=0;
|
|
}
|
|
}
|
|
}
|
|
int main()
|
|
{
|
|
int d=1;
|
|
srand(time(NULL));
|
|
printf("The original Sudoku matrix:\n");
|
|
format(a);
|
|
for(int i=1;i<=9;i++)
|
|
for(int j=1;j<=9;j++)
|
|
{
|
|
if(a[i][j])
|
|
{
|
|
if(!ok(i,j,a))
|
|
{
|
|
printf("False:Invalid initial Sudoku matrix!\n");
|
|
if(e==1) printf("The number %d in the col %d has been used!",g,f);
|
|
else if(e==0) printf("The number %d in the row %d has been used!",g,f);
|
|
else if(e==2) printf("The number %d in the block %d has been used!",g,f);
|
|
return 0;
|
|
}
|
|
}
|
|
}
|
|
printf("True:Valid initial Sudoku matrix!\n");
|
|
dfs(1,1,a);
|
|
if(finish==0) printf("No solution!");
|
|
return 0;
|
|
}
|
|
|
|
|