数独算法:避免回溯的策略（译文）

原文地址：https://www.codeproject.com/Articles/23247/Sudoku-Algorithm-Strategies-to-Avoid-Backtracking

原文作者：PeterMoon

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

前言

A Sudoku algorithm with 4 deterministic strategies to avoid backtracking

具有4种确定性策略的Sudoku算法,可避免回溯

• 下载可执行文件-8.25 KB(Download executable - 8.25 KB)
• 下载源代码(C#)-19.03 KB(Download source code (C#) - 19.03 KB)

介绍(Introduction)

首先,我必须承认我不是Sudoku的粉丝.但是,看到妻子每天花5到10分钟解决报纸上的日常难题后,我尝试了解她的策略.有几个朋友喜欢这个难题,但是他们花的时间更多,所以我妻子有东西!一周后,我与大家分享了她的建议来解决这个难题,但是我使用的语言是C#…(First of all, I must confess that I’m not a fan of Sudoku. However, after seeing my wife spend 5 to 10 minutes every day solving the daily puzzle in the newspaper, I try to understand her strategy. Several friends like this puzzle, but they spend much more time, so my wife has something! A week after, I share her advices to solve this puzzle with all of you, but in a language I understand… C#…)

什么是数独？(What is Sudoku?)

如上图所示,数独包含81个单元,分布在9x9矩阵中.该矩阵由9行和9列组成,每个都有9个单元格.此外,还有9组3x3矩阵(如上所示),在本文中称为"正方形".这个想法是在每个单元格中写一个1到9之间的数字,但是游戏有一些规则:(As shown in the image above, Sudoku consists in 81 cells, distributed in a 9x9 matrix. This matrix is composed of 9 rows and 9 columns, each with 9 cells. Additionally, there are 9 groups of 3x3-matrixes (as shown above), that we call “squares” in this article. The idea is to write a digit between 1 and 9 in each cell, but the game has some rules:)

• 您不能在同一行的两个或多个单元格中写入相同的数字.(You cannot write the same digit in two or more cells of the same row.)
• 您不能在同一列的两个或多个单元格中写入相同的数字.(You cannot write the same digit in two or more cells of the same column.)
• 您不能在同一"正方形"的两个或多个单元格中写入相同的数字(You cannot write the same digit in two or more cells of the same “square”)

数独解决细胞问题的策略(Sudoku Strategies to Solve a Cell)

该算法使用四种策略来确定Sudoku板中某个单元格的有效值.这些策略如下:(The algorithm uses four strategies to determine a valid value for a cell in the Sudoku board. The strategies are the following:)

• 搜索具有唯一解决方案的单元格.(Search for cells with a unique solution possible.)
• 在具有唯一单元格的行中搜索特定数字.(Search for rows with a unique cell for an specific digit.)
• 搜索具有唯一单元格的列以显示特定数字.(Search for columns with a unique cell for an specific digit.)
• 搜索具有特定数字的唯一单元格的"正方形".(Search for “squares” with a unique cell for an specific digit.)
• 从单元格的可用有效值中随机选择一个值.(Pick a value randomly from the available valid values for a cell.) 该程序将四个优先策略套用到一个循环中.实践证明,这4种策略足以用一种解决方案解决任何数独难题.换句话说,如果数独谜题只有一个解决方案,那么这4个策略就足以找到该解决方案.(This programs applies the 4 first strategies into a loop. This 4 strategies have proven to be sufficient to solve any Sudoku puzzle with one solution. In other words, if a Sudoku puzzle has only one solution, these 4 strategies are enough to find this solution.) 如果Sudoku拼图有多个解决方案,则需要最后一种策略:为单元格选择一个随机值.(If the Sudoku puzzle has more than one solution, the last strategy is needed: Pick a Random value for the cell.)

搜索具有唯一解决方案的单元格(Searching for Cells with a Unique Solution Possible)

此策略包括查找与其他单元格的当前值没有冲突的某个单元格的所有可能值的列表.这意味着根据谜题的规则,一个单元格只有一个可能的值.这是一个例子:(This strategy consists of finding the list of all the possible values for a cell that don’t have a conflict with the current values of the other cells. This means that a cell has only one possible value according to the rules of the puzzle. This is an example:) 灰色的单元格只能有一个有效的解决方案:7.如果选中,所有其他值都会与带有红色圆圈的单元格产生冲突.(The grayed cell can only have one valid solution: 7. If you check, all the other values create a conflict with the cells with the red circles.)

搜索具有特定数字的唯一单元格的行,列和"平方"(Searching for Rows, Columns and “Squares” with a Unique Cell for a Specific Digit)

每行必须具有介于1和9之间的所有数字.此策略包括查找可以放置每个数字的所有单元格.如果这些值之一只能放在特定行的一个单元格中,那么我们已经找到了该单元格的解决方案.这是一个例子:(Each row must have all the digits between 1 and 9. This strategy consists of finding all the cells where each digit can be placed. If one of these values can only be placed into one cell in a specific row, then we have found a solution for that cell. This is an example:) 标记的行只能在灰色单元格中包含值2.由于具有红色圆圈的单元格,所以该行中的所有其他单元格不能具有该值.该概念也可以应用于每列和"正方形"以查找其他解决方案.(The row marked can only host the value 2 in the grayed cell. All of the other cells in this row cannot have this value, because of the cells with the red circles. This concept can be applied as well for each column and “square” to find other solutions.)

申请详情(Details of the Application)

该应用程序在主用户界面中显示Sudoku面板,您可以在其中放置拼图的初始值.(The application shows in the main user interface a Sudoku board where you can place the initial values for the puzzle.)如果您没有为任何单元格写入任何初始值,程序将生成一个随机的Sudoku板.(If you don’t write any initial value for any cell, the program will generate a random Sudoku board.) 为了解决这个难题,应用程序按照前面所示的顺序应用了4种确定性策略.如果这些策略中的任何一个产生了解决方案,则第一个策略将再次运行,直到数独板解决.如果应用了这四种策略,并且没有为单元生成新的解决方案,并且数独板不完整,那么此数独有多个解决方案,因此我们必须使用随机策略.(To solve the puzzle, the application applies the 4 deterministic strategies, in the same order as shown before. If any of those strategies produces a solution, then the first strategy will be run again, until the Sudoku board is solved. If the 4 strategies are applied, and no new solution for a cell is generated, and the Sudoku board is not complete, then this Sudoku has more than one solution, so we must use the random strategy.) 首先,我们确定哪个单元格具有最小的可能有效值.我们这样做是为了避免为具有高可能解集的单元格选择随机值,因为这可能导致具有短有效解集的单元格最终没有任何值.这是避免回溯算法的策略.在为所选单元格选择一个随机值之后,我们返回以再次执行这4种基本策略.我们一直这样做,直到为董事会找到有效的解决方案为止.(First, we determinate which cell has the minimum of possible valid values. We do so, to avoid picking a random value to a cell with a high set of possible solutions, because this can cause cells with a short set of valid solutions to end up without any value. This is the strategy to avoid the need of a backtracking algorithm. After we pick a random value for the selected cell, we go back to execute the 4 basic strategies again. We do this until we have a valid solution for the board.)

不需要回溯吗？(No Need for Backtracking?)

如前所述,该应用程序不需要回溯算法,因为我们不仅仅依赖于单元的随机选择.当需要随机策略时,我们为"更不幸的单元格"选择一个随机值,即具有最短有效值集的单元格.(As mentioned before, this application does not need a Backtracking Algorithm, because we don’t depend only on random selections for the cells. And when the random strategy is needed, we pick a random value for the “more unfortunate cell”, this is, the cell with the shortest set of valid values.)

解决策略细节(Solving Strategy Details)

该应用程序显示了所使用的每种策略的详细信息,指定了求解的单元格以及所选的值.(The application shows a detail of each strategy used, specifying the solved cell, and the selected value.)

历史(History)

• 27(27)日(th)2008年1月:首次发布(January, 2008: First publication)

许可

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

C# 新闻 翻译