数独（Sudoku）是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。 每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。
如下图所示，就是一个数独的题目
关于数独的详细介绍，参看“百度百科——数独”
数独的基本解法就是利用规则的摒弃法
一些定义
每一行称为数独的行，每一列称为数独的列，每一个小九宫格称为数独的宫。数独的基本规则就是每一行、每一列、每一宫中，1-9这9个数字都只出现一次。
用（行，列）表示上图的单元格，例如（1，1）表示第一行第一列的单元格，（2，4）表示第二行第四列的单元格
如上图，每个空白单元格中能填的数字都是有限制的。
例如：（1，1）就只能填7和8；而（6，4），只能填8；
那些只能填一个数字的空白单元格，我们称之为唯一数单元格，上图中（6，4）就是唯一数单元格
解题的顺序，就是从唯一数单元格开始，由于唯一数单元格只能填一个数，故先在这个单元格里填数。在这个单元格里填数，由于规则的定义，那么这个单元格所在的行、所在的列、所在的宫的其他单元格就不能再填这个数了。这些单元格能填的数的可能性就少了。有可能会产生新的唯一数单元格。
在相当的一些的数独题目中，从唯一数单元格开始填数，不停的在唯一数单元格填数就可以把数独解出来。
如果在解题的过程中，发现某些空白单元格没有数字能填这样的单元格称之为无解单元格，那就说明：要么这个数独没有解；要么之前的解题过程有问题，需要返回检查之前的解题过程查看。
但是还有不少的数独的题目，在解题的过程中，在还有空白单元格的情况下，却找不到唯一数单元格，也就是意味着每个空白单元格中能填的数字至少有2个。我们称之为无唯一数单元格的状况
这个时候怎么办？我们找到其中一个可能数最少的空白单元格（这个没有定论，可以是可能数最少的空白单元格；也可以是第一个空白单元格；也可以是可能数最多的空白单元格，选哪个空白单元格对后面的解题是否有影响，没有证明过，不好妄下定论。凭感觉选可能数最少的空白单元格是最好的选择），由于能填的数字不止一个，先把当前的状态保存起来，再在能选的数字中选择一个数字填写（从小到大选择），然后继续求解下去。如果能解出最后的结果，说明当前的选择是正确的；如果后面的求解过程有问题，说明当前的数字的选择有问题，那么再挑选另一个数填写，继续求解。如果，所有的选择都求不出最后的结果，还是说明：要么这个数独没有解；要么之前的解题过程有问题，需要返回检查之前的解题过程查看。如此反复，直到求出最终的答案。
会有种极端的情况（可能性不大）。那就是在当前的空白单元格的所有可能的数字都选择了一遍，都没有解。而之前又没有出现无唯一数单元格的状况。那就说明这个数独根本就没有解
下图是数独求解的流程图
下面谈谈该算法的具体实现
1、数独状态的表示
用计算机来求解数独。基本的一点就是如何表示数独的状态。
用整形一维数组来表示数独的状态
用Num（80）表示数独的状态（数组的下标从0开始），数独是一个二维表格，而数组是一维数组。那么就存在一维和二维之间的转换
一维数组的下标Index（小标从0开始）和二维下标X、Y（下标从0开始）之间的转换公式
一维到二维的转换
X=Int（Index/9）
Y=Index mod 9
二维到一维的转换
Index=X*9+Y
数组中的每个整数表示数独对应的单元格的状态
正数表示空白单元格能填的数的组合，用二进制表示。用位来表示该单元格是否能填相应的数字，1表示能填，0表示不能填。
如文章开始的数独的单元格（1，1）可能填7和8，则第7位和第8位上是1（位数是从后往前数），其余位都是0，用整数表示就是Num（0）=0110000002=192
每在单元格中填一个数字，则把相应的行、列、宫中其余的单元格把该数字去掉。
我们可以充分利用位运算来简化去数字的过程。如：要把单元格去掉7这个数字的可能。首先7对应的二进制位0010000002，取其反数得到1101111112，再和目标单元格的数值进行AND的位运算，来实现去除该单元格7这个数字的可能性（由于位运算的便捷，不需要考虑该单元格是否原本包含7这个数字的可能性）。
如：（1，1）=0110000002 AND 1101111112=0100000002，去除7这个可能性，只剩8这个可能性了，也就是成为唯一数单元格
再比如：（1，9）=0100000102 AND 1101111112=0100000102，原本单元格就没有7这个可能性，执行位运算后，还是原来的可能性，没有发生变化。
负数表示该单元格已经确定的数，例如：（1，2）=-6，表示该单元格已近填了数字6
0表示该单元格既没有填确定的数字，也没有可填数的可能性。也就是上文说的无解单元格
为了算法中计算的方便，事先把这些二进制数都缓存起来，用一个一维的数组表示
用数组V来表示各个位对应的数字
V（0）=0000000012=1
V（1）=0000000102=2
V（2）=0000001002=4
V（3）=0000010002=8
V（4）=0000100002=16
V（5）=0001000002=32
V（6）=0010000002=64
V（7）=0100000002=128
V（8）=1000000002=256
V（9）=1111111112=511
数字7对应的二进制数为V（6）=0010000002=64，7的反数为V（9）-V（6）=1101111112=447
每个单元格初始的值都是V（9）=1111111112=511
2、如何获得一个单元格的可填数的个数
由于是用二进制来表示单元格的状态，那么可填数的个数就是该数字中1的个数。我们之前有一个很方便的方法快速计算一个数中1的个数，参看算法的强大——快速计算一个正二进制整数中包含多少个1。
3、状态的缓存
依据之前的说法，在碰到无唯一数单元格的情况时，要把当前的状态缓存起来。考虑到实际情况，从算法的角度上来说，用栈（先进后出）这个数据结构来实现比较合适。可以自己写一个栈的实现。但是，目前很多的编程语言都实现了基本的数据结构，提供了基本的数据结构的类和方法供我们调用。
以Visual Studio为例，它有Stack这个类，实现了栈的基本操作。有两个栈的方法：Push（压栈）——把数据写到栈里面；Pop（出栈）——把数据从栈里提出来，并删除栈中的数据。
4、代码说明
基本的变量
Private _Num(80) As Integer Private _V(9) As Integer Private _S As System.Text.StringBuilder Private _HasString As Boolean
_Num数组表示数独的状态；_V数组是辅助数组，缓存常用的二进制数
_S是一个文本对象，保存数独求解的过程；_HasString是个开关变量，表示是否记录求解过程；这两个变量是辅助变量，仅仅起到记录的作用。
类的初始化
Public Sub New(Optional ByVal HasString As Boolean = True) Dim I As Integer _V(0) = 1 For I = 1 To 8 _V(I) = _V(I - 1) * 2 Next _V(9) = 511For I = 0 To 80 _Num(I) = _V(9) Next
_S = New System.Text.StringBuilder _HasString = HasString End Sub
代码的前半段生成V这个数组，_V（9）=511。后半段，初始化数独数组。由于是空白数独数组，故每个单元格的值都是_V（9）
在给定的单元格里移除某个数字的可能性代码
Private Function RemoveNum(ByVal Row As Integer, ByVal Col As Integer, ByVal Num2 As Integer) As Integer Dim Index As Integer = Row * 9 + Col If _Num(Index) > 0 Then _Num(Index) = _Num(Index) And Num2 Return _Num(Index) End Function3个参数，Row表示行，Col表示列（都是下标从0开始），Num2表示要去除的数的反码，以二进制表示。
例如：在（1，1）这个单元格去除7这个可能性，则调用RemoveNum（0，0，1101111112）
返回值是该单元格的状态值，如果返回0，表示该单元就成了无解单元格，要后面的代码做适当的处理
在给定的单元格填某个数的代码
Private Function SetNumPri(ByVal Row As Integer, ByVal Col As Integer, ByVal Num As Integer) As Boolean If (_V(Num) And _Num(Row * 9 + Col)) = 0 Then Return False _Num(Row * 9 + Col) = -(Num + 1) Num = _V(9) - _V(Num)Dim I As Integer, J As Integer
For I = 0 To 8 If RemoveNum(I, Col, Num) = 0 Then Return False If RemoveNum(Row, I, Num) = 0 Then Return False Next
Dim R1 As Integer = Int(Row / 3) * 3 Dim C1 As Integer = Int(Col / 3) * 3
For I = R1 To R1 + 2 For J = C1 To C1 + 2 If RemoveNum(I, J, Num) = 0 Then Return False Next Next
Return True End Function
3个参数，Row表示行，Col表示列，Num表示要填充的数字（下标从0开始），这个方法是供类内部调用，从程序的角度来说，程序处理下标，从0开始比从1开始要来得简单。
例如：在（1，1）中填入数字7，则调用SetNumPri（0，0，6）
代码的第1行，先利用位运算判断当前单元格能否填制定的数字，不能填返回False
代码的第2行，设置当前单元格为指定数字，之前说了，用负数表示已填好的数字
代码的第3行，获得当前数字的反码，为后面去除该单元格所在的行、列、宫的其他单元格的该数字做准备
后面有两个循环，第一个循环去除行、列的其他单元格的该数字；第二个双循环去除宫的其他单元格的该数字。在调用RomoveNum方法时，若返回的是0，说明产生了无解单元格，那说明在这个单元格填该数字是不合理的，故返回False
当全部的代码都能顺利完成了，说明这个单元格填该数字是合理的，返回True
该方法的另一个重载形式
Private Function SetNumPri(ByVal Index As Integer, ByVal Num2 As Integer) As Boolean Dim Row As Integer = Int(Index / 9) Dim Col As Integer = Index Mod 9 Dim I As Integer For I = 0 To 8 If _V(I) = Num2 Then Exit For Next Return SetNumPri(Row, Col, I) End Function这也是一个供内部调用的方法，两个参数，Index是一维数组的下标；Num2是数字的二进制的形式。整个方法就是参数的转换，然后调用之前的方法
下面是两个供外面调用的方法
Public Function SetNum(ByVal Row As Integer, ByVal Col As Integer, ByVal Num As Integer) As Boolean Return SetNumPri(Row - 1, Col - 1, Num - 1) End FunctionPublic Function SetLine(ByVal Row As Integer, ByVal ParamArray Num() As Integer) As Boolean If Num.Length = 0 Then Return True
Dim I As Integer
For I = 0 To IIf(Num.Length - 1 > 8, 8, Num.Length - 1) If Num(I) > 0 AndAlso SetNumPri(Row - 1, I, Num(I) - 1) = False Then Return False Next
Return True
End Function
第一个方法是公开给外部调用的填数的方法。对外来说，从直观性上来说，下标是从1开始比较合适，但是内部的方法从0开始比较好。
如在（1，1）填7，调用SetNum（1，1，7），这个方法转而调用SetNumPri（0，0，6）
这个方法一般用在初始化数独时候调用
第二个方法也是公开给外部的方法，一次填写一行数的方法，如果是空白单元格，则用0替代
如