#include<stdio.h>
#include<string.h>
#include <stdlib.h>
#include <time.h>

#define HANG 9
#define LIE 9

void printing(int matrix[HANG][LIE]) {
    for (int i = 0; i < HANG; ++i) {
        if (i % 3 == 0 && i != 0) {
            printf("----------------------|\n");
        }
        for (int j = 0; j < LIE; ++j) {
            if (j % 3 == 0 && j != 0) {
                printf("| ");
            }
            if (matrix[i][j] == '0') {
                printf("0 ");
            }
            else {
                printf("%c ", matrix[i][j]);
            }
            if (j == 8) {
                printf("|\n");
            }
        }
    }
    printf("----------------------|\n");
}

int is_valid(int board[9][9], int row, int col, int num) {// 检查行； 
    for (int i = 0; i < 9; i++) {
        if (board[row][i] == num) {
            return 0;
        }
    } 
    for (int i = 0; i < 9; i++) {//检查列 ； 
        if (board[i][col] == num) {
            return 0;
        }
    }
    int startr = row - row % 3;
    int startc = col - col % 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[startr + i][startc + j] == num) {
                return 0;
            }
        }
    }
    return 1;
}//函数 ； 
int solve_sudoku(int board[9][9]) {
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            if (board[row][col] == 0) {
                for (int num = 1; num <= 9; num++) {
                    if (is_valid(board, row, col, num)) {
                        board[row][col] = num;
                        if (solve_sudoku(board)) {
                            return 1;
                        }
                        board[row][col] = 0;
                    }
                }
                return 0;
            }
        }
    }
    return 1;
}
//函数 
int main(){
srand(time(NULL)); // 设置随机数种子
    int board[HANG][LIE];
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            board[i][j] = '0';
        }
    }
    for (int i = 0; i < 9; ++i)
    {
        int A= 0, B=0;
        int num[3];
        int posi[3];
        while (B< 3) 
        {
            int number = rand() % 9 + 1;
            if (B < 3 && !( num[2] == number|| num[1] == number ||num[0] == number )) 
            {
                num[B++] = number;
            }
        }
        while (A < 3) 
        {
            int place = rand() % LIE;
            if (  (A < 3)&&board[i][place] == '0') 
            {
                posi[A++] = place;
            }
        }
        
        for (int k = 0; k < 3; ++k) 
        {
            board[i][posi[k]] = num[k] + '0';
        }
    }printing(board); // 打印矩阵
	int a=0,b=0,c=0,d=1;
	for(int i=0;i<9;i++){
		for(int m=1;m<=9;m++){
			for(int j=0;j<9;j++){
				if(board[i][j]==m){
					a=a+1;
					if(a>1){
						printf("False:Invalid initial Sudoku matrix!\n");
						printf("The number %d in the row %d has been used!\n",m,i+1);
						return 0;
					}
				}
			}a=0;
			
		}
	}
	//行的判断 ； 
	for(int start=0;start<=6;){
		for(int end=0;end<=6;){
	        for(int m=1;m<9;m++){
	            for(int i=start;i<3;i++){
		         	for(int j=end;j<3;j++){
			        	if(board[i][j]==m){
					        c=c+1;}
				         	if(c>1){
				                printf("False:Invalid initial Sudoku matrix!\n");
						        printf("The number %d in the block %d has been used!\n",m,d);
						        return 0;
					        }
			        }
		        }
			c=0;
    	    }
			end=end+3;
			d=d+1;  
     	}
     	start=start+3;
    }
	//方块的判断； 
	for(int i=0;i<9;i++){
		for(int m=1;m<9;m++){
			for(int j=0;j<9;j++){
				if(board[j][i]==m){
					b=b+1;}
					if(b>1){
				        printf("False:Invalid initial Sudoku matrix!\n");
						printf("The number %d in the col %d has been used!\n",m,i+1);
						return 0;
					}
			}b=0;
		}b=0;
	}
printf("True:Valid initial Sudoku matrix!\n");
	//这是对数组的判断，是否为数独数组 
if (solve_sudoku(board)) {
printf("The solution of Sudoku matrix:\n"); 
printf("|-----------------------|\n");
	for(int i=0;i<9;i++){
		printf("| ");
		for(int j=0;j<9;j++){
			printf("%d ",board[i][j]);
			if((j+1)%3==0){
				printf("| ");
			}
		}
		printf("\n");
		if((i+1)%3==0)	{
			printf("|-----------------------|\n");
		   }
		   //数组的输出； 
		}
}else {
 printf("No solution!\n");} 
 return 0;
}