怎么使用Python进行数独求解(python,开发技术)

1. 引言

数独这个名字的由来来自日语短语suuji wa dokushin ni kagiru，意思是“数字必须保持单一”。数独游戏的流行也源于其规则的简单性：数独游戏要求在 9 x 9 空间的网格上进行数字填写。在行和列中有 9 个“正方形”的格子block(由 3 x 3 个子单元格cell组成)。每一行、每一列、每一个block都需要填写数字 1-9，行、列、block内不得重复任何数字。

好的，知道了上述数独的规则，那么我们就来直接进入主体吧。 ：）

2.描述数独九宫格

这一步主要为使用一组数字来初始化我们的九宫格。我们使用setBoard() 函数将输入转换为适合我们后续操作的数据类型。我们使用以下约定：

• 空的单元格cell初始化为默认值0。

• 维持数独谜题数字值的数据类型是一个 9x9 大小的二维列表。

这里我们的输入是一个多行字符串，我们将其处理成二维列表的形式。样例代码如下：

#Initializea2-Dlistwithinitialvaluesdescribedbytheproblem.#ReturnsboarddefsetBoard():board=list()sudokuBoard='''200080300 060070084 030500209 000105408 000000000 402706000 301007040 720040060 004010003 '''rows=sudokuBoard.split('\n')forrowinrows:column=list()forcharacterinrow:digit=int(character)column.append(digit)board.append(column)returnboard

上述代码运行后，如果展示在拼图游戏中，他的样子大概如下：

3.寻找下一个空子单元格

函数findEmpty() 函数的操作更加简单：对初始化后的九宫格作为参数传递，然后该遍历该九宫格中每一个子单元格cell，直到找到返回的第一个空的子单元格。如果没有找到空的子单元格，这表明我们的问题已解决，因此它返回None。

样例代码如下：

#FindnextemptyspaceinSudokuboardandreturndimensionsdeffindEmpty(board):forrowinrange(9):forcolinrange(9):ifboard[row][col]==0:returnrow,colreturnNone

4. 子单元格中设置值的合法性

函数isValid()的操作是确认设定的数字是否是九宫格子单元格的有效选项。为了使设置的值满足数独九宫格的要求，该值的设置需满足以下条件：

• 同一行的任何子单元格cell都不应包含该数字

• 同一列的任何子单元格cell都不应包含该数字

• 该子单元格cell所在的block不应该包含该数字

如果我们设定的值满足以上所有条件，该函数返回True，否则返回False。代码如下：

#CheckwhetheraspecificnumbercanbeusedforspecificdimensionsdefisValid(board,num,pos):row,col=pos#Checkifallrowelementsincludethisnumberforjinrange(9):ifboard[row][j]==num:returnFalse#Checkifallcolumnelementsincludethisnumberforiinrange(9):ifboard[i][col]==num:returnFalse#CheckifthenumberisalreadyincludedintheblockrowBlockStart=3*(row//3)colBlockStart=3*(col//3)rowBlockEnd=rowBlockStart+3colBlockEnd=colBlockStart+3foriinrange(rowBlockStart,rowBlockEnd):forjinrange(colBlockStart,colBlockEnd):ifboard[i][j]==num:returnFalsereturnTrue

以下是通过isValid() 函数中描述的条件后成功插入新值的动态示例：

同时，若我们引入一个与九宫格数独上已经存在的值冲突的数值，那么此时该值将不会被插入。图例如下：

5. 实现回溯算法

下一个函数是我们整个解决方案的核心思想，这里引入了回溯思想，该算法的实现步骤如下：

• 搜索下一个空的子单元格cell。如果没有找到，那么我们已经解决了这个难题；如果没有，则转到第 2 步。

• 通过迭代数字1-9 来猜测正确的数字，并参考已经确定的数字来检查它是否是一个合法的数字。

• 如果找到一个有效的数字，此时递归调用solve() 函数并猜测下一个空的子单元格cell。

• 如果数字1-9均无效，则将将子单元格cell的值重置为 0，并继续迭代以查找下一个有效数字。

#SolveSudokuusingbacktrackingdefsolve(board):blank=findEmpty(board)ifnotblank:returnTrueelse:row,col=blankforiinrange(1,10):ifisValid(board,i,blank):board[row][col]=iifsolve(board):returnTrueboard[row][col]=0returnFalse

由于递归理解起来不是那么直观，不妨让我们尝试使用动态来将整个过程形象化：

正如我们在上面的示例中看到的那样，该算法用有效数字填充空子单元格cell，直到出现死胡同；然后它回溯，直到重新迭代该过程。

6. 性能表现

上述我们的程序需要使用回溯算法来遍历每个单元格的许多潜在值。这当然不是最优的解法，可以预想到我们的解决方法的性能会很慢。

我们使用上述代码，来解决欧拉计划的第96题中的50道数独题目，运行时间为：

Theexecutiontimeofaboveprogramis:23.56185507774353s