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

void printSudoku(int sudoku[9][9]) {
	printf("-------------------------\n");
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (sudoku[i][j] == 0) {
				printf(" .");
			} else {
				printf(" %d", sudoku[i][j]);
			}
			if ((j + 1) % 3 == 0) {
				printf(" |");
			}
		}
		printf("\n");
		if ((i + 1) % 3 == 0) {
			printf("-------------------------\n");
		}
	}
}

void generateSudoku(int sudoku[9][9]) {
	srand(time(NULL));
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			sudoku[i][j] = 0;
		}
	}
	for (int i = 0; i < 9; i += 3) {
		int num = 1;
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				int row = rand() % 3 + i;
				int col = rand() % 9;
				while (sudoku[row][col] != 0) {
					col = (col + 1) % 9;
				}
				sudoku[row][col] = num;
				num = (num + 1) % 9 + 1;
			}
		}
	}
}

int isValidSudoku(int sudoku[9][9]) {
	int row[9][10] = {0}; 
	int col[9][10] = {0}; 
	int block[3][3][10] = {0};
	
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			int num = sudoku[i][j];
			if (num != 0) {
				if (row[i][num] == 1) {
					printf("False: Invalid initial Sudoku matrix!\n");
					printf("The number %d in the row %d has been used!\n", num, i + 1);
					return 0;
				}
				if (col[j][num] == 1) {
					printf("False: Invalid initial Sudoku matrix!\n");
					printf("The number %d in the column %d has been used!\n", num, j + 1);
					return 0;
				}
				if (block[i / 3][j / 3][num] == 1) {
					printf("False: Invalid initial Sudoku matrix!\n");
					printf("The number %d in the block %d has been used!\n", num, (i / 3) * 3 + j / 3 + 1);
					return 0;
				}
				row[i][num] = 1;
				col[j][num] = 1;
				block[i / 3][j / 3][num] = 1;
			}
		}
	}
	printf("True: Valid initial Sudoku matrix!\n");
	return 1;
}

int isSudokuFilled(int sudoku[9][9]) {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (sudoku[i][j] == 0) {
				return 0;
			}
		}
	}
	return 1;
}

int isSafe(int sudoku[9][9], int row, int col, int num) {
	for (int i = 0; i < 9; i++) {
		if (sudoku[row][i] == num || sudoku[i][col] == num) {
			return 0;
		}
	}
	int startRow = row - row % 3;
	int startCol = col - col % 3;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (sudoku[i + startRow][j + startCol] == num) {
				return 0;
			}
		}
	}
	return 1;
}

int solveSudoku(int sudoku[9][9]) {
	if (isSudokuFilled(sudoku)) {
		return 1;
	}
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (sudoku[i][j] == 0) {
				for (int num = 1; num <= 9; num++) {
					if (isSafe(sudoku, i, j, num)) {
						sudoku[i][j] = num;
						if (solveSudoku(sudoku)) {
							return 1;
						}
						sudoku[i][j] = 0;
					}
				}
				return 0;
			}
		}
	}
	return 0;
}

int main() {
	int sudoku[9][9];
	
	generateSudoku(sudoku);
	printf("The original Sudoku matrix:\n");
	printSudoku(sudoku);
	
	isValidSudoku(sudoku);
	
	if (solveSudoku(sudoku)) {
		printf("The solution of Sudoku matrix:\n");
		printSudoku(sudoku);
	} else {
		printf("No solution!\n");
	}
	
	return 0;
}