#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
void b(int board[][9])
{
	printf("|-----------------------|\n");
for(int i=0;i<=8;i++)
{
	printf("| ");
	for(int j=0;j<=8;j++)
	{
		printf("%d ",board[i][j]);
		if(j==2||j==5)
		printf("| ");
	}
	printf("|\n");
	if(i==2||i==5)
	printf("|-----------------------|\n");
}
printf("|-----------------------|\n");
}
void bb(int board[][9])
{
	srand(time(NULL));
	int board[9][9]={0};
	for(int i=1;i<=9;i++)
	{
		int x,y;
	while(1)
	{
		
		x=rand()%10;
		y=rand()%10;
		
		if((x>=0&&x<=2)&&(y>=0&&y<=8))
		{
			int a=0;
			for(int j=0;j<=8;j++)
			{
				if(board[x][j]!=0)
				a++;
			}
			if(a<3&&board[x][y]==0)
			{
			board[x][y]=i;
            break;
		    }
		}
	}
    }
    for(int i=1;i<=9;i++)
	{
		int x,y;
	while(1)
	{
		
		x=rand()%10;
		y=rand()%10;
		

		if((x>=3&&x<=5)&&(y>=0&&y<=8))
		{
			int a=0;
			for(int j=0;j<=8;j++)
			{
				if(board[x][j]!=0)
				a++;
			}
			if(a<3&&board[x][y]==0)
			{
			board[x][y]=i;
			break;
		}
		}
	}
}
for(int i=1;i<=9;i++)
	{
		int x,y;
	while(1)
	{
		
		x=rand()%10;
		y=rand()%10;
		if((x>=6&&x<=8)&&(y>=0&&y<=8))
		{
			int a=0;
			for(int j=0;j<=8;j++)
			{
				if(board[x][j]!=0)
				a++;
			}
			if(a<3&&board[x][y]==0)
			{
			board[x][y]=i;
			break;
		}
		}
	}
}
	b(board);
    
}
int w(int board[][9])
{
	int judge=0;
	flag1:
	if(judge==0)
	{
	for(int i=0;i<9;i++)
	{
		for(int j=0;j<9;j++)
		{
			if(board[i][j]!=0)
			{
				for(int m=0;m<9;m++)
				{
					if(board[i][m]==board[i][j]&&m!=j)
					{
						judge=1;
						goto flag1;
					}
				}
			}
		}
	}
    }
    flag2:
	if(judge==0)
	{
		for(int i=0;i<9;i++)
    	{
		for(int j=0;j<9;j++)
		{
			if(board[j][i]!=0)
			{
				for(int m=0;m<9;m++)
				{
					if(board[m][i]==board[j][i]&&m!=j)
					{
						judge=1;
						goto flag2;
					}
				}
			}
		}
    	}
	}
	flag3:
	if(judge==0)
	{
		for(int i=0;i<=6;i=i+3)
		{
			for(int j=0;j<=6;j=j+3)
			{
				for(int x=i;x<i+3;x++)
				{
					for(int y=j;y<j+3;y++)
					{
						if(board[x][y]!=0)
						{
							for(int m=i;m<i+3;m++)
							{
								for(int n=j;n<j+3;n++)
								{
									if(board[m][n]==board[x][y]&&(m!=x||n!=y))
									{
										judge=1;
										goto flag3;
									}
								}
							}
						}
					}
				}
			}
		}
	}
	return judge;
}
void ww(int board1[][9])
{
	int u=1;
	flag:
	if(u=1)
	{
	int d=0,e=0,f=0;
	for(int i=0;i<=8;i++)
	{
	int c[9]={0};
	for(int j=0;j<=8;j++)
	{
		for(int k=1;k<=9;k++)
		{
		if(board1[i][j]==k)
		c[k-1]++;
		if(c[k-1]>1)
		{
			d=1;
			printf("False:Invalid initial Sudoku matrix!");
			printf("The number %d in the col %d has been used!",k,i+1);
			break;
		}
	    }
	    if(d==1)
	    break;
	}
	
	if(d==1)
	break;
    }
if(d==1)
{
	u=0;
	goto flag;
}
	for(int i=0;i<=8;i++)
	{
	int c[9]={0};
	for(int j=0;j<=8;j++)
	{
		for(int k=1;k<=9;k++)
		{
		if(board1[j][i]==k)
		c[k-1]++;
		if(c[k-1]>1)
		{
			e=1;
			printf("False:Invalid initial Sudoku matrix!");
			printf("The number %d in the row %d has been used!",k,i+1);
			break;
		}
	    }
	    if(e==1)
	    break;
	}
	if(e==1)
	break;
    }
    if(e==1)
    {
    	u=0;
    	goto flag;
	}
	for(int i=0;i<=6;i=i+3)
	{
		for(int j=0;j<=6;j=j+3)
		{
			int r;
			if(i==0&&j==0)
			r=1;
			if(i==0&&j==3)
			r=2;
			if(i==0&&j==6)
			r=3;
			if(i==3&&j==0)
			r=4;
			if(i==3&&j==3)
			r=5;
			if(i==3&&j==6)
			r=6;
			if(i==6&&j==0)
			r=7;
			if(i==6&&j==3)
			r=8;
			if(i==6&&j==6)
			r=9;
			int c[9]={0};
			for(int g=i;g<=i+2;g++)
			{
				
				for(int h=j;h<=j+2;h++)
				{
					for(int k=1;k<=9;k++)
					{
						if(board1[g][h]==k)
						{
							c[k-1]++;
							if(c[k-1]>1)
							{
								f=1;
								printf("False:Invalid initial Sudoku matrix!");
			                    printf("The number %d in the block %d has been used!",k,r);
			                    break;
							}
						}
					}
					if(f==1)
					break;
				}
				if(f==1)
					break;
			}
			if(f==1)
					break;
		}
		if(f==1)
					break;
	}
	if(d==0&&e==0&&f==0)
	printf("True:Valid initial Sudoku matrix!\n");
    }
}
bool p(int board[][9])
{
	int n=10,m=10;
	flag:
	if(n==10)
	{
	for(int i=0;i<9;i++)
	{
		for(int j=0;j<9;j++)
		{
			if(board[i][j]==0)
			{
				n=i;
				m=j;
				goto flag;
			}
			if(i==8&&j==8)
			return true;
		}
	}
    }
	for(int x=1;x<=9;x++)
	{
		board[n][m]=x;
		int c=w(board);
		board[n][m]=0;
		if(c==0)
		{
			board[n][m]=x;
			if(p(board))
			return true;
			board[n][m]=0;
		}
	}
	return false;
}
int main()
{
	int board[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}};
        printf("The original Sudoku matrix:\n");
		b(board);
		ww(board);
	int n=w(board);
	if(n==1)
	printf("No Solution!\n");
	else
	if(p(board))
	{
		printf("The solution of Sudoku matrix:\n");
		p(board);
		b(board);
	}
	else
	printf("No Solution!\n");
	return 0;
}