创建一个数独游戏
如何快速创建一个数独游戏。
引言
这是生成/解决/使用数独网格的后台代码。我不会描述或提供显示网格的代码，因为有无数种方法可以做到这一点，我将让你决定你想要如何实现。
但是，我将提供一个带界面的可执行文件来演示如何使用它。
背景
此代码在编写时考虑到了速度。
Using the Code
在 zip 文件中，我提供了一个项目文件、一个模块和四个类。类中的代码可以移到模块中；由于其中的函数/子程序是共享的，我决定以这种方式拆分它，以便更清晰。让我们从项目文件开始；其中有一个主要内容：我在高级编译器设置中启用了“删除整数溢出检查”，其他所有设置都是默认设置。
我在模块中声明了以下变量
Private Const debugTime As String = "hh:mm:ss.fffffff"
Private r As New Random()
Private iSquare As Integer
Private squareExp2 As Integer
Private squareExp3 As Integer
Private gridRow() As Integer
Private gridCol() As Integer
Private gridbox() As Integer
Private gridbox1() As Integer
Private selectedGameType As gridSize = gridSize.grid9X9
Private Enum gridSize
grid9X9 = 3
grid16X16 = 4
End Enum
Private gameType As benchType = benchType.random
Private Enum benchType
random
solve
End Enum
我通过以下方式初始化了 iSquare、squareExp2 和 squareExp3
iSquare = selectedGameType
squareExp2 = iSquare * iSquare
squareExp3 = squareExp2 * squareExp2 - 1
为了填充行和列数组，我使用了以下代码
For i = 0 To squareExp3
gridCol(i) = i Mod squareExp2
gridRow(i) = i - gridCol(i)
Next
起初，我用这段代码填充方块数组，但我不喜欢它
For j = 0 To squareExp2 - 1
For i = 0 To squareExp2 - 1
box = (j * squareExp2) + i
gridbox(box) = ((j \ Square) * squareExp2 * Square) + _
((j Mod Square) * Square) + (i \ Square) * squareExp2 + (i Mod Square)
gridbox1(gridbox(box)) = ((j \ Square) * squareExp2 * Square) + _
(((j Mod Square) * Square) * Square)
Next
Next
于是，我去了 stackoverflow 并提交了这个问题 问题。
我收到了另一位用户的以下回复
因此，对于
gridbox，您基本上是取i和j，并在base(square)中交错它们的数字。例如，给定base(scale)中的i和j，您正在计算：i(2)j(2)i(1)j(1)，其中 (n) 表示base(scale)中的数字。因此，这很容易加速：只需记录每个数字对gridbox(...)最终值的贡献。加速
gridbox1(...)甚至更容易。基本上，你正在计算Square * Square *(j\Square * Square + (j Mod Square))现在，
(j Mod Square)展开为(j - j\Square*Square)这使得上述内容简化为
Square * Square *(j\Square * Square + (j - j\Square*Square))这简化为
Square * Square *(j\Square * Square + j - j\Square*Square)这简化为
Square * Square * (j)
阅读回复后我修改了代码，如下所示
Dim box As Integer
Dim Square2 As Integer = iSquare * iSquare
Dim Square3 As Integer = Square2 * iSquare
Dim Square4 As Integer = Square2 * Square2
Dim j2_offset As Integer, j1_offset As Integer
Dim j1_interleaved_offset As Integer, i2_offset As Integer
Dim i2_interleaved_offset As Integer, j_offset_value As Integer
Dim offset_value As Integer, interleaved_value As Integer
For j2 As Integer = 0 To iSquare - 1
j1_offset = 0
j1_interleaved_offset = 0
For j1 As Integer = 0 To iSquare - 1
i2_offset = 0
i2_interleaved_offset = 0
j_offset_value = j2_offset + j1_offset
For i2 As Integer = 0 To iSquare - 1
offset_value = j_offset_value + i2_offset
interleaved_value = j2_offset + _
i2_interleaved_offset + j1_interleaved_offset
For i1 As Integer = 0 To iSquare - 1
box = offset_value + i1
gridbox(box) = interleaved_value + i1
gridbox1(gridbox(box)) = j_offset_value
Next
i2_offset += iSquare
i2_interleaved_offset += Square2
Next
j1_offset += Square2
j1_interleaved_offset += iSquare
Next
j2_offset += Square3
Next
为什么要执行所有这些步骤来填充这些数组？为了能够这样使用它们
根据位置（在本例中为 i）获取一行中的所有数字
j = myGridRow(i)
For x = j To (j + squareExp2) - 1
foundNumber(grid(x)) = grid(x)
Next
获取一列中的所有数字
j = myGridCol(i)
For x = j To squareExp3 Step squareExp2
foundNumber(grid(x)) = grid(x)
Next
要获取一个方块中的所有数字，通常你会这样做
k = (gridRow(pos) \ iSquare) * iSquare
l = (gridCol(pos) \ iSquare) * iSquare
For i = l To l + iSquare - 1
For j = k To k + iSquare - 1
box = (j * squareExp2) + i
foundNumber(grid(box)) = grid(box)
Next
Next
但是，由于通过 gridbox 和 gridbox1 数组你已经知道了方块内的每个位置，所以你只需要这样做
j = myGridbox1(i)
For x = j To (j + squareExp2) - 1
foundNumber(grid(myGridbox(x))) = grid(myGridbox(x))
Next
对于这些类，我总是传递所有预先计算的变量、数组和随机变量。
返回随机网格的函数返回一个一维数组。要显示它，你只需要使用一个循环，并在每 squareExp2 次后创建一个新行。例如
Dim msg As String = Nothing
For i = 0 To squareExp3
If i Mod squareExp2 = 0 Then
msg += vbCrLf
End If
msg += grid(i).ToString
Next
MsgBox(msg)
要生成一个网格，我的函数中有两个主要部分。第一部分包含回溯逻辑，第二部分查找特定位置的所有可能数字，然后从结果可能的数字列表中选择一个随机数字。
Grid 数组的大小为 squareExp3，我通过循环来按顺序填充它。
让我们从回溯逻辑开始
If count = 0 Then
x = i
If tried > squareExp2 Then
tried = 0
If i > squareExp2Mult2 Then
i -= squareExp2Mult2 - 2
Else
i = 0
End If
Else
tried += 1
i -= squareExp2 - 2
End If
For j = i To x
grid(j) = 0
Next
End If
squareExp2Mult2 等于 squareExp2 * 2。
count 显示了上一个位置有多少种可能性，我将其初始化为1，这样当我开始循环时它就不会进入。
如果前一个位置没有可能的数字，代码将检查当前网格进入回溯逻辑的次数，如果对于 9x9 网格的例子，它进入了 10 次，它将检查当前位置 (i) 以确保它不会变成负值，并为同一个 9x9 网格移除最多 16 个数字；如果少于 10 次，则只移除 7 个数字。
完成此操作后，主循环计数器将改变，以便它可以继续填充网格。我选择了数字“16”和“7”。在我进行基准测试时，它们似乎是目前为止最好的数字，但如果你找到其他数字，请告诉我。
对于第二部分
j = myGridRow(i)
For x = j To (j + squareExp2) - 1
foundNumber(grid(x)) = grid(x)
Next
j = myGridCol(i)
For x = j To squareExp3 Step squareExp2
foundNumber(grid(x)) = grid(x)
Next
j = myGridbox1(i)
For x = j To (j + squareExp2) - 1
foundNumber(grid(myGridbox(x))) = grid(myGridbox(x))
Next
count = 0
For x = 1 To squareExp2
If foundNumber(x) = 0 Then
foundNumberRnd(count) = x
count += 1
End If
foundNumber(x) = 0
Next
If count > 1 Then
grid(i) = foundNumberRnd(r.Next(count))
Else
grid(i) = foundNumberRnd(0)
End If
我已经解释了前三个循环的工作原理，所以我将从“count = 0”这一行开始解释。
我遍历大小为 squareExp2 的 foundNumber 数组，以查找每个 0。当找到 0 时，意味着当前位置 (i) 有一个可能的数字，所以我将计数器 x 的值放入第二个数组 (foundNumberRnd) 中，该数组用于查找随机数，然后递增计数器。最后，我将 foundNumber 的值重置为 0，以便进行下一个循环（位置）。
如果找到不止一个数字，即 count > 1，我会在 foundNumberRnd 数组中选择一个随机数。否则，我选择 foundNumberRnd 数组中的第一个数字，这个数字可能是有效或无效的；如果它是无效数字，则表示 count 仍然为 0，并将触发回溯逻辑。返回提示的函数需要另外两个参数，实际的 grid() 和位置，它将返回一个一维数组。要使用结果，你只需要检查 1 到 squareExp2 之间的数组，并找到所有 0。
我写了一个函数来验证网格是否有效。你需要将 grid() 传递给函数，它将返回 true/false。
解决网格的函数远未完成，它仍在开发中。
注意，此逻辑中没有“停止”，因此如果网格无效或当前算法无法找到解决方案，您可能会陷入无限循环。该函数需要一个字符串来表示网格，或者您可以不传递任何内容来实际创建一个网格。找到解决方案后，它将返回一个数组，您可以使用用于生成器的代码来显示它。
关注点
在实现这段代码时，我学到了一些优化技巧。例如
- 数组仍然比
List(Of T)快。 - 在高级编译器设置中启用“移除整数溢出检查”可以提高性能。
- 一维数组比多维数组快得多，但更难使用。
- 最好在类/应用程序级别声明一个随机变量，而不是在子程序/函数中反复声明。
还有一些其他的小优化。
在我的家用电脑上，我每秒可以生成超过 53,000 个 9x9 随机网格，以及超过 310 个 16x16 随机网格。
历史
- 版本 1.3，2009-03-12。
- 版本 1.2，2009-03-10 .
- 版本 1.1，2009-03-08。
- 初始发布版本 1.0，2009-03-05。
更新了演示以修复调整大小时的错误。
添加了 Visual Studio 2005 的 Zip 文件。
添加了网格的生成方式。