C语言实现数独程序的示例代码

下面是关于“C语言实现数独程序的示例代码”的完整攻略：

一、编写数独程序的流程

1. 确定程序输入和输出

数独程序的输入应该是一个9x9的矩阵，即数独的谜题，其中0表示未知格子。程序的输出应该是一个解开谜题后的9x9矩阵。

2. 确定算法

数独程序的算法一般有两种，分别是暴力求解和回溯法。

2.1 暴力求解

暴力求解是指从左到右、从上到下依次填数，直到填到空格为止。如果填到某一个格子时，发现无法填入任何数字，就回溯到上一个格子，重新填数。

暴力求解的代码比较简单，但时间复杂度非常高，不适用于求解复杂的数独谜题。

2.2 回溯法

回溯法是指从左到右、从上到下依次填数，如果填到某一个格子时，发现无法填入任何数字，就回溯到上一个格子，重新填数。回溯法在暴力求解的基础上加了一些优化，速度更快，适用于求解复杂的数独谜题。

3. 编写代码

首先定义一个9x9的二维数组表示数独谜题，其中0表示未知格子。

int sudoku[9][9] = {
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0}
};

输入数独谜题，将谜题赋值给二维数组。

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

声明一个函数用于判断填数是否合法，判断的标准为这个数字是否在这一行、这一列和这个九宫格中都没有出现过。

int is_valid(int row, int col, int num) {
    // 判断行是否合法
    for (int i = 0; i < 9; i++) {
        if (sudoku[row][i] == num) {
            return 0;
        }
    }
    // 判断列是否合法
    for (int i = 0; i < 9; i++) {
        if (sudoku[i][col] == num) {
            return 0;
        }
    }
    // 判断九宫格是否合法
    int start_row = row / 3 * 3;
    int start_col = col / 3 * 3;
    for (int i = start_row; i < start_row + 3; i++) {
        for (int j = start_col; j < start_col + 3; j++) {
            if (sudoku[i][j] == num) {
                return 0;
            }
        }
    }
    return 1;
}

声明一个回溯函数用于求解数独谜题。

int solve_sudoku(int row, int col) {
    // 如果已经填满了，返回1表示已经得到可行解
    if (row == 9) {
        return 1;
    }
    // 如果当前格子已经填了数字，跳到下一个格子继续填数
    if (sudoku[row][col] != 0) {
        if (col == 8) {
            if (solve_sudoku(row + 1, 0)) {
                return 1;
            }
        } else {
            if (solve_sudoku(row, col + 1)) {
                return 1;
            }
        }
        return 0;
    }
    // 枚举当前格子可以填的数字
    for (int i = 1; i <= 9; i++) {
        if (is_valid(row, col, i)) {
            // 填数
            sudoku[row][col] = i;
            // 继续填下一个格子，如果填完后返回1，那么就说明已经得到可行解
            if (col == 8) {
                if (solve_sudoku(row + 1, 0)) {
                    return 1;
                }
            } else {
                if (solve_sudoku(row, col + 1)) {
                    return 1;
                }
            }
            // 如果填完后没有得到可行解，就回溯到上一个格子，重新填数
            sudoku[row][col] = 0;
        }
    }
    return 0;
}

调用回溯函数求解数独谜题。

if (solve_sudoku(0, 0)) {
    // 输出解
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            printf("%d ", sudoku[i][j]);
        }
        printf("\n");
    }
} else {
    printf("No solution!\n");
}

二、示例说明

示例一

现在有一个数独谜题如下：

0 0 0 0 0 0 0 2 0
0 0 7 0 0 0 0 0 0
0 0 0 0 0 0 6 0 0
0 0 0 8 0 0 0 0 0
0 9 0 0 0 3 0 5 0
5 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 7 0
0 4 0 0 0 0 0 0 0
0 0 0 0 1 0 0 6 0

使用上面给出的程序模板，可以得到以下输出：

1 3 5 6 4 9 8 2 7 
4 6 7 1 5 2 3 8 9 
9 2 8 3 7 8 6 4 5 
2 5 6 8 3 1 7 9 4 
7 9 1 2 6 3 4 5 8 
5 8 3 4 9 7 2 1 6 
3 1 2 5 8 4 9 7 1 
6 4 9 7 2 1 5 3 3 
8 7 4 9 1 5 7 6 2

示例二