Sudoku 算法：在 0.018 秒内生成有效的 Sudoku

• 下载源代码 - 31.8 KB

引言

当我设计本文所基于的项目时，重点并非是实现一个快速的 Sudoku 生成算法。在各种意图和目的上，我已经在之前的项目中实现了这一点。不，这个项目是为了进一步挑战自己，学习处理问题的新方法，并总体上用我新学到的东西来改进我之前的代码。我当时并不知道，我会将我曾经的最佳 5 秒算法缩短到仅仅 0.07 秒。现在回头看，这似乎很明显。

目标

这个项目的目标是创建一个快速、简洁且可靠的 Sudoku 算法。为了做到这一点，我使用了三个主要部分：一个专门的结构体、ArrayList 和泛型 List。

这种组合和回溯技术的应用，达到了我预期的目标。一个不会出错的 Sudoku 生成器，代码行数少于 300 行，并在 0.07 秒内生成一个 Sudoku。这已经很令人印象深刻了，但感谢 Keith B.、Imperiatus 和 Spirch，现在该生成器平均可以在 0.018 秒内生成一个 Sudoku。

概述

什么是回溯

回溯算法在 Sudoku 中的基本原理是，一次向前移动一个格子，以生成一个可行的 Sudoku 棋盘。当出现问题时，算法会回退一步，尝试另一条路径。本质上，这就像在迷宫中行走，带着一根金线，在死胡同里来回穿梭，直到找到正确的出路。通过随机放置数字并试图让它们匹配，几乎不可能生成一个有效的 Sudoku。同样，使用随机放置方法的回溯同样无效（相信我，我两者都试过了）。回溯在以线性方式进行时效果最好。如果正确执行，它会快速、有效且可靠。下图显示了算法的一般流程。

数独

万一你忘记了或不确定。Sudoku 只有一个规则：每个数字从 1 到 9 必须在每一行、每一列和每个 3x3 的区域中放置一次，且仅放置一次。

何时回溯

好的，让我们以上图为例。我们已经顺利完成了前 17 个数字，但当涉及到为第 18 个数字找到一个有效的匹配项时，却没有有效的选项。除了 1 之外的所有数字都在这一行中使用了，但 1 已经在上方、同一列和同一区域中使用过了。因此；我们必须回溯，在这种情况下，回溯到 6。将 6 改为 1 将解决这个问题。

回溯的关键

回溯最重要的部分，顾名思义，就是跟踪已经尝试过的内容和位置，或者在这个例子中，是什么还没有在某个位置尝试过。在这个例子中，我使用了一个泛型列表的 ArrayList。

Dim Available(80) as List(Of Integer)

这样，Sudoku 的每个格子都有自己独立的数值列表，告诉算法在该格子中尝试过哪些数字。这样，当需要选择另一个数字时，唯一可用的数字就是那些尝试过的数字。

算法

你会注意到，算法调用了许多其他函数、子程序和最重要的“结构体”，我还没有讲到。为了方便理解，我已经为它们编号并进行了说明。

Public Sub GenerateGrid()

    Clear()
    Dim Squares(80) As Square 'an arraylist of squares: see line 86
    Dim Available(80) As List(Of Integer) 'an arraylist of generic lists (nested lists)
    'we use this to keep track of what numbers we can still use in what squares
    Dim c As Integer = 0 'use this to count the square we are up to

    For x As Integer = 0 To Available.Length - 1
        Available(x) = New List(Of Integer)
        For i As Integer = 1 To 9
            Available(x).Add(i)
        Next
    Next

    Do Until c = 81 'we want to fill every square object with values
        If Not Available(c).Count = 0 Then 	'if every number has been tried 
					'and failed then backtrack
            Dim i As Integer = GetRan(0, Available(c).Count - 1)
            Dim z As Integer = Available(c).Item(i)
            If Conflicts(Squares, Item(c, z)) = False Then 	'do a check with the 
							'proposed number
                Squares(c) = Item(c, z) 	'this number works so we add it to the 
					'list of numbers
                Available(c).RemoveAt(i) 'we also remove it from its individual list
                c += 1 'move to the next number
            Else
                Available(c).RemoveAt(i) 	'this number conflicts so we remove it 
					'from its list
            End If
        Else
            For y As Integer = 1 To 9 'forget anything about the current square
                Available(c).Add(y) 'by resetting its available numbers
            Next
            Squares(c - 1) = Nothing 'go back and retry a different number 
            c -= 1 'in the previous square
        End If
    Loop

    Dim j As Integer ' this produces the output list of squares
    For j = 0 To 80
        Sudoku.Add(Squares(j))
    Next

     'This algorithm produces a Sudoku in an average of 0.018 seconds, 
     'tested over 5000 iterations
     End Sub

1. Clear 简单地删除之前生成的 Sudoku（如果有的话）。

   Public Sub Clear()
       Sudoku.Clear()
   End Sub

2. Square 是我给结构体起的名字。square 的每个实例代表一个对象，该对象包含关于每个 square 的值、索引和相对位置的信息。它包含其区域（3x3 区域）、行、列、索引和值。

   Public Structure Square
       Dim Across As Integer
       Dim Down As Integer
       Dim Region As Integer
       Dim Value As Integer
       Dim Index As Integer
   End Structure

3. GetRan 检索一个介于 0 和当前列表最后一个索引之间的随机数，这意味着它抓取了一个剩余数字的索引。

   Private Function GetRan(ByVal lower As Integer, ByVal upper As Integer) _
   	As Integer
       Dim r As New Random
       GetRan = r.Next(lower, upper - 1)
   End Function

4. Conflicts，可能是整个算法中最重要的函数。它告诉我们我们正在考虑使用的数字是否有效。为此，它获取当前已生成的格子，并将它们与一个尚未生成的格子的实例进行比较。这个测试格子（“假设”）是在下面的“Item”函数中创建的。

   Private Function Conflicts(ByVal CurrentValues As Square(), _
   	ByVal test As Square) As Boolean
         
   For Each s As Square In CurrentValues
       If (s.Across <> 0 And s.Across = test.Across) OrElse _
              (s.Down <> 0 And s.Down = test.Down) OrElse _
              (s.Region <> 0 And s.Region = test.Region) Then
               
           If s.Value = test.Value Then
               Return True
           End If
       End If
   Next
   
   Return False
   End Function

5. Item 接收给定的值和给定的索引，并返回一个包含所有相关信息的格子项。它通过调用 3 个其他函数来获取格子的行、列和区域。这些其他函数使用简单的数学来确定行、列等。

   Private Function Item(ByVal n As Integer, ByVal v As Integer) As Square
       n += 1
       Item.Across = GetAcrossFromNumber(n)
       Item.Down = GetDownFromNumber(n)
       Item.Region = GetRegionFromNumber(n)
       Item.Value = v
       Item.Index = n - 1
   End Function
   
   Private Function GetAcrossFromNumber(ByVal n As Integer) As Integer
       Dim k As Integer
       k = n Mod 9        
       If k = 0 Then Return 9 Else Return k
   End Function
   
   Private Function GetDownFromNumber(ByVal n As Integer) As Integer
       Dim k As Integer
       If GetAcrossFromNumber(n) = 9 Then
           k = n\9   
       Else
           k = n\9 + 1
       End If
       Return k
   End Function
   
   Private Function GetRegionFromNumber(ByVal n As Integer) As Integer
       Dim k As Integer
       Dim a As Integer = GetAcrossFromNumber(n)
       Dim d As Integer = GetDownFromNumber(n)
   
       If 1 <= a And a < 4 And 1 <= d And d < 4 Then
           k = 1
       ElseIf 4 <= a And a < 7 And 1 <= d And d < 4 Then
           k = 2
       ElseIf 7 <= a And a < 10 And 1 <= d And d < 4 Then
           k = 3
       ElseIf 1 <= a And a < 4 And 4 <= d And d < 7 Then
           k = 4
       ElseIf 4 <= a And a < 7 And 4 <= d And d < 7 Then
           k = 5
       ElseIf 7 <= a And a < 10 And 4 <= d And d < 7 Then
           k = 6
       ElseIf 1 <= a And a < 4 And 7 <= d And d < 10 Then
           k = 7
       ElseIf 4 <= a And a < 7 And 7 <= d And d < 10 Then
           k = 8
       ElseIf 7 <= a And a < 10 And 7 <= d And d < 10 Then
           k = 9
       End If
       Return k
   End Function

更多关于结构体

如果你像我一样，在开始这个为期两天的项目时对结构体完全陌生，那么这里有一个关于它是如何工作的简要概述。当你创建一个结构体的实例时，就像我每次创建 'square' 时一样。结构体本身中定义的变量作为属性的一部分被创建。它们可以被读取和写入，但至关重要的是它们是实例的一部分，就像文本框中的文本一样。通过这种方式，你可以创建一个全新的、极其有用/通用的对象，例如 Sudoku square。拥有一个自定义结构体列表的好处是能够访问单个项并提取单个值。例如：

Dim Test as Integer =  SudoGen.Sudoku.Items(0).value

学习它们最好的方法要么是阅读，要么是多动手实践，直到你掌握窍门。我推荐后者，经验无与伦比。

列表的好处

使用列表（整数）最有益的部分是它在删除项目时自动调整自身的方式。当你取出一个项目时，就像一个 listbox，下一个项目就会获得它的索引，这意味着在使用 GetRan 时，它不是一个碰运气的事情，每个项目总有一个可用的数字。

Using the Code

为了方便使用，讨论的代码被编译在一个名为 SudoGen 的模块中。易于访问，易于使用，易于集成到无数项目中。

要生成一个 Sudoku，就像这样简单：

SudoGen.GenerateGrid

然后，一旦 Sudoku 生成完毕，就可以轻松访问输出。这些会一直保留，直到创建新的网格或调用 SudoGen.Clear 函数。

SudoGen.Sudoku 'A list(of square) : The output grid

关注点

将模块中的组件移除并在你的主类中使用它们可能更有用，因为它将允许你对代码做不同的事情。例如，你可以跟踪生成器的进度以显示给用户。

这与本程序关系不大，但我相信有些细菌使用回溯来找到通往食物源的最直接路径，探测每一个方向，直到找到足够大的食物源来喂养整个群体，然后未被使用/不成功的部门为了群体的最大利益而消失。我觉得有点相似。如果大自然认为这是最有效的方法，那么我认为同意这是一个明智之举。

历史

• 发布日期：2008年1月26日，下午7:04 AEDST
• 更新日期：2008年1月26日，下午8:50 AEDST
• 更新日期：2008年1月27日，上午9:00 AEDST
• 将 Sudoku 创建速度从平均 6-20 秒提高到 0.07 秒
• 更新日期：2008年2月3日，上午11:20 AEDST
• 添加了 Keith B. 的建议，将生成器速度从 0.07 提高到 0.0452
• 更新日期：2009年2月18日，上午10:59 AEDST
• 添加了 Imperiatus 和 Spirch 的建议，谢谢你们
• 更新了源 zip 和文章代码
• 现在平均运行速度为 0.018