#include<stdio.h>

int main()
{
	//引用函数 
	void Printf(char* p0);
	int Sudoku(char* p0);
	void Sudokuprint(char* p0);
	void Sudokuback(int k,char* p0);
	//给出矩阵 并打印 
	char board[9][9]={
	{'3','.','4','.','.','.','1','.','2'},
	{'.','.','.','2','3','8','.','.','.'},
	{'9','.','.','.','.','4','.','.','6'},
	{'.','3','5','.','7','.','.','6','.'},
	{'.','4','.','3','.','5','.','8','.'},
	{'.','7','.','.','9','.','2','5','.'},
	{'8','.','.','6','.','.','.','.','7'},
	{'.','.','.','9','4','7','.','.','.'},
	{'4','.','7','.','.','.','5','.','9'}};
	char* p0 = board;
	printf("The original Sudoku matrix:\n");
	Printf(p0);   
	int i,j,k;
	//成立的情况 运用回溯函数
	if(Sudoku(p0))
	{
		printf("True:Valid initial Sudoku matrix!\n");
		Sudokuback(0, p0);
	}	
	//不成立的情况 
	else
	{
		printf("False:Invalid initial Sudoku matrix!\n");
		Sudokuprint(p0);
		printf("No solution\n");
	}
	return 0;
}
//打印矩阵
void Printf(char* p0)
{
	int i,j;
	for(i=0;i<9;i++)
	{
		for(j=0;j<9;j++)
		{
			printf("%c ",p0[9*i+j]);
		}
		printf("\n");
	}
}
//判断是数独但不打印
int Sudoku(char* p0)
{
int i,j,number,s,q,p,t,g; 
//此处引入1
int c[10]={0,0,0,0,0,0,0,0,0,0};//用来储存数字出现的个数


//下面小矩阵的判断
int w[10]={1,2,3,4,5,6,7,8,9};
int k=0;
for(t=3;t<=9;t=t+3)
{
	for(g=3;g<=9;g=g+3)
	{
		for(i=t-3;i<t;i++)
		{
			for(j=g-3;j<g;j++)//分出来小矩阵
			{
				for(number=1;number<=9;number++)
				{
					if(p0[9*i+j] == number + '0')
						{c[number]++;}
				}
			}
		}
		for(q=1;q<=9;q++)
		{
			if(c[q]>1)
			{
				return 0;
			}
		}
		k++;
		for(s=0;s<=9;s++)c[s]=0;
	}

}
//完成行的判断
for(i=0;i<9;i++)
{

	for(number=1;number<=9;number++)
	{
		for(j=0;j<9;j++)
		{
			if(p0[9*i+j] == number + '0')
				c[number]++;
		}
	}
	for(q=1;q<=9;q++)
	{ 
		if(c[q]>1)
		{
			return 0 ;
		}
}
	for(p=0;p<10;p++)c[p]=0;
}
//同理列的判断
for(i=0;i<9;i++)
{
	for(number=1;number<=9;number++)
	{
	for(j=0;j<9;j++)
	{
		if(p0[9*j+i] == number + '0')
			c[number]++;}
	}
	for(q=1;q<=9;q++)
	{
		if(c[q]>1)
		{
			return 0;
		}
	}
	for(p=0;p<10;p++)c[p]=0;
}	
return 1;
}	
//判断数独并打印
void Sudokuprint(char* p0)
{

	int i, j, number, s, q, p, t, g;
	//此处引入1
	int c[10] = { 0,0,0,0,0,0,0,0,0,0 };//用来储存数字出现的个数


	//下面小矩阵的判断
	int w[10] = { 1,2,3,4,5,6,7,8,9 };
	int k = 0;
	for (t = 3;t <= 9;t = t + 3)
	{
		for (g = 3;g <= 9;g = g + 3)
		{
			for (i = t - 3;i < t;i++)
			{
				for (j = g - 3;j < g;j++)//分出来小矩阵
				{
					for (number = 1;number <= 9;number++)
					{
						if (p0[9 * i + j] == number + '0')
						{
							c[number]++;
						}
					}
				}
			}
			for (q = 1;q <= 9;q++)
			{
				if (c[q] > 1)
				{
					printf("The number %d in the block %d has been used!\n", q, w[k]);
					return ;
				}
			}
			k++;
			for (s = 0;s <= 9;s++)c[s] = 0;
		}

	}
	//完成行的判断
	for (i = 0;i < 9;i++)
	{

		for (number = 1;number <= 9;number++)
		{
			for (j = 0;j < 9;j++)
			{
				if (p0[9 * i + j] == number + '0')
					c[number]++;
			}
		}
		for (q = 1;q <= 9;q++)
		{
			if (c[q] > 1)
			{
				printf("The number %d in the col %d has been used!\n", q, i + 1);
				return ;
			}
		}
		for (p = 0;p < 10;p++)c[p] = 0;
	}
	//同理列的判断
	for (i = 0;i < 9;i++)
	{
		for (number = 1;number <= 9;number++)
		{
			for (j = 0;j < 9;j++)
			{
				if (p0[9 * j + i] == number + '0')
					c[number]++;
			}
		}
		for (q = 1;q <= 9;q++)
		{
			if (c[q] > 1)
			{
				printf("The number %d in the column %d has been used!\n", q, i + 1);
				return ;
			}
		}
		for (p = 0;p < 10;p++)c[p] = 0;
	}
	return ;
}
//回溯法填空
void Sudokuback(int k,char* p0)
{
	int m;
	if (k == 81)
	{
		if (Sudoku(p0)) 
		{ 
			printf("The solution of Sudoku matrix:\n");
			Printf(p0);
		}
		else printf("No sulotion\n");
		return;
	}
	if (p0[k] == '.')
	{
		for (m = 1;m <= 9;m++)
		{
			p0[k] = m+'0';
			if (Sudoku(p0))
			{
				Sudokuback(k + 1,p0);
			}

			else if (!Sudoku(p0)&&m==9)
			{
				p0[k] = '.';
				return ;
			}
		}
	}
	else
	{
		Sudokuback(k + 1, p0);
	}
}