数独算法:在0.018秒内生成有效的数独（译文）

原文地址：https://www.codeproject.com/Articles/23206/Sudoku-Algorithm-Generates-a-Valid-Sudoku-in-0-018

原文作者：The ANZAC

译文由本站 robot-v1.0 翻译

前言

An article about the simple, yet often annoying to achieve, backtracking algorithm for Sudoku generation.

有关数独生成的简单但通常很烦人的回溯算法的文章.

• 下载源31.8 KB(Download source - 31.8 KB)

介绍(Introduction)

当我设计本文所基于的项目时,与为Sudoku生成快速算法无关.出于所有目的和目的,我已经在上一个项目中实现了这一目标.不,这个项目的目的是进一步测试自己,以学习处理事物的新方法,并总体上以我学到的新东西改进我以前的代码.我几乎不知道我会把历史上最好的5秒算法减少到仅0.07秒算法.现在我看它,它看起来是如此明显.(When I designed the project this article is based on, it was much less about producing a fast algorithm for Sudoku generation. For all intents and purposes, I had already achieved this in a previous project. No, this project was about testing myself that little bit further to learn new ways of dealing with things and, overall, improving my previous code with the new things I had learnt. Little did I know I’d reduce my all time best 5 second algorithm to a mere 0.07 second algorithm. Now I look at it, it seems so obvious.)

目标(Aim)

该项目的目的是创建一种快速,简短和可靠的Sudoku算法.为此,我使用了三个主要部分:专门的结构,数组列表和通用列表.(The aim of this project was to create a fast, short and reliable Sudoku algorithm. To do this, I used three main parts; a specialized structure, array lists and generic lists.)

回溯技术的这种结合和应用的结果正是我的目标.不会出错的Sudoku生成器,其代码少于300行,并在0.07秒内生成了Sudoku.这足够令人印象深刻,但是多亏了Keith B.,Imperiatus和Spirch,现在该生成器现在可以平均以0.018秒的速度产生数独了.(The result of this combination and application of the backtracking technique has resulted in exactly what I aimed for. A Sudoku generator that does not make a mistake, is less than 300 lines of code and makes a Sudoku in 0.07 seconds. That was impressive enough but thanks to Keith B., Imperiatus and Spirch, now the generator can now produce a Sudoku at an average of 0.018 seconds.)

破败不堪(The Rundown)

什么是回溯(What is Backtracking)

关于Sudoku,回溯算法的基本原理是向前工作,一次生成一个正方形,以生成一个有效的Sudoku网格.发生问题时,该算法将自己退后一步并尝试另一条路径.从本质上讲,这就像走过带有金线的迷宫并在死胡同中来回走动,直到找到正确的出路为止.通过随机绘制数字并尝试使它们合适来生成有效的数独几乎是不可能的.同样,使用随机放置方法回溯同样无效(相信我,我已经尝试过两种方法).回溯最好采用线性方法.如果正确完成,它是快速,有效和可靠的.下面是显示该算法一般流程的基本示意图:(The basic principle of a backtracking algorithm, in regards to Sudoku, is to work forwards, one square at a time to produce a working Sudoku grid. When a problem occurs, the algorithm takes itself back one step and tries a different path. Essentially it’s like walking through a maze with some golden thread and going back and forth down dead ends until you find the right way out. It’s nearly impossible to produce a valid Sudoku by randomly plotting numbers and trying to make them fit. Likewise, backtracking with a random placement method is equally ineffective (trust me I’ve tried both). Backtracking best works in a linear method. It is fast, effective and reliable if done correctly. Below is a basic diagram showing the general flow of the algorithm:)

数独(Sudoku)

以防万一您忘记或不确定. Sudoku仅有一个规则,必须将每个从1到9的数字放置一次,并且只能在每个行,列和3x3区域中放置一次.(Just in case you have forgotten or are unsure. There is only one rule to Sudoku, every number form 1 to 9 must be placed once, and once only, in every row, column and 3x3 region.)

何时回溯(When to Backtrack)

好的,我们以该图像为例.到目前为止,我们对前17个数字的要求一直不错,但是要找到对第18个数字的有效匹配项时,没有有效的选择.在此行中,每个数字条1都已使用,但在同一列和同一区域中,上面已使用1.因此;我们必须回溯,在这种情况下回到6.将6更改为1将解决此问题.(Ok, let’s use this image as an example. We’ve been going fine so far for the first 17 numbers, but when it comes to finding a valid fit for the 18th number there are no valid options. every number bar 1 has been used on this line, but 1 has been used above, in the same column and the same region. Therefore; we have to backtrack, in this case back to the 6. Changing the 6 to a 1 would fix this problem.)

回溯的关键(The Key to Backtracking)

从逻辑上讲,回溯的最重要部分是跟踪已经尝试过的内容以及在哪里,或者在这种情况下,尚未尝试过的内容.在此示例中,我使用了通用列表的数组列表.(The most important part of backtracking is, logically, keeping track of what has already been tried and where, or, in this case, what hasn’t been tried where. For this example, I used an arraylist of generic lists.)

Dim Available(80) as List(Of Integer)

这样,数独的每个平方都有自己的值列表,告诉算法平方中没有尝试过的内容.这样,当必须选择另一个号码时,唯一可用的号码就是唯一尝试过的号码.(This way, each square of the Sudoku has its own individual list of values, telling the algorithm what hasn’t been tried in the square. This way when another number has to be chosen, the only available numbers are the only ones tried.)

算法(The Algorithm)

您会注意到该算法调用了许多其他函数,子函数和所有重要的"结构",这些我都还没有讨论过.为了便于理解,我对它们进行了编号和解释.(You’ll notice the algorithm calls a number of other functions, subs and the all important ‘Structure’, which I haven’t yet talked about. For ease of understanding, I have numbered and explained them.)

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

• Clear 只需删除先前产生的数独(如果有).(simply deletes the previously produced Sudoku, if any.)
• Square 是我为结构指定的名称.每个实例(is the name I have given to the structure. Each instance of) square 表示一个对象,其中包含有关每个对象的值,索引和相对位置的信息(represents an object that contains information about the value, index and relative position of each) square .它包含其区域(3x3区域),行,列,索引和值.(. It contains its region (3x3 area), row, column, index and value.)
• GetRan 检索介于0和当前列表的最后一个索引之间的随机数,这意味着它将获取其余数字索引之一.(retrieves a random number between 0 and the last index of the current list, which means it grabs one of the remaining numbers indexes.)
• 冲突可能是整个算法中最重要的功能.它告诉我们正在寻找的号码是否可以使用.为此,它将当前生成的正方形与未生成的正方形的实例进行比较.该测试方块(“假设”)是在"(Conflicts is, perhaps, the most important function in the overall algorithm. It tells us if the number we are looking at using, is going to work or not. To do this it takes the squares currently produced and compares them with an instance of a not yet produced square. This test square (‘the hypothetical’) is made in the ‘) Item ‘功能如下.(’ function below.)
• Item接受给定的值和给定的索引,并返回包含所有相关信息的正方形项.它通过调用其他3个函数来获取正方形的行,列和区域来执行此操作.这些其他功能使用简单的数学运算来确定行,列等.(Item takes the given value and the given index and returns a square item containing all relevant information. It does this by calling on 3 other functions to acquire the row, column and region of the square. These other functions use simple math to determine the row, column etc.)

有关结构的更多信息(More About the Structure)

如果您像刚开始这个为期两天的项目时那样刚接触结构,那么这里是其工作原理的简要概述.当您创建结构实例时,就像我每次创建"(If you are completely new to structures like I really was when I started this two day project then here is a brief rundown of how it works. When you create an instance of a structure like I did every time I created a ‘) square ‘.在结构本身中定义的变量是作为实例(如属性)的一部分创建的.它们可以读写,但它们是实例的关键部分,例如文本到文本框.这样,您可以创建一个全新的,极其有用/多功能的对象,例如Sudoku(’. The variables defined in the structure itself are created as part of the instance like properties. They can be read and written but are crucially part of the instance, like text to a textbox. In this way, you can create a totally new and extremely useful/versatile object such as the Sudoku) square .列出这些自定义结构的好处是可以访问单个项目并提取单个值.例如:(. The beauty of having a list of these custom structures is the ability to access individual items and extract individual values. For instance:)

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

了解它们的最好方法是通过阅读或与它们一起玩耍,直到掌握它们为止.我推荐后者,没有什么比经验更重要的了.(The best way to learn more about them is either by reading or playing around with them a bit, until you get the hang of it. I recommend the latter, nothing beats experience.)

清单的好处(Benefit of the List)

使用列表(整数)最有益的部分是删除项目时它自动进行自我调整的方式.当您取出物品时,例如(The most beneficial part about using list (of integer) is the way it automatically adjusts itself when an item is removed. When you take an item out, like a) listbox ,则下一项采用其索引,这意味着在使用时(, the next item takes on its index which means when using) GetRan ,这不是偶然事件,每个项目中总会有一个数字.(, it’s not a hit and miss affair, there’s always a number available in every item.)

使用代码(Using the Code)

为了易于使用,讨论的代码在称为的模块中编译.(For ease of use, the code discussed is compiled in a module called) SudoGen .易于访问,易于使用并且易于合并到无数项目中.(. Easy to access, easy to use and easy to incorporate into countless projects.) 生成数独,非常简单:(To generate a Sudoku, it’s as easy as:)

SudoGen.GenerateGrid

然后,数独生成后,很容易访问输出.这些将一直保留到创建新网格或(Then it’s simple to access the output once the Sudoku has generated. These remain until a new grid is created or the) SudoGen.Clear 函数被调用.(function is called.)

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

兴趣点(Points of Interest)

从模块中删除组件并在主类中使用它们可能会更有用,因为这将使您可以对代码执行不同的操作.例如,您可以跟踪生成器的进度以显示给用户.(Removing the components form the module and using them within your main class may be more useful as it will allow you to do different things with the code. For example, you could keep track of the progress of the generator to display to the user.) 该程序与该程序无关,但我相信某些细菌会利用回溯来找到通往食物来源的最直接路径,并探查各个方向,直到找到足够大的食物来源以供殖民地使用,然后将未使用/不成功的部分消灭.为了殖民地更大的利益.我觉得有点相似.如果自然界认为这是最有效的,那么就认为这是一个明智的举动.(Nothing really to do with this program, but I believe some Bacteria use backtracking to find the most direct path to a source of food, probing every direction until they find a large enough source to feed the colony, then the unused/unsuccessful parts die off for the greater good of the colony. A bit similar I think. If nature thinks it’s the most effective, then methinks it is a wise move to agree.)

历史(History)

• 发表时间:2008年1月26日,美国东部夏令时间下午7:04(Posted: January 26, 2008, 7:04 PM AEDST)

• 更新时间:AEDST,2008年1月26日,晚上8:50(Updated: January 26, 2008, 8:50 PM AEDST)

• 更新日期:2008年1月27日,美国东部标准时间上午9:00(Updated: January 27, 2008, 9:00 AM AEDST)

  • 将数独的创建速度从平均6-20秒增加到0.07秒(Increased Sudoku creation speed from an average of 6-20 seconds, all the way down to 0.07 seconds)

• 更新时间:2008年2月3日,美国东部标准时间上午11:20(Updated: February 3, 2008, 11:20 AM AEDST)

  • 添加了Keith B.的建议,该建议将发电机速度从0.07提高到0.0452(Added suggestions from Keith B. which increased the generator speed from 0.07 to 0.0452)

• 更新日期:2009年2月18日,美国东部标准时间上午10:59(Updated: February 18, 2009, 10:59AM AEDST)

  • 新增了Imperiatus和Spirch的建议,谢谢(Added suggestions from Imperiatus and Spirch, thank you guys)
  • 更新了源邮政编码和文章代码(Updated source zip and article code)
  • 现在以0.018的平均速度运行(Now runs at an average speed of 0.018)

许可

本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。