另一个数独解算器和生成器
4.44/5 (29投票s)
一个帮助您解决数独问题或检查数独问题是否只有一个解的程序。
引言
另一个数独解算器和生成器，是 CodeProject 上的第一个（虽然是用 VB 写的）。它可以动态搜索给定数独问题的所有解。界面很简单，搜索是连续的且非常快。因此，如果您想生成自己的问题，它会很有用。
数独
本文的大部分内容摘自：http://en.wikipedia.org/wiki/Sudoku。请参阅它以了解有关数独的更多详细信息。
来自维基百科，自由的百科全书
数独（日语：数独, sūdoku），有时拼写为 Su Doku，是一种基于逻辑的放置谜题，在美国也被称为 Number Place。United States。 经典谜题的目的是在由 3x3 子网格（称为“区域”）组成的 9x9 网格的每个单元格中输入从 1 到 9 的数字，从某些单元格中给出的各种数字（“已知数字”）开始。每行、每列和每个区域必须仅包含每个数字的一个实例。完成拼图需要耐心和逻辑能力。虽然最初于 1979 年出版，但 Sudoku 最初在 1986 年在 日本流行起来，并在 2005 年获得了国际性的普及。
解决谜题
该程序使用一种称为“回溯搜索”的技术，根据维基百科。
这意味着它为第一个单元格（比如左上角）分配一个值（比如 1，或最接近 1 的可用数字），然后继续为下一个可用单元格分配下一个可用值（比如 2）。这种情况一直持续到发生冲突为止，在这种情况下，为上次更改的单元格使用下一个替代值。如果单元格无法填充，则程序向后退一级（从该单元格），并在更高级别尝试下一个值（因此得名回溯）。
这种方法非常简单，它可以在不到一分钟的时间内解决大多数问题。
速度提升 1
为了提高速度，该程序还跟踪每行、每列和 3x3 框中已使用的值。使用了三个数组，horz()、vert() 和 box()。horz(0) 指示第一条水平线上已经输入了哪些单元格。horz(1) 指示第二条水平线上已经输入了哪些单元格...
要了解可以在第 3 行第 2 列的单元格中填写什么值，程序必须检查 horz(3)、vert(2) 和 box(0)。
此外，每个值都使用 9 位二进制掩码进行编码。
- 数独值 1 用 1 编码
- 数独值 2 用 2 编码
- 数独值 3 用 4 编码
- 数独值 4 用 8 编码
- ...
- 数独值 9 用 256 编码
二进制格式非常方便；为了检查第 3 行第 2 列中填写了哪个值，程序可以执行
dim played as integer
played = horz(3) or vert(2) or box(0)
速度提升 2
第二个最好的改进非常简单。像大多数游戏解算器一样，这个问题可以看作是一个树解析程序。同样，像这种类型的大多数问题一样，最好首先从最大约束开始。因此，程序不是尝试填写左上角的第一个单元格，而是找到具有较少拟合值的单元格，并首先填写该单元格。
' try to find the cell with the most constraints
For i As Integer = 0 To 81 - 1
curCell = CellsArray(i)
With curcell
If .played = False Then
If .forcedVal > 0 Then
' found a very good one
bestCell = curCell
Exit For
Else
' try to calculate the constraints for curCell
Dim pos As Integer = horz(.y) Or vert(.x) Or box(.box)
curCellConstraint = nbBits(pos)
If curCellConstraint > constraintMax Then
bestCell = curCell
constraintMax = curCellConstraint
If constraintMax = 9 Then Exit For
End If
End If
End If
End With
Next
生成谜题
创建数独时，您必须记住它只能有一个解决方案；否则，它就不被认为是真正的数独。只需在演示程序中输入值，直到它显示解决方案的数量 = 1。
结论
数独不是用计算机解决的最复杂或最有趣的问题。如果您想要一个更复杂的问题，请查看我今年早些时候发布的Mac Mahon 文章。如果您知道任何您认为有趣的问题或难题，请写信给我或在下面的论坛中留言。我希望有些人会发现这个程序很有趣。我已尽力使其易于使用；欢迎您的评论。
历史
- 2005 年 12 月 9 日 - 首次提交。