纯C语言编程实现数独解法

        编程解决数独问题，网上查了很多资料，大多数的C语言程序虽然可以运行出结果，但是往往定义了很多全局数组变量来存储待解决数独中每一个空的状态信息（如：通过扫描整个数独表，记录待填的空的位置；记录每个待填空所在行和列已经有哪些值，接下来可以填哪些值等信息），这导致代码中全局变量很多，全局变量在整个程序中到处调用，在没有足够注释的情况下整个程序可读性不高，代码结构不是很清楚。

       本文下面给出的C程序中没有使用多少临时变量，当然此程序没有定义那么多全局变量存储数独解决过程的状态信息，可能导致运行时间稍微长一些，不过在我的环境下进行的几次测试，运行出结果的时间基本都在1秒以内（偶尔也会有7、8秒才出结果……）。这就是一个  “浪费空间换时间，浪费时间换空间”  的问题了。

       下面的C语言程序是参考着此处（https://www.cnblogs.com/wang-lianjie/p/shudujiafa.html）java程序中的算法所写的。程序中给出了较详细的注释，并且使用纯C语言，没有用C++的函数库。

       理解以下程序需要的主要基础知识：

           1.C语言：数组、循环、判断、函数、指针操作等。

           2.算法方面： 穷举思想、递归、基本的试探与回溯等。

       补充说明：

           1.代码没有进行充分的测试。

                    输入的数独数据本身是无解的，或对于一个数独可能存在一题多解的情况，程序会有什么反应我没测试过。

           3.数独数据是写死在程序里的，没有写从控制台手动输入或是从文件中读取数独数据的功能。

           2.该段代码具体的算法描还没写，哪天有空了再完善吧。。。

#include 
  
    #include 
   
     #define N 3 //小九宫格 #define M 9 //大九宫格 /*定义全局变量*/ int x[M][M]={ {0,2,0,0,0,9,0,1,0}, {5,0,6,0,0,0,3,0,9}, {0,8,0,5,0,2,0,6,0}, {0,0,5,0,7,0,1,0,0}, {0,0,0,2,0,8,0,0,0}, {0,0,4,0,1,0,8,0,0}, {0,5,0,8,0,7,0,3,0}, {7,0,2,3,0,0,4,0,5}, {0,4,0,0,0,0,0,7,0}, }; /* 结果： 4 2 3 7 6 9 5 1 8 5 7 6 4 8 1 3 2 9 9 8 1 5 3 2 7 6 4 8 3 5 6 7 4 1 9 2 1 9 7 2 5 8 6 4 3 2 6 4 9 1 3 8 5 7 6 5 9 8 4 7 2 3 1 7 1 2 3 9 6 4 8 5 3 4 8 1 2 5 9 7 6 */ /*---------------------------------------------------------------------------------------------------------*/ //int x[M][M]={ // {0,6,0,5,9,3,0,0,0}, // {9,0,1,0,0,0,5,0,0}, // {0,3,0,4,0,0,0,9,0}, // {1,0,8,0,2,0,0,0,4}, // {4,0,0,3,0,9,0,0,1}, // {2,0,0,0,1,0,6,0,9}, // {0,8,0,0,0,6,0,2,0}, // {0,0,4,0,0,0,8,0,7}, // {0,0,0,7,8,5,0,1,0}, //}; /* 结果： 7 6 2 5 9 3 1 4 8 9 4 1 2 7 8 5 3 6 8 3 5 4 6 1 7 9 2 1 9 8 6 2 7 3 5 4 4 7 6 3 5 9 2 8 1 2 5 3 8 1 4 6 7 9 3 8 7 1 4 6 9 2 5 5 1 4 9 3 2 8 6 7 6 2 9 7 8 5 4 1 3 */ /* 函数声明 */ //解决问题最主要的递归函数，递归访问大的9*9矩阵中的每一个小格，对待填空格（二维数组x中值为零的格子）进行填值操作。 void Solve(int r, int c); //以下3个函数为Solve运行过程中调用的判断函数，具体在下面有注释。 int checkedbox(int r); int checked(int r, int c, int num); int* getData(int r, int c,int *data); //输出最终计算结果的函数 void show(void); /* 函数定义 */ void Solve(int r, int c) { int i; //（一） //如果填的行号增加到了9，表示已经填完了整个数独空格（x二维数组行列的下标范围均为 0-8），打印结果即可 if (r == M) { show(); return; //此处的return返回表示已经填完了整个数独空格，接下来会逐步返回到主函数 } //（二） //在填写第3、6行开头数字的时,检查上边的三行的方块里是不是有重复的数字 if (c == 0 && (r == N || r == N*2)) { if (checkedbox(r) == 0) { // checkedbox()返回0表示小九宫格中出现了重复数字，说明之前的填写有误，则需要返回之前的填写试探中。 return; //这里的return会返回到第四个if中的某次循环中 } } //（三） //填到某行最后一个元素时，要转到下一行开头去 if (c == M) { Solve(r+1, 0); return; } //（四） //当前的坐标是0的时候才开始循环填写，否则跳过去填写下一个数字 if (x[r][c] == 0) { for (i = 1; i <= M; i++) { //对于每一个待填写的空格，循环1-9进行试探 if (checked(r,c,i) == 1) { x[r][c]=i; Solve(r, c+1); x[r][c]=0; } } } /* 如果上面的四个情况都不是。则正常地填该行的下一个元素，即行号不动，列号往前走一个。即Solve(r, c+1); 上面的四个情况是指： 1.既没有填写或处理完整个数独表 2.也不是刚填写或处理完了3个并列的小九宫格 3.也没有填写或处理到某行最后一个元素 4.此处坐标也不是零，即无需填写或处理 */ else{ Solve(r, c+1); } } / * 得到指定小九宫格中的九个数据，存入data中并返回data指针 * @param r 行号，可能取值为3，6 * @param c 列号，可能取值为0，3，6 * @return 判断结果，0表示小九宫格中有重复数字。1表示小九宫格中无重复数字。 */ int checkedbox(int r) { int i,j,c; int *data = malloc(sizeof(int)*M); for (c = 0; c < M; c+=N) { //循环三次，分别是c=0，3，6。对应循环大矩阵中9个3*3的小九宫格 data = getData(r,c,data); //得到小九宫格中的九个数据，存入全局变量数组data中 for(i = 0; i < M-1 ; i++) { for(j = i+1 ; j < M ; j++) { if(data[i] == data[j]) { //循环成立表示有重复数字 return 0; //有重复数字，返回0。 } } } } free(data); //函数执行结束，返回判断结果以前，释放指针malloc的空间。 return 1; //该函数能运行至此还没有结束返回，表示并列的三个小九宫格中，填入的均是1-9，没有重复数字，故返回1。 } / * 得到指定小九宫格中的九个数据，存入data中并返回data指针 * @param r 行号，可能取值为3，6 * @param c 列号，可能取值为0，3，6 * @return data指针（数组） */ int* getData(int r, int c,int *data){ int i,j,k = 0; for (i = r-N; i < r ; i++) { for(j = c; j < c+N ; j++){ data[k++] = x[i][j]; } } return data; } / * 判断某个待填位置所在的行和列是否有某个数字 * @param r 待填位置的行号 * @param c 待填位置的列号 * @param num 需要比较的待填数字 * @return 返回0：有重复数字，x[r][c]位置不能填num */ int checked(int r, int c, int num) { int j = 0,flag = 1; for (j = 0; j < M; j++) { if (x[j][c]==num || x[r][j]==num) { flag = 0; } } return flag; } //输出运算结果 void show(void) { int i,j; for (i = 0; i < M; i++) { for (j = 0; j < M; j++) { printf("%d ",x[i][j]); } printf("\n"); } printf("\n"); } int main(void) { Solve(0,0); return 0; }