题解 | #Sudoku#

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

static char g_input[9][9] = {0};
static int CheckUnitLegal(int row, int col) /* 检查当前数字在数独对应位置中是否合法(没有重复) */
{
    int r = (row / 3) * 3, c = (col / 3) * 3; /* 当前输入位置对应其所在九宫格的起始位置 */
    for (int i = 0; i < 9; i++) if ((g_input[row][i] == g_input[row][col]) && (i != col)) return -1; /* 行匹配 */
    for (int i = 0; i < 9; i++) if ((g_input[i][col] == g_input[row][col]) && (i != row)) return -1; /* 列匹配 */
    for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) { /* 九宫格匹配 */
        if ((g_input[r + i][c + j] == g_input[row][col]) && ((r + i) != row) && ((c + j) != col)) return -1;
    }
    return 0;
}

static char g_stack[81][3] = {0};
int main(int argc, char** argv)
{
    for (char i = 0; i < 9; i++) for (char j = 0; j < 9; j++) scanf("%d", &g_input[i][j]); /* 保存输入 */

    int row = 0, col = 0, idx = 0, i = 0;
    while ((row <= 8) && (col <= 8)) {
        if (g_input[row][col] != 0) { /* 非零则非填充数字，直接往后偏移跳过即可 */
            if (col >= 8) { if (row >= 8) break; else { col = 0; row++; } } else col++;
            continue;
        }

        for (i = 1; i <= 9; i++) { g_input[row][col] = i; if (CheckUnitLegal(row, col) == 0) break; } /* 直接填充1-9 */
        if (i <= 9) { /* 以上填充 1-9 发现合法时（即行、列、九宫格都满足数据要求），则将此次填充的位置和数值记录下来入栈 */
            g_stack[idx][0] = row; g_stack[idx][1] = col; g_stack[idx++][2] = i;
        } else { /* 如果 1-9 间填入任何数值都不合法，证明之前填充的数不对，需要将当前填充数清零，并把最后入栈的数出栈，重新填数 */
            g_input[row][col] = 0; /* 清零；恢复待填充状态 */
            while (--idx >= 0) { /* 出栈栈顶即最后一个入栈的填充信息 */
                row = g_stack[idx][0]; col = g_stack[idx][1];
                if (g_stack[idx][2] >= 9) g_input[row][col] = 0;
                else { g_input[row][col] = ++g_stack[idx][2]; if (CheckUnitLegal(row, col) == 0) break; else idx++; }
            }
            if (idx < 0) break; else idx++;
        }
    }

    for (char x = 0; x < 9; x++) {for (char y = 0; y < 9; y++) printf("%d ", g_input[x][y]); printf("\n"); } printf("\n");
    return 0;
}