C语言回溯法解数独完整实现

咖啡半糖

发布时间：2026-10-16 | 5人浏览过

原创

本文详解如何利用C语言编写一个数独求解程序。通过回溯算法（Backtracking）与多维数组状态标记，实现对输入数独题目的自动填充与验证，适合C语言初学者理解递归与约束满足问题。

数独求解原理与结果

数独规则要求在一个 9x9 的网格中，每行、每列以及每一个 3x3 的九宫格内，数字 1-9 均只能出现一次且不能重复。解题的核心在于找到一个空位，尝试填入符合上述规则的数字，若后续无法继续则回退（回溯）并尝试下一个数字。

输入格式： 9x9 的矩阵，已知数字直接输入，空位用 0 补齐，数字间以空格隔开。

输出结果： 填满数字的完整数独矩阵。

准备条件

环境要求：gcc 或任何支持 C99 标准的编译器。无需外部库，仅依赖 stdio.h 和 stdlib.h。

真实操作顺序与代码结构

第1步：定义状态标记函数

目的： 为了高效判断某个位置能否填入数字 n，避免每次检查整行/列/宫。
入口： 辅助函数 fillnumber 和 resetnumber。
动作： 使用三维数组 g[9][9][10] 记录状态。第三维索引 1-9 代表填入的数字。当填入数字 number 时，将该数字对应行、列及所在九宫格的位置计数加 1；撤销时减 1。若任意位置计数大于 0，说明冲突。

int *fillnumber(int a[9][9][10], int number, int i, int j) {
    for (int k=0; k<9; k++) {
        a[i][k][number]++;      // 更新行
        a[k][j][number]++;      // 更新列
    }
    // 更新所在3x3九宫格
    for (int n=0; n<3; n++) {
        for (int m=0; m<3; m++) {
            a[i/3*3+n][j/3*3*m][number]++;
        }
    }
    return a;
}

int *resetnumber(int a[9][9][10], int number, int i, int j) {
    for (int k=0; k<9; k++) {
        a[i][k][number]--;
        a[k][j][number]--;
    }
    for (int n=0; n<3; n++) {
        for (int m=0; m<3; m++) {
            a[i/3*3+n][j/3*3+m][number]--;
        }
    }
    return a;
}

第2步：实现回溯搜索核心逻辑

目的： 递归寻找空格并填入合法数字。
入口： search(step, a, g)，其中 step 为剩余空格数。
动作：

终止条件： 若 step == 0，表示所有空格已填满，打印矩阵并退出。
寻找空格： 遍历 9x9 网格，找到第一个值为 0 的空位 (i, j)。
尝试数字： 循环 number = 1 to 9。若 g[i][j][number] == 0（无冲突）：

调用 fillnumber 标记占用。
将 a[i][j] 设为 number。
递归调用 search(step-1, ...)。
回溯： 无论递归成功与否，需恢复状态：将 a[i][j] 清零，调用 resetnumber 移除标记。

void search(int step, int a[9][9], int g[9][9][10]) {
    if (step == 0) {
        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                printf("%d ", a[i][j]);
            }
            printf("\n");
        }
        exit(0); // 找到唯一解后直接退出
    }

    for (int i=0; i<9; i++) {
        for (int j=0; j<9; j++) {
            if (a[i][j] == 0) {
                // 找到第一个空格，尝试所有可能数字
                for (int number=1; number<10; number++) {
                    if (g[i][j][number] == 0) {
                        fillnumber(g, number, i, j);
                        a[i][j] = number;
                        search(step - 1, a, g);
                        // 回溯恢复现场
                        a[i][j] = 0;
                        resetnumber(g, number, i, j);
                    }
                }
                return; // 当前格子所有数字试完仍无解，返回上一层
            }
        }
    }
}

第3步：主函数输入与初始化

目的： 读取用户输入，预处理初始盘面状态。
动作：

初始化二维数组 a 存储盘面，三维数组 abool 存储状态标记。
读取 9x9 个整数。统计空格数量作为初始 step。
若输入为非零数字，立即调用 fillnumber 进行预标记，确保后续搜索尊重已知数字。

int main() {
    int a[9][9];
    int abool[9][9][10];
    int step = 0;

    // 初始化状态数组
    for (int i=0; i<9; i++)
        for (int j=0; j<9; j++)
            for (int k=1; k<10; k++)
                abool[i][j][k] = 0;

    // 读取输入并预处理
    for (int i=0; i<9; i++) {
        for (int j=0; j<9; j++) {
            scanf("%d", &a[i][j]);
            if (a[i][j] == 0) {
                step++;
            } else {
                fillnumber(abool, a[i][j], i, j);
            }
        }
    }

    // 开始搜索
    search(step, a, abool);
    return 0;
}