shudu1/4

#include <stdio.h>
#include <ctype.h>
void output(int (*p)[9]);
int check(int (*p)[9], int row, int col, int n);
int solve(int (*p)[9]);
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");
	output(board);
    int i,j,k;
	int f=1;
	for(i=0;i<9;i++)
	{
		int x[10]={0};
		for(j=0;j<9;j++)
		{
			x[board[i][j]]+=1;
		}
		for(k=1;k<=9;k++)
		{
			if(x[k]>1&&f==1)
			{
			printf("False:Invalid initial Sudoku matrix!\n");
			printf("The number %d in the col %d has been used!\n",k,i+1);
			f=0;
			}
		}
	}
	for(i=0;i<9;i++)
	{
		int z[10]={0};
		for(j=0;j<9;j++)
		{
			z[board[j/3+(i%3)*3][j%3+(i/3)*3]]+=1;
		}
		for(k=1;k<=9;k++)
		{
			if(z[k]>1&&f==1)
			{
				printf("False:Invalid initial Sudoku matrix!\n");
				printf("The number %d in the block %d has been used!\n",k,i+1);
				f=0;
			}
		}
	}
	for(i=0;i<9;i++)
	{
		int y[10]={0};
		for(j=0;j<9;j++)
		{
			y[board[j][i]]+=1;
		}
		for(k=1;k<=9;k++)
		{
			if(y[k]>1&&f==1)
			{
				printf("False:Invalid initial Sudoku matrix!\n");
				printf("The number %d in the row %d has been used!\n",k,i+1);
				f=0;
			}
		}
	}
	if(f==1)printf("True:Valid initial Sudoku matrix!\n");
    int flag=solve(board);
    if (flag)
    {
        printf("The solution of Sudoku matrix:\n");
        output(board);
    }
    else
    {
        printf("No solution!\n");
    }
    return 0;
}

void output(int (*p)[9])
{
    for (int i=0;i<9;i++)
    {
		if (i%3==0)
		{
			printf("|-----------|\n");
		}	
        for (int j=0;j<9;j++)
        {
			if (j%3==0)
			{
				printf("|");
			}
			printf("%d", p[i][j]);
        }
        printf("|\n");
    }
    printf("|-----------|\n");
}
int check(int (*p)[9], int row, int col, int num)
{
    int i, j, row1, col1;
    for (j=0;j<9;j++)
    {
        if (p[row][j]==num)
        {
            return 0;
        }
    }
    for (i=0;i<9;i++) 
    {
        if (p[i][col]==num)
        {
            return 0;
        }
    }
    row1=row/3*3;                      
    col1 =col/3*3;
    for (i=row1;i<=row1+2;i++)
    {
        for (j=col1;j<=col1+2;j++)
        {
            if (p[i][j]==num)
            {
                return 0;
            }
        }
    }
    return 1;
}
int solve(int (*p)[9])
{
    int arr[81][3]; 
    int i,j;
    int end=-1, now=0;  
    for (i=0;i<9;i++) 
    {
        for (j=0;j<9;j++)
        {
            if (p[i][j]==0)
            {
                end=end+1;
                arr[end][0]=i;
                arr[end][1]=j;
                arr[end][2]=1;
            }
        }
    }
    for (now=0;now<=end;)
    {
        if (arr[now][2]> 9)
        {
            if (now==0)
            {
                return 0;
            }
            else
            {
                arr[now][2]=1;
                p[arr[now][0]][arr[now][1]]=0;
                now=now-1;
                continue;
            }
        }
        for (i=arr[now][2];i<=9;i++) 
        {
            if (check(p,arr[now][0],arr[now][1],i)) 
            {
                arr[now][2]=i+1; 
                p[arr[now][0]][arr[now][1]]=i;
                now=now+1;
                break;
            }
            else if (i==9) 
            {
                arr[now][2]=1; 
                p[arr[now][0]][arr[now][1]]=0;
                now=now-1;
            }
        }
    }
    return 1;
}