- 浏览: 83677 次
-
文章分类
- 全部博客 (136)
- 我的技术资料收集 (98)
- 具体技术 (1)
- 的技术资料收集 (4)
- All Articles (1)
- 机器学习 Machine Learning (1)
- 网络编程 (1)
- java (2)
- ava (1)
- 零散技术 (1)
- C# (3)
- 技术资料收集 (1)
- CQRS (1)
- 数据库技术(MS SQL) (1)
- .Net微观世界 (1)
- Oracle SQL学习之路 (1)
- C/C++ (1)
- JS/JQ (1)
- Js封装的插件/实例/方法 (2)
- 敏捷个人 (2)
- Javascript (1)
- 程序设计---设计模式 (1)
- Bug (1)
- 未知分类 (1)
- 程序设计 (1)
- Sharepoint (1)
- Computer Graphic (1)
- IT产品 (1)
- [06]JS/jQuery (1)
- [07]Web开发 (1)
- .NET Solution (1)
- Android (3)
- 机器学习 (1)
- 系统框架设计 (1)
- Others (1)
- 算法 (1)
- 基于Oracle Logminer数据同步 (1)
- 网页设计 (1)
- 原创翻译 (1)
- EXTJS (1)
- Jqgrid (1)
- 云计算 (1)
最新评论
数独（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) = 511
For 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 Function
3个参数，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 Function
Public 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替代
如本文开始的数独，填写第一行代码就是SetLine（1，0，6，0，5，9，3，0，0，0）
几个辅助方法
Private Sub RestoreNum(ByVal L As List(Of Integer))
Dim I As Integer
For I = 0 To 80
_Num(I) = L.Item(I)
Next
AppendString("Restore Matrix")
End Sub
恢复L中的数据到数独数组中，L是之前缓存的数据。AppendString这个方法是将数据记录到文本对象
Private Function Get1Count(ByVal Value As Integer) As Integer
Dim C As Integer = 0
Do While Value > 0
Value = Value And (Value - 1)
C += 1
Loop
Return C
End Function
获得一个数中1的个数，也就是获得一个空白单元格的可填数的数目
例如：（1，1）=0110000002，Get1Count（0110000002）=2，说明（1，1）这个单元格能填2个数
Private Function GetIndexOfNum(ByVal Num As Integer, ByVal Index As Integer) As Integer
Dim I As Integer, K As Integer = 0
For I = 0 To 8
If (_V(I) And Num) <> 0 Then
K += 1
If K = Index Then Return I + 1
End If
Next
Return -1
End Function
获得指定数Num（二进制形式）的第Index个的可填数
还是以上面的为例，（1，1）=0110000002，
GetIndexOfNum（0110000002，1）=7，表示第1个可填数是7
GetIndexOfNum（0110000002，2）=8，表示第2个可填数是8
GetIndexOfNum（0110000002，3）=-1，表示没有第3个可填数
辅助记录函数
这些函数对求解算法没啥太大的帮助，仅仅是将求解的过程记录到文本中，以供日后研究参考
Private Function ReturnNumString(ByVal Num As Integer) As String
If Num < 0 Then Return "#" & (-Num) & " "
Dim I As Integer, S As String = ""
For I = 0 To 8
If (_V(I) And Num) <> 0 Then S &= (I + 1)
Next
Return S.PadRight(10)
End Function
返回一个数字的文本格式，如果是空白单元格，返回该单元格的所有可填数；如果是已填单元格，返回#+数字的字符串。返回的字符串经过对齐处理。
Private Function ReturnMatrix() As String
Dim I As Integer, J As Integer, S As String = ""
For I = 0 To 8
For J = 0 To 8
S &= ReturnNumString(_Num(I * 9 + J))
Next
S &= vbNewLine
Next
Return S
End Function
返回整个数独的状态文本
Private Sub AppendString(ByVal Text As String, Optional ByVal AppendMatrix As Boolean = True)
If _HasString = False Then Exit Sub
_S.AppendLine(Text)
_S.AppendLine()
If AppendMatrix = True Then
_S.AppendLine(ReturnMatrix)
_S.AppendLine()
End If
End Sub
将文本添加到文本对象，并根据AppendMatrix参数来决定是否将整个数独的状态添加到文本对象
Private Function IndexToXY(ByVal Index As Integer) As String
Return (Int(Index / 9) + 1) & "-" & (Index Mod 9 + 1) & " Num:" & -_Num(Index)
End Function
返回指定Index的坐标和已填的数，用于在文本对象中
Public Function CalculationString() As String
Return _S.ToString
End Function
对外公开的方法，返回文本对象，也就是之前记录的求解过程，共日后研究参考
主求解函数——算法的核心
下面的3个函数是算法的核心
Private Function FindMinCell() As Integer
Dim I As Integer, C As Integer
Dim tP As Integer = -1, tMin As Integer = 20
I = 0
Do
If _Num(I) > 0 Then
C = Get1Count(_Num(I))
If C = 1 Then
If SetNumPri(I, _Num(I)) = False Then Return -2
AppendString("SetNum " & IndexToXY(I))
If I = tP Then
tP = -1
tMin = 20
End If
I = -1
Else
If C < tMin Then
tP = I
tMin = C
End If
End If
End If
I += 1
Loop Until I > 80
Return tP
End Function
该函数是获得最少可能数的单元格（可填数大于2的空白单元格）
该函数返回值有3个可能性
返回值：-1，没有找到这样的单元格，函数从某个唯一数单元格开始填数，依次填下去，并且把所有的空白单元格都填满。这说明，求解结束。
返回值：-2，没有找到这样的单元格，函数从某个唯一数单元格开始填数，依次填下去，产生了无解单元格。说明之前的求解过程有错误或者说该数独无解
返回值：0-80，找到这样的单元格，并且当前的数独数组中不再存在唯一数单元格（函数直接会在唯一数单元格上填数）
Public Function Calculate() As Integer()
Dim I As Integer
Dim K As Integer
Dim Q As New Stack(Of List(Of Integer))
Dim L As List(Of Integer)
_S = New System.Text.StringBuilder
AppendString("Init Matrix")
K = FindMinCell()
Do While K <> -1
If K = -2 Then
If Q.Count = 0 Then
AppendString("Error!!!!!", False)
Return Nothing
End If
L = Q.Pop
K = L(82)
L.RemoveAt(82)
I = L(81) + 1
L.RemoveAt(81)
AppendString("Stack Pop " & Q.Count + 1, False)
RestoreNum(L)
K = FindNextK(Q, L, K, I)
Else
L = New List(Of Integer)
L.AddRange(_Num)
K = FindNextK(Q, L, K, 1)
End If
Loop
AppendString("Calculating Complete!!!!")
Dim V(80) As Integer
For I = 0 To 80
V(I) = -_Num(I)
Next
Return V
End Function
对外公开的主求解函数，返回最终结果的整形数组
首先解释一下栈对象Q，由于栈Q每次压栈的时候只能压一个对象，而当出现无唯一数单元格的情况的时候，需要将当前的数据缓存起来。需要缓存的内容有三个部分，分别是数独数组、找到的最少可能数的单元格的下标、最少可能数的单元格的选择填的第几个数。故用一个List（of Integer）对象将之前的三个内容缓存起来。L（0）—L（80）表示是数独数组，L（81）是最少可能数的单元格的下标，L（82）是最少可能数的单元格的选择填的第几个数。
该函数的主要是判断K的值，如上个函数所述，K的值主要有3种
K=-1，说明没有空白单元格，数独已经完美的求解完成，直接返回结果
K=-2，说明有无解单元格，那么判断栈Q中的数据，如果栈Q中没有数据，说明该数独无解；如果栈Q中有数据，那么把数据提出来，把数独的状态恢复到之前的情况。并从上次缓存的最少可能数单元格中，提取下一个可填数去继续进行尝试。
举例说明，缓存了0，1。说明上次尝试的是第1个单元格（下标从0开始）的第1个可填数。由于出现了无解单元格，说明第1个可填数是不正确的，那么继续尝试第2个可填数。调用的方法：FindNextK(Q, L, K, I)，之前I已经加过1了。
K=0-80，得到最少可能数的单元格的下标。从该单元格的第1个可填数开始尝试。调用的方法：FindNextK(Q, L, K, 1)
尝试可能数的函数是FindNextK，返回值也是分为3种，-1、-2、0-80。意义和上面一样
Private Function FindNextK(ByVal Q As Stack(Of List(Of Integer)), ByVal L As List(Of Integer), ByVal K As Integer, ByVal Index As Integer) As Integer
Dim J As Integer = GetIndexOfNum(_Num(K), Index)
Do While J <> -1
If SetNumPri(K, _V(J - 1)) = True Then
AppendString("Stack Push " & Q.Count + 1, False)
AppendString("SetNum MayBe " & IndexToXY(K))
L.Add(Index)
L.Add(K)
Q.Push(L)
K = FindMinCell()
Exit Do
End If
RestoreNum(L)
Index += 1
J = GetIndexOfNum(_Num(K), Index)
Loop
If J = -1 Then K = -2
Return K
End Function
辅助函数，获得尝试可能数的结果
首先，通过GetIndexOfNum获得当前可填数。如果返回值-1的话，说明当前已经没有可填数，出现无解单元格，直接返回值为-2
然后尝试在当前单元格填数，调用SetNumPri(K, _V(J - 1))，返回True表示该数能填，那么把当前的状态缓存到栈Q中，并通过FindMinCell函数获得下一个可能的K值，并返回；返回False表示该数不能填，恢复数据到数独数组，继续尝试下一个数。
至此该算法类的代码都说明完整了
在该算法中仅仅用了最基本的解法——摒除法。遇见唯一数单元格，就直接填数，如果遇见无唯一数单元格，则缓存数据，并对该单元格的所有可填数做尝试，直到求解出该数独为止。
会有人疑问，利用栈Q缓存数据，会不会极大的占用系统资源，导致无法解题的情况。以目前的情况来看，我用该算法求解了“程序员们都是不被世人所理解的真正天才吗?-请大家看这个数独的解法”中的号称最难的数独，并把求解的结果保存到文件后打开分析了一下，发现栈Q的缓存不超过20步，以20步为例，每步83*4字节，则一共20*83*4=6640字节<7K字节。远小于系统的承受能力。因此，不必担心系统的承受能力
如果，谁有好的数独的算法，欢迎交流，不吝赐教。
让我们实战看看成果，用该算法求解本文开头的数独，代码如下：
Dim tS As New clsSudoku
tS.SetLine(1, 0, 6, 0, 5, 9, 3, 0, 0, 0)
tS.SetLine(2, 9, 0, 1, 0, 0, 0, 5, 0, 0)
tS.SetLine(3, 0, 3, 0, 4, 0, 0, 0, 9, 0)
tS.SetLine(4, 1, 0, 8, 0, 2, 0, 0, 0, 4)
tS.SetLine(5, 4, 0, 0, 3, 0, 9, 0, 0, 1)
tS.SetLine(6, 2, 0, 0, 0, 1, 0, 6, 0, 9)
tS.SetLine(7, 0, 8, 0, 0, 0, 6, 0, 2, 0)
tS.SetLine(8, 0, 0, 4, 0, 0, 0, 8, 0, 7)
tS.SetLine(9, 0, 0, 0, 7, 8, 5, 0, 1, 0)
tS.Calculate()
My.Computer.FileSystem.WriteAllText("1.txt", tS.CalculationString, False)
该数独还是比较简单的，一路唯一数单元格到底
结果如下：
Calculating Complete!!!!
#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
下面是该算法类的完整代码
<style><!--.cf1 {color:#0000ff}.cf2 {color:#2b91af}.cf3 {color:#a31515}--></style>Public Class clsSudoku
Private _Num(80) As Integer
Private _V(9) As Integer
Private _S As System.Text.StringBuilder
Private _HasString As Boolean
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) = 511
For I = 0 To 80
_Num(I) = _V(9)
Next
_S = New System.Text.StringBuilder
_HasString = HasString
End Sub
Private Function Get1Count(ByVal Value As Integer) As Integer
Dim C As Integer = 0
Do While Value > 0
Value = Value And (Value - 1)
C += 1
Loop
Return C
End Function
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 Function
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 Function
Public 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
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
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
Private Function FindMinCell() As Integer
Dim I As Integer, C As Integer
Dim tP As Integer = -1, tMin As Integer = 20
I = 0
Do
If _Num(I) > 0 Then
C = Get1Count(_Num(I))
If C = 1 Then
If SetNumPri(I, _Num(I)) = False Then Return -2
AppendString("SetNum " & IndexToXY(I))
If I = tP Then
tP = -1
tMin = 20
End If
I = -1
Else
If C < tMin Then
tP = I
tMin = C
End If
End If
End If
I += 1
Loop Until I > 80
Return tP
End Function
Public Function Calculate() As Integer()
Dim I As Integer
Dim K As Integer
Dim Q As New Stack(Of List(Of Integer))
Dim L As List(Of Integer)
_S = New System.Text.StringBuilder
AppendString("Init Matrix")
K = FindMinCell()
Do While K <> -1
If K = -2 Then
If Q.Count = 0 Then
AppendString("Error!!!!!", False)
Return Nothing
End If
L = Q.Pop
K = L(82)
L.RemoveAt(82)
I = L(81) + 1
L.RemoveAt(81)
AppendString("Stack Pop " & Q.Count + 1, False)
RestoreNum(L)
K = FindNextK(Q, L, K, I)
Else
L = New List(Of Integer)
L.AddRange(_Num)
K = FindNextK(Q, L, K, 1)
End If
Loop
AppendString("Calculating Complete!!!!")
Dim V(80) As Integer
For I = 0 To 80
V(I) = -_Num(I)
Next
Return V
End Function
Private Sub RestoreNum(ByVal L As List(Of Integer))
Dim I As Integer
For I = 0 To 80
_Num(I) = L.Item(I)
Next
AppendString("Restore Matrix")
End Sub
Private Function GetIndexOfNum(ByVal Num As Integer, ByVal Index As Integer) As Integer
Dim I As Integer, K As Integer = 0
For I = 0 To 8
If (_V(I) And Num) <> 0 Then
K += 1
If K = Index Then Return I + 1
End If
Next
Return -1
End Function
Private Function FindNextK(ByVal Q As Stack(Of List(Of Integer)), ByVal L As List(Of Integer), ByVal K As Integer, ByVal Index As Integer) As Integer
Dim J As Integer = GetIndexOfNum(_Num(K), Index)
Do While J <> -1
If SetNumPri(K, _V(J - 1)) = True Then
AppendString("Stack Push " & Q.Count + 1, False)
AppendString("SetNum MayBe " & IndexToXY(K))
L.Add(Index)
L.Add(K)
Q.Push(L)
K = FindMinCell()
Exit Do
End If
RestoreNum(L)
Index += 1
J = GetIndexOfNum(_Num(K), Index)
Loop
If J = -1 Then K = -2
Return K
End Function
Private Function ReturnNumString(ByVal Num As Integer) As String
If Num < 0 Then Return "#" & (-Num) & " "
Dim I As Integer, S As String = ""
For I = 0 To 8
If (_V(I) And Num) <> 0 Then S &= (I + 1)
Next
Return S.PadRight(10)
End Function
Private Function ReturnMatrix() As String
Dim I As Integer, J As Integer, S As String = ""
For I = 0 To 8
For J = 0 To 8
S &= ReturnNumString(_Num(I * 9 + J))
Next
S &= vbNewLine
Next
Return S
End Function
Private Sub AppendString(ByVal Text As String, Optional ByVal AppendMatrix As Boolean = True)
If _HasString = False Then Exit Sub
_S.AppendLine(Text)
_S.AppendLine()
If AppendMatrix = True Then
_S.AppendLine(ReturnMatrix)
_S.AppendLine()
End If
End Sub
Private Function IndexToXY(ByVal Index As Integer) As String
Return (Int(Index / 9) + 1) & "-" & (Index Mod 9 + 1) & " Num:" & -_Num(Index)
End Function
Public Function CalculationString() As String
Return _S.ToString
End Function
End Class
发表评论
相关推荐
关于数独的算法有很多种,最基本的有基拙挖掘法,唯一解法,侯选数置换法.查了很多资料但都没有找到完整的算法实现.花了30块银子到当当网上买了编程之美>>找到其中的章节,看完之后大失所望.其中的算法实现藏头露尾,...
3. 算法实现：数独的解法通常采用回溯算法，即深度优先搜索。当遇到无法填入数字的情况时，会回退到上一步，尝试其他可能性。同时，我们还需要实现一些辅助函数，如检查当前填入的数字是否正确，即该位置的数字是否...
本篇文章将深入探讨这些经典算法题目，并通过两个文档——"Java算法之经典题目篇.doc"和"JAVA经典算法40题.doc"中的内容来展开讨论。 首先，让我们了解一下算法的基础。算法是一系列明确的指令，用于解决特定问题或...
本项目“SimpleSudokuSolver”就是利用MATLAB进行的一个有趣的应用实例——数独求解器的开发。数独是一种逻辑谜题，通过填数字使每行、每列以及每个宫格内的数字均不重复，达到一种特定的完整状态。本文将详细介绍...
《SudokuConsole 06.03.07_sudokuCsharp_——探索C#实现数独解法的奥秘》 数独，一种源于18世纪末的逻辑推理游戏，近年来在全球范围内广受欢迎，其魅力在于通过数字排列挑战人们的逻辑思维与观察力。在编程领域，将...
之后，是游戏的核心部分——解数独算法。常见的解法有深度优先搜索（DFS）或暴力穷举。DFS同样利用回溯策略，逐个尝试填充空格，每次填充后检查是否违反数独规则，如果违反则回溯到上一步。当所有空格都填满且无误时...
在数独的特殊变种——靶形数独中，还引入了分值的概念，需要在满足规则的同时最大化总分数。 代码中使用C语言实现了解决数独的程序，主要函数包括`findx`和`findy`用于找到下一个待填充的格子，`cando`函数用于检查...
在本资源包中，主题聚焦于C语言的基础学习，特别是针对LeetCode编程挑战中的第36题——"有效的数独"。LeetCode是一个知名的在线编程练习平台，它提供了丰富的算法和数据结构题目，帮助程序员提升技能，特别是对于...
第四卷的第五册《C语言版Dancing Links1》专注于一种高效的算法——Dancing Links（舞蹈链接）。这个算法是解决回溯问题，特别是全排列、组合和子集问题的有效工具。Dancing Links是一种基于链表的数据结构，它巧妙...
《数独解析器sudokizer：Go语言的力量与智慧》 数独，这个源自日本的数字谜题，以其独特的逻辑魅力...sudokizer的源代码（sudokizer-main）是学习Go语言编程和理解数独解法算法的宝贵资源，值得开发者深入研究和借鉴。
1. **基础算法**：排序（如快速排序、归并排序）、查找（如二分查找、哈希查找）、图论（如最短路径、拓扑排序）、动态规划（如背包问题、最长公共子序列）、回溯法（如八皇后问题、数独解法）等。 2. **数据结构**...
经典的数独解法通常包含回溯法和候选数法（也称为隐含数法）。回溯法是一种试探性的方法，从当前空白格子开始尝试填入数字，如果发现违反了数独规则，则回退并尝试下一个可能的数字。候选数法则是在每个空白格子中...
《数独益智评测器——Java实现深度解析》 数独是一种广受欢迎的逻辑益智游戏，它基于九宫格的填数字规则，既锻炼玩家的思维能力，又具有高度的娱乐性。"SudokuEveluator"项目，正如其名，是一个用于评估数独谜题...
通过对这些AC代码的学习，我们可以深入理解各类算法的原理，并且通过实践来提高编程效率。同时，参考他人的解法也能拓宽思路，了解不同的编程风格和优化技巧。在实际的编程竞赛或工作中，这种积累和理解会成为我们...
《ACM程序设计题目分析——探索算法与竞赛智慧》 在信息技术领域，ACM（Association for Computing Machinery）国际大学生程序设计竞赛是一项具有极高影响力的赛事，它不仅锻炼参赛者的编程技能，更强调团队合作、...
8. **用户界面（可选）**：虽然未在描述中提及，但一个完整的数独解算器可能还包括一个用户友好的图形用户界面（GUI），让用户可以直接在界面上输入数独谜题并查看解法过程。 综上所述，"Sudoku-Solver"项目利用...
《算法X：跳舞链接在数独解法中的应用》 数独是一种广受欢迎的逻辑谜题，它基于九宫格的填数字游戏，要求每一行、每一列以及每一个小九宫格内数字1到9各出现一次且不重复。Donald Knuth，这位计算机科学界的泰斗，...
- 1086——1.cpp: 可能是关于回溯法的题目，用于解决如八皇后问题、N皇后问题、数独等。 4. **树与图的深度优先搜索（DFS）与广度优先搜索（BFS）** - 1088.cpp: 可能需要使用DFS或BFS来遍历树或图，解决树的...
《快速易用数独求解器——开源技术详解》 数独，作为一种广受欢迎的智力游戏，挑战着玩家的逻辑思维和推理能力。而“Quick and Easy Sudoku Solver”这款开源软件，正是为解决数独难题而生。它不仅提供快速解决方案...
而"SudokuSolver"则明确了我们的目标——创建一个解决数独谜题的程序。 在C#中，我们可以利用其强大的面向对象特性来构建数独模型。首先，创建一个表示数独单元格的类，包含值、是否已填入等属性，以及相应的操作...