#include <stdio.h>
#include <stdbool.h>

char board0[9][9] = { {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                     {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                     {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                     {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                     {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                     {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                     {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                     {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                     {'.', '.', '.', '.', '8', '.', '.', '7', '9'} };

char board1[9][9] = { {'8', '3', '.', '.', '7', '.', '.', '.', '.'},
                     {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                     {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                     {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                     {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                     {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                     {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                     {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                     {'.', '.', '.', '.', '8', '.', '.', '7', '9'} };

char board[9][9] = { 0 };

bool dfs(char board[][9], bool row[][9], bool col[][9], bool block[][9], int i, int j)
{
   
    int num ;
    while (board[i][j] != '.')
    {
        if (++j >= 9)
        {
            i++;
            j = 0;
        }
        if (i >= 9)
        {
            return true;
        }
    }
    for (num = 0; num < 9; num++)
    {
        int blockIndex = i / 3 * 3 + j / 3;
        if (!row[i][num] && !col[j][num] && !block[blockIndex][num])
        {
            
            board[i][j] = (char)('1' + num);
            row[i][num] = true;
            col[j][num] = true;
            block[blockIndex][num] = true;
            if (dfs(board, row, col, block, i, j))
            {
                return true;
            }
            else
            {
                
                row[i][num] = false;
                col[j][num] = false;
                block[blockIndex][num] = false;
                board[i][j] = '.';
            }
        }
    }
    return false;
}


bool isValidSudoku(char board[][9]) {
    bool row[9][9] = { {false} };
    bool col[9][9] = { {false} };
    bool block[9][9] = { {false} };
    int i, j;

    for (i = 0; i < 9; i++) {
        for (j = 0; j < 9; j++) {
            if (board[i][j] != '.') {
                int num = board[i][j] - '1';
                int blockIndex = i / 3 * 3 + j / 3;
                if (row[i][num] || col[j][num] || block[blockIndex][num]) {
                    printf("False:Invalid initial Sudoku matrix!\n");
                    printf("      ");
                    if (row[i][num]) {
                        printf("The number %d in the row %d has been used!\n", num + 1, i + 1);
                    }
                    if (col[j][num]) {
                        printf("The number %d in the col %d has been used!\n", num + 1, j + 1);
                    }
                    if (block[blockIndex][num]) {
                        printf("The number %d in the block %d has been used!\n", num + 1, blockIndex + 1);
                    }
                    return false;
                }
                else {
                    row[i][num] = true;
                    col[j][num] = true;
                    block[blockIndex][num] = true;
                }
            }
        }
    }
    printf("True:Valid initial Sudoku matrix!\n");
    return dfs(board, row, col, block, 0, 0);
}

void printMatrix(char board[][9])
{
    int i, j;
    printf("      1 2 3   4 5 6   7 8 9\n");
    printf("    +-----------------------+\n");
    for (i = 0; i < 9; i++)
    {
        printf(" %d  | ", i + 1);
        for (j = 0; j < 9; j++)
        {
            printf("%c ", board[i][j]);
            if (j % 3 == 2)
            {
                printf("| ");
            }
        }
        printf("\n");
        if (i % 3 == 2)
        {
            printf("    +-----------------------+\n");
        }
    }
}


int main()
{
    int i, j;
    for (i = 0; i < 9; i++)
    {
        for (j = 0; j < 9; j++)
        {
            board[i][j] = '.';
        }
    }
    printf("The original Sudoku matrix:\n");
    printMatrix(board0);
    if (isValidSudoku(board0))
    {
        printf("The solution of Sudoku matrix:\n");
        printMatrix(board0);
    }
    else
    {
        printf("No solution!");
    }

    return 0;
}