关于数独的规则，在这里就不介绍了，蓝天十分钟内教你玩转数独对数独的规则和基本方法进行了解释。

这里主要介绍采用程序的方法来解数独问题。

数独问题最基本的方法是排除法和唯余法。

解数独问题，基本方法都是从数独满足的三个条件而得来的：

1、每行数字填入1-9,且不能重复  2、每列数字填入1-9,且不能重复  3、每宫数字填入1-9,且不能重复(宫就是黑粗线框出的3×3单元格的区域) 

所谓排除法，就是如果i行j列的位置的数字为d，那么i行、i列以及该位置所在的宫的其它位置不能有d的存在，否则就违背了数独的条件。

而唯余法则是用自己本身所在的行、列和宫的其它数字来得到自己可以放置的数字。

不过，应该注意的是，这些基本的方法只能解一些相对比较简单的题目。

排除法是用自己去排除其它格可以放置的数字，因此，就必须保存每个格被排除的数字。依次遍历81个格，如果某个格初始时已经填入了数字，就要用它来排除它所在行、列、宫可以放置的数字，行和列是很好判断的，关键的问题是宫，可以通过某个格获得该格所在的宫，然后依次遍历宫内的各个元素，这是通过in_square()来完成的。如果最后某个格被经过排除后只能放一个数字，那么，该位置就放置该数字。

唯余法是用别人来得到自己可以放置的数字，因此，必须保存每个格可以放置的数字。依次遍历81个格，如果某个宫初始时没有填入数字，就要用它所在的行、列、宫的其它数字来得到它可以放置的数字。其实代码跟上面的类似。

下面解释一下各数据结构和函数的功能：

char sudoku[MAXN][MAXN];    整个数独棋盘，这里为了简单起见，使用二维数组 int flag[MAXN][MAXN];              因为数独棋盘中，有些数字是固定的，保存一个二维数组用于标识这些数字。

                                                 当flag[i][j] = 0，说明sudoku[i][j]需要填入数字，如果flag[i][j] = 1，说明 sudoku[i][j]不需要填入数字。 char *exclude[89];                      包含89个指针的数组，每个指针保存某个格的排除的相关信息。

                                                  sudoku[i][j]对应的排除信息保存在exclude[i * 10 + j]中，它是一个包含9个元素的字符数组。exclude[i * 10 + j][k]保存的是sudoku[i][j]中是否可以放置k + 1，如果exclude[i * 10 + j][k] = 0表示可以放置k + 1，否则表示不能放置k + 1。

int empty_digit;                           记录未填入数字的个数，可以用于结束程序的条件。

以下就是数据结构的定义：

void set_sudoku()                       将文件中的未完成的数独读取到sudoku二维数组中，主要是为了方便起见，不用每次都输入数独数据。数独在文件中保存的格式是是类似.6.593...9.1...5...3.4...9.1.8.2...44..3.9..12...1.6.9.8...6.2...4...8.7...785.1.这样的，为了简单，81个格的信息都放在一行，"."表示需要填入数字。该函数的实现涉及到了文件的基本操作，打开文件，然后依次读取81个元素，然后关闭文件。

void print_sudoku()         打印整个数独棋盘，用两层循环就可以实现，要注意的是，在程序中将1-9当作字符还是整数来处理，这里将1-9当作整数来处理，因此，它们虽然保存在char型数组中，在输出的时候，如果是"."，就要当作字符来输出，否则，就要作为整数来输出。

void get_next(int ln, int col, int *next_ln, int *next_col)    获得(ln, col)的下一个位置，而且它在宫内是依次从左到右，从上到下，宫内最后一个元素的一个元素就是下一个宫的第一个元素，因此，利用该函数可以遍历九个宫。

int in_square(int ln, int col, int digit)           判断digit是否在(ln, col)所在的宫内，首先利用计算机的四则运算来获得(ln, col)所在的宫的第一个元素，然后调用9次get_next()来遍历这个宫，如果digit存在，则digit在该宫中，否则不在。

int is_valid(int ln, int col, char digit)        判断digit是否在(ln, col)所在的行和列，其实两个循环可以合并成一个，不过为了直观，这里并没有将它们合并。

void set_exclude(int ln, int col)      为sudoku[ln][col]设置排除集，设置排除集是用别的元素来排除它，依旧是分为三个部分。

void set_all_exclude()                    为数独中所有元素设置排除集，两层循环，不做过多解释。

void set_left(int ln, int col)    得到(ln, col)可以放置的数字，最后，如果只有一个可以放入的数字，就放入这个数字。

void set_all_left()                   为所有元素调用set_left()。

然后就可以利用set_all_exclude()和set_all_left()得到元素的排除集和余集（自己取的名字，呵呵）。

下面来看看，两种方式的结果：

对上面的数独执行set_all_exclude()，得到：

上面就是部分成员的排除集，当有8个元素时，剩下那个就是需要填入的值，执行10次排除法，就能够得到上述数独的解。

执行set_all_left()，得到：

上面是部分成员的余集，当只有一个元素时，就可以填入那个元素，如上图的[4][4]、[5][3]、[6][4]、[6][5]、[6][8]都可以直接填入了。执行5次唯余法，就可以得到上述数独的解。

下面给出上述数独的解：

数独问题是个很有意思的问题，而且数独还分为不同的难度级别，像上面这两种方法只能解决一些简单的数独问题，对于难的问题就不行了。当然，个人水平有限，从数据结构到代码可能写的不是很好，望各位批评指正！