#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;
int number=0;
void randomquene(int array[], int len) 
{
    srand(time(NULL));
    for (int i=len-1;i>0;i--) 
	{
        int j=rand()%(i+1);
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }
}
void randomputs(int array[],int len)
{
	for(int row=1;row<10;row++)
	{
		int k=1;
		while(k<4)
		{
			int col=rand()%9+1;
			if(a[row][col]==0)
			{
			    a[row][col]=array[number];
			    number++;
			    k++;
			}
		}
		if(row%3==0)
		{
			number=0;
			randomquene(array,len);
		}
	}
}
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,i;
	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(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));
    /*
	int array[]={1, 2, 3, 4, 5, 6, 7, 8, 9};
    int len=sizeof(array)/sizeof(array[0]);
    randomquene(array,len);
    randomputs(array,len);
	*/
    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;
}