#include <stdio.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");
    }
}

int main()
{
    int board[9][9] = {{5,3,4,6,7,8,9,1,2},
                       {6,7,2,1,9,5,3,4,8},
                       {1,9,8,3,4,2,5,6,7},
                       {8,5,9,7,6,1,4,2,3},
                       {4,2,6,8,5,3,7,9,1},
                       {7,1,3,9,2,4,8,5,6},
                       {9,6,1,5,3,7,2,8,4},
                       {2,8,7,4,1,9,6,3,5},
                       {3,4,5,2,8,6,1,7,9}};
    putboard(board);
    return 0;
}


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

#define ROWS 9
#define COLS 9

void printMatrix(char matrix[ROWS][COLS]);

int main() {
    srand(time(NULL)); // 设置随机数种子
    char matrix[ROWS][COLS];

    // 初始化矩阵为'.'
    int i,j,k; 
    for (i = 0; i < ROWS; ++i) {
        for ( j = 0; j < COLS; ++j) {
            matrix[i][j] = '.';
        }
    }

    // 填充矩阵
    for ( i = 0; i < ROWS; ++i) {
        int positions[3];
        int numbers[3];
        int posIndex = 0, numIndex = 0;

        // 随机选择3个不同的位置
        while (posIndex < 3) {
            int randPos = rand() % COLS;
            if (matrix[i][randPos] == '.' && posIndex < 3) {
                positions[posIndex++] = randPos;
            }
        }

        // 随机选择3个不同的数字
        while (numIndex < 3) {
            int randNum = rand() % 9 + 1;
            if (numIndex < 3 && !(numbers[0] == randNum || numbers[1] == randNum || numbers[2] == randNum)) {
                numbers[numIndex++] = randNum;
            }
        }

        // 将数字放置在随机位置上
        for ( k = 0; k < 3; ++k) {
            matrix[i][positions[k]] = numbers[k] + '0';
        }
    }

    printMatrix(matrix); // 打印矩阵
    return 0;
}

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


#include <stdio.h>

#define SIZE 9

void printBoard(int board[SIZE][SIZE]) {
    printf("The original Sudoku matrix:\n");
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            printf("%d ", board[i][j]);
        }
        printf("\n");
    }
}

int isValidSudoku(int board[SIZE][SIZE]) {
    int row[SIZE][SIZE] = {0};
    int col[SIZE][SIZE] = {0};
    int block[SIZE][SIZE] = {0};

    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            int num = board[i][j];
            if (num < 1 || num > 9) continue; // Skip zeros

            int blockIndex = (i / 3) * 3 + (j / 3);

            // Check row
            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;
            }
            row[i][num - 1] = 1;

            // Check column
            if (col[j][num - 1]) {
                printf("False: Invalid initial Sudoku matrix!\n");
                printf("The number %d in the col %d has been used!\n", num, j + 1);
                return 0;
            }
            col[j][num - 1] = 1;

            // Check block
            if (block[blockIndex][num - 1]) {
                printf("False: Invalid initial Sudoku matrix!\n");
                printf("The number %d in the block %d has been used!\n", num, blockIndex + 1);
                return 0;
            }
            block[blockIndex][num - 1] = 1;
        }
    }
    printf("True: Valid initial Sudoku matrix!\n");
    return 1;
}

int main() {
    int board0[SIZE][SIZE] = {
        {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}
    };

    printBoard(board0);
    isValidSudoku(board0);

    return 0;
}


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

#define ROWS 9
#define COLS 9

int checkValid(char matrix[ROWS][COLS]);
void printMatrix(char matrix[ROWS][COLS]);
int isSafe(char matrix[ROWS][COLS], int row, int col, char num);
int solveSudoku(char matrix[ROWS][COLS]);
void generateSudoku(char matrix[ROWS][COLS]);

int main() {
    srand(time(NULL)); // 设置随机数种子
    char matrix[ROWS][COLS] = {0};

    // 循环直到生成一个有解的数独矩阵
    do {
        generateSudoku(matrix);
    } while (!checkValid(matrix));

    printf("The original Sudoku matrix: \n");
    printMatrix(matrix);

    if (solveSudoku(matrix)) {
        printf("True: Valid initial Sudoku matrix!\n");
        printf("The solution of Sudoku matrix:\n");
        printMatrix(matrix);
    } else {
        printf("False: Invalid initial Sudoku matrix!\n");
        printf("No solution!\n");
    }

    return 0;
}

void generateSudoku(char matrix[ROWS][COLS]) {
    // 初始化矩阵为'.'
    for (int i = 0; i < ROWS; ++i) {
        for (int j = 0; j < COLS; ++j) {
            matrix[i][j] = '.';
        }
    }

    // 填充矩阵
    for (int i = 0; i < ROWS; ++i) {
        for (int j = 0; j < COLS; ++j) {
            if (rand() % 2) { // 随机决定是否填充数字
                int num = rand() % 9 + 1;
                matrix[i][j] = num + '0';
            }
        }
    }
}

int checkValid(char matrix[ROWS][COLS]) {
    // 检查每行是否有重复的数字
    for (int i = 0; i < ROWS; ++i) {
        int rowUsed[10] = {0};
        for (int j = 0; j < COLS; ++j) {
            if (matrix[i][j] != '.') {
                int num = matrix[i][j] - '0';
                if (rowUsed[num]) {
                    return 0; // 行中有重复数字
                }
                rowUsed[num]++;
            }
        }
    }

    // 检查每列是否有重复的数字
    for (int j = 0; j < COLS; ++j) {
        int colUsed[10] = {0};
        for (int i = 0; i < ROWS; ++i) {
            if (matrix[i][j] != '.') {
                int num = matrix[i][j] - '0';
                if (colUsed[num]) {
                    return 0; // 列中有重复数字
                }
                colUsed[num]++;
            }
        }
    }

    // 检查每个3x3子矩阵是否有重复的数字
    for (int i = 0; i < ROWS; i += 3) {
        for (int j = 0; j < COLS; j += 3) {
            int subUsed[10] = {0};
            for (int x = i; x < i + 3; ++x) {
                for (int y = j; y < j + 3; ++y) {
                    if (matrix[x][y] != '.') {
                        int num = matrix[x][y] - '0';
                        if (subUsed[num]) {
                            return 0; // 子矩阵中有重复数字
                        }
                        subUsed[num]++;
                    }
                }
            }
        }
    }

    return 1; // 数独矩阵有效
}

int isSafe(char matrix[ROWS][COLS], int row, int col, char num) {
    // 检查行
    for (int i = 0; i < COLS; ++i) {
        if (matrix[row][i] == num) return 0;
    }

    // 检查列
    for (int i = 0; i < ROWS; ++i) {
        if (matrix[i][col] == num) return 0;
    }

    // 检查3x3子矩阵
    int startRow = row - row % 3, startCol = col - col % 3;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (matrix[i + startRow][j + startCol] == num) return 0;
        }
    }

    return 1;
}

int solveSudoku(char matrix[ROWS][COLS]) {
    for (int i = 0; i < ROWS; ++i) {
        for (int j = 0; j < COLS; ++j) {
            if (matrix[i][j] == '.') {
                for (int num = 1; num <= 9; ++num) {
                    char numChar = num + '0';
                    if (isSafe(matrix, i, j, numChar)) {
                        matrix[i][j] = numChar;
                        if (solveSudoku(matrix)) return 1;
                        matrix[i][j] = '.';
                    }
                }
                return 0;
            }
        }
    }
    return 1;
}

void printMatrix(char matrix[ROWS][COLS]) {
    for (int i = 0; i < ROWS; ++i) {
        if (i % 3 == 0 && i != 0) {
            printf("--------------|\n");
        }
        for (int j = 0; j < COLS; ++j) {
            if (j % 3 == 0) {
                printf("|");
            }
            printf("%c ", matrix[i][j] == '.' ? '.' : matrix[i][j]);
            if (j == 8) {
                printf("|\n");
            }
        }
    }
    printf("--------------|\n");
}