C语言||暴力算法解数独

前言

前几天在玩解数独游戏时，发现有点费时间。心血来潮想实现一个解数独的c语言程序，根据我在晚解数独游戏的思路，采用了暴力算法求解。在数组维数的选择上，我选择了用一维数组实现。

分析

其实暴力算法求解的实际是，将求解数组的思路，整合成代码，通过代码告诉计算机，让计算机按我们的想法来工作。 首先，9*9数独的规则是，每行九个数各不相同，每列九个数各不相同，每个小九宫格的九个数各不相同。例如下图（图片源于网络，侵删）： 暴力算法的实际就是，对81个小格里面待填元素逐一填值（1-9），符合则填入，九个数字都不符合则回退到上一个代填值元素，对该元素填新值，以此类推。时间复杂度是O(9^81)。下面是具体实现思路。

实现

1，拷贝原始数独至辅助数组，通过逐渐填满辅助数组来实现数独求解。而原始数独数组的作用是实时获取到上一个待填元素的位置，以便不会将原始数据改变。

void exit(int n) { int i = n; for (; i < 81; i++) { arr[i] = shudu[i]; } }

2，判断该值于该元素是否符合。 对于每次尝试填入的值，判断其是否符合规则（行唯一，列唯一，小单元格唯一）。主要通过调用下面的函数实现判断。

int check(int n, int num) {//检查num能不能作为当前元素的值 int hang = n / 9;//行 int lie = n % 9;//列 //获得所在小九宫格 int x = n / 9 / 3; int y = n % 9 / 3; int i , j; for (i=0; i < 9; i++) { if (arr[hang * 9 + i] == num && n != (hang * 9 + i)) {//检查行 return 0; } if (arr[lie + i * 9] == num && n != (lie + i * 9)) {//检查列 return 0; } } //检查小九宫格 for (i = x * 3; i < (x + 1) * 3; i++) { for (j = y * 3; j < (y + 1) * 3; j++) { if (num == arr[i * 9 + j] && n != (i * 9 + j)) { return 0; } } } return 1; }

3，如果该元素无论填1-9的任意值到不能满足要求，则回退。通过回退原始数组，从其原始的值得到具体回退的目标位置，获取改下标值，去查辅助数组从而获得刚刚成功的填入值，对其加1，重新判断，以此类推。下面是关键代码：

void solve() { int x = 0; for (; x < 81; x++) { if (shudu[x] == 0) { int i; int tellok=0; if (arr[x] == 0) { i = 1; }else { i = arr[x]; } for (; i < 10; i++) { int res = check(x, i); if (res) { tellok = 1; arr[x] = i; break; } } if(tellok == 0 ){ x--; while(shudu[x] != 0){ x--; } arr[x]++; exit(x+1); x--; } } } }

4，输出，直接输出辅助数组即可。

运行

完整源代码

下面附上有完整注释的源代码，刚需下（在visual studio上写的，可以在visual studio上、虚拟机的Gcc编译器上跑）https://download.csdn.net/download/qq_43543920/12565682