#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<stdbool.h>
void putboard(int board[][9])
{
	printf("|-----------------------|\n");
	for(int i=0;i<9;i++)
	{
		printf("|");
		for(int j=0;j<9;j++)
		{
			printf("%2d",board[i][j]);
			if(j==2||j==5||j==8)
			printf(" |");
		}
		printf("\n");
		if(i==2||i==5||i==8)
		printf("|-----------------------|\n");
	}
}
void judgeboard(int board[][9])
{
	int judge=0;
	printf("The original Sudoku matrix:\n");
	putboard(board);
	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)
					{
						printf("False:Invalid initial Sudoku matrix!\n");
						printf("      The number %d in the line %d has been used!\n",board[i][j],i+1);
						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)
					{
						printf("False:Invalid initial Sudoku matrix!\n");
						printf("      The number %d in the col %d has been used!\n",board[j][i],i+1);
						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))
									{
										printf("False:Invalid initial Sudoku matrix!\n");
										printf("      The number %d in the block %d has been used!\n",board[x][y],i/3+1+(j/3+1)*3);
										judge=1;
										goto flag3;
									}
								}
							}
						}
					}
				}
			}
		}
	}
	if(judge==0)
	printf("True:Valid initial Sudoku matrix!\n");
}
int judgeboard2(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 creatboard(int board[][9])
{
	srand(time(NULL));
	for(int i=0;i<9;i++)
	{
		for(int j=0;j<9;j++)
		board[i][j]=0;
	}
	int a[9]={0};
	int n,m;
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=9;j++)
		{
			n=rand()%10;
			m=rand()%10;
			while(!(n-(i-1)*3>=0&&n-(i-1)*3<3)||a[n]>=3||!(m>=0&&m<9)||board[n][m]!=0)
			{
				n=rand()%10;
		    	m=rand()%10;
			}
			board[n][m]=j;
			a[n]++;
		}
	}
}
bool solveboard(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=judgeboard2(board);
		board[n][m]=0;
		if(c==0)
		{
			board[n][m]=x;
			if(solveboard(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}};
    judgeboard(board);
	int n=judgeboard2(board);
	if(n==1)
	printf("No Solution!\n");
	else
	if(solveboard(board))
	{
		printf("The solution of Sudoku matrix:\n");
		solveboard(board);
		putboard(board);
	}
	else
	printf("No Solution!\n");
	return 0;
}