C 解法, 执行用时: 1ms, 内存消耗: 360KB, 提交时间: 2021-03-18

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

#define N 9

bool Digui(int **grid, int **rowFlag, int **colFlag, int **subGridFlag, int row, int col){
    if (col == 9){
        col = 0;
        row += 1;
    }
    if (row == 9){
        return true;
    }
    if(grid[row][col] == 0){
        for(int i=1; i<10; i++){
            if(rowFlag[row][i-1] ==0 && colFlag[col][i-1] == 0 
               && subGridFlag[(row/3)*3+(col/3)][i-1] == 0){
                grid[row][col] = i;
                rowFlag[row][i-1] = 1;
                colFlag[col][i-1] = 1;
                subGridFlag[(row/3)*3+(col/3)][i-1] = 1;
                if(true == Digui(grid, rowFlag, colFlag, subGridFlag, row, col+1)){
                    return true;
                }else{
                    grid[row][col] = 0;
                    rowFlag[row][i-1] = 0;
                    colFlag[col][i-1] = 0;
                    subGridFlag[(row/3)*3+(col/3)][i-1] = 0;
                }
            }
        }
    }else{
        return Digui(grid, rowFlag, colFlag, subGridFlag, row, col+1);
    }
    return false;
}
void jieShudu(int **grid){
    int **rowFlag = (int **)malloc(N*sizeof(int*));
    int **colFlag = (int **)malloc(N*sizeof(int*));
    int **subGridFlag = (int **)malloc(N*sizeof(int*));
    for(int i=0; i<N; i++){
        rowFlag[i] = (int *)malloc(N*sizeof(int));
        memset(rowFlag[i], 0, sizeof(int)*N);
        colFlag[i] = (int *)malloc(N*sizeof(int));
        memset(colFlag[i], 0, sizeof(int)*N);
        subGridFlag[i] = (int *)malloc(N*sizeof(int));
        memset(subGridFlag[i], 0, sizeof(int)*N);
    }
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            int value = grid[i][j];
            if(value >0 && value < 10){
                rowFlag[i][value - 1] = 1;
                colFlag[j][value - 1] = 1;
                subGridFlag[(i/3)*3 + (j/3)][value - 1] = 1;
            }
        }
    }
    Digui(grid, rowFlag, colFlag, subGridFlag, 0, 0);
}
void printShudu(int **grid){
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                printf("%2d", grid[i][j]);
            }
        }
}
int main(){
    int **grid = (int **)malloc(N*sizeof(int*));
   for(int i=0; i<9; i++){
       grid[i] = (int *)malloc(N*sizeof(int));
       memset(grid[i], 0, sizeof(int)*N);
   }
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            scanf("%d", &grid[i][j]);
        }
    }
    jieShudu(grid);
    printShudu(grid);
    return 0;
}

C 解法, 执行用时: 1ms, 内存消耗: 364KB, 提交时间: 2021-01-17

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

#define N 9

bool Digui(int **grid, int **rowFlag, int **colFlag, int **subGridFlag, int row, int col)
{
    if (col == 9){
        col = 0;
        row += 1;
    }
    if (row == 9){
        return true;
    }
    
    if(grid[row][col] == 0){
        for(int i=1; i<10; i++){
            if(rowFlag[row][i-1] ==0 && colFlag[col][i-1] == 0 
               && subGridFlag[(row/3)*3+(col/3)][i-1] == 0){
                grid[row][col] = i;
                rowFlag[row][i-1] = 1;
                colFlag[col][i-1] = 1;
                subGridFlag[(row/3)*3+(col/3)][i-1] = 1;
                
                if(true == Digui(grid, rowFlag, colFlag, subGridFlag, row, col+1)){
                    return true;
                }else{
                    grid[row][col] = 0;
                    rowFlag[row][i-1] = 0;
                    colFlag[col][i-1] = 0;
                    subGridFlag[(row/3)*3+(col/3)][i-1] = 0;
                }
            }
        }
        
    }else{
        return Digui(grid, rowFlag, colFlag, subGridFlag, row, col+1);
    }
    return false;
}
void jieShudu(int **grid)
{
    int **rowFlag = (int **)malloc(N*sizeof(int*));
    int **colFlag = (int **)malloc(N*sizeof(int*));
    int **subGridFlag = (int **)malloc(N*sizeof(int*));
    
    for(int i=0; i<N; i++){
        rowFlag[i] = (int *)malloc(N*sizeof(int));
        memset(rowFlag[i], 0, sizeof(int)*N);
        colFlag[i] = (int *)malloc(N*sizeof(int));
        memset(colFlag[i], 0, sizeof(int)*N);
        subGridFlag[i] = (int *)malloc(N*sizeof(int));
        memset(subGridFlag[i], 0, sizeof(int)*N);
    }
    
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            int value = grid[i][j];
            if(value >0 && value < 10){
                rowFlag[i][value - 1] = 1;
                colFlag[j][value - 1] = 1;
                subGridFlag[(i/3)*3 + (j/3)][value - 1] = 1;
            }
        }
    }
    
    Digui(grid, rowFlag, colFlag, subGridFlag, 0, 0);
}
void printShudu(int **grid)
{
        for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            printf("%2d", grid[i][j]);
        }
        }
}
int main()
{
    int **grid = (int **)malloc(N*sizeof(int*));
        
   for(int i=0; i<9; i++){
       grid[i] = (int *)malloc(N*sizeof(int));
       memset(grid[i], 0, sizeof(int)*N);
   }
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            scanf("%d", &grid[i][j]);
        }
    }
    jieShudu(grid);
    printShudu(grid);
    return 0;
}