题解 | #Sudoku#

#include <stdio.h>
#include <stdbool.h>
void printsudo(int sudo[9][9]) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if(j != 8) printf("%d ", sudo[i][j]);
            else printf("%d", sudo[i][j]);
        }
        printf("\n");
    }
}
// 输入分别是，数独盘面，所在行数列数和填充的数字
bool checknumvalid(int sudo[9][9], int row, int col, int num) {
    // 先检查行
    for(int i = 0; i < 9; i++) {
        if(sudo[row][i] == num) return false;
    }

    // 然后检查列
    for(int i = 0; i < 9; i++) {
        if(sudo[i][col] == num) return false;
    }

    // 检查所在九宫格

    int startrow = row - row % 3;
    int startcol = col - col % 3;
    for(int i = startrow; i < startrow + 3; i++) {
        for(int j = startcol; j < startcol + 3; j++) {
            if(!(i == row && j == col)) {
                if(sudo[i][j] == num) return false;
            }
        }
    }

    return true;
}

bool solvesudo(int sudo[9][9]) {
    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 9; j++) {
            if(sudo[i][j] == 0) {
                for(int k = 1; k <= 9; k++) {
                    // printf("for %d,%d trying number %d\n", i, j, k);
                    if(checknumvalid(sudo, i, j, k)) {
                        sudo[i][j] = k;
                        if(solvesudo(sudo)) return true;
                        // 如果填充的数字不能实现数独的全解，回复为0方便寻找下一个数字
                        else sudo[i][j] = 0;
                    }
                }
                return false;
            }
        }
    }
    return true;
}

int main () {
    int sudoku[9][9];
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            scanf("%d", &sudoku[i][j]);
        }
    }
    if(solvesudo(sudoku)) {
        printsudo(sudoku);
    }
    return 0;
}