完成数独的算法 python,python解数独
本文主要介绍如何构建一个Python脚本来解决数独谜题。本文的重点是介绍用于构建数独求解器的回溯算法。感兴趣的朋友可以了解一下。
00-1010 1.导言2。描述一下数独九宫格3。找到下一个空单元格4。在子单元格5中设置值的合法性。实现回溯算法6。业绩7。总结。
目录
本文是介绍流行的数独游戏系列文章的第一篇。更具体地说，我们如何构建一个脚本来解决数独难题？本文重点介绍用于构建数独解算器的回溯算法。
数独这个名字来自日语短语suuji wa dokushin ni kagiru，意思是“数字必须保持单一”。数独游戏的流行也源于其规则的简单：数独游戏要求在9 x 9空间的网格上填写数字。在行和列中有9个“正方形”的网格块(由3 x 3子单元单元组成)。每行、每列、每块都需要填写数字1-9，行、列、块中不能有数字重复。
好了，知道了以上数独的规则，我们直接进入正文。)
1. 引言
这一步主要是用一组数字来初始化我们的九宫格。我们使用setBoard()函数将输入转换成适合后续操作的数据类型。我们使用以下约定：
的空单元单元被初始化为默认值0。维护数独谜题数值的数据类型是9x9大小的二维列表。这里我们的输入是一个多行字符串，我们把它处理成一个二维列表的形式。示例代码如下：
#用问题描述的初始值初始化一个二维列表。
#退货板
def setBoard():
board=list()
数独板=
200080300
060070084
030500209
000105408
000000000
402706000
301007040
720040060
004010003
rows=sudokuBoard.split(\n )
对于行：中的行
column=list()
对于行：中的字符
digit=int(字符)
列.追加(数字)
board.append(列)
滑板
上面的代码运行后，如果以拼图的形式显示，看起来会是这样的：
2.描述数独九宫格
findEmpty()函数操作起来更简单：将初始化后的九宫格作为参数传递，然后遍历九宫格中的每个子单元格单元格，直到找到第一个空的子单元格。如果没有找到空的子单元格，则表明我们的问题已经解决，所以它返回None。
示例代码如下：
#在数独棋盘中寻找下一个空格并返回尺寸
def findEmpty(板):
对于范围(9):中的行
对于范围(9):中的列
if板[行][列]==0 :
返回行，列
不返回
3.寻找下一个空子单元格
isValid()函数的作用是确认设置的数字是否是九宫格的有效选项。为了使设定值满足数独九宫格的要求，该值的设定需要满足以下条件：
同一行中的任何子单元格都不应包含此数字，同一列中的任何子单元格都不应包含此数字。该子单元所在的块不应包含该数字。如果我们设置的值满足以上所有条件，这个函数就返回True，否则就返回。
False。代码如下：
# Check whether a specific number can be used for specific dimensionsdef isValid(board, num, pos):
row, col = pos
# Check if all row elements include this number
for j in range(9):
if board[row][j] == num:
return False
# Check if all column elements include this number
for i in range(9):
if board[i][col] == num:
return False
# Check if the number is already included in the block
rowBlockStart = 3* (row // 3)
colBlockStart = 3* (col // 3)
rowBlockEnd = rowBlockStart + 3
colBlockEnd = colBlockStart + 3
for i in range(rowBlockStart, rowBlockEnd):
for j in range(colBlockStart, colBlockEnd):
if board[i][j] == num:
return False
return True
以下是通过isValid() 函数中描述的条件后成功插入新值的动态示例：
同时，若我们引入一个与九宫格数独上已经存在的值冲突的数值，那么此时该值将不会被插入。图例如下：
5. 实现回溯算法
下一个函数是我们整个解决方案的核心思想，这里引入了回溯思想，该算法的实现步骤如下：
- 搜索下一个空的子单元格cell。如果没有找到，那么我们已经解决了这个难题；如果没有，则转到第 2 步。
- 通过迭代数字1-9 来猜测正确的数字，并参考已经确定的数字来检查它是否是一个合法的数字。
- 如果找到一个有效的数字，此时递归调用solve() 函数并猜测下一个空的子单元格cell。
- 如果数字1-9均无效，则将将子单元格cell的值重置为 0，并继续迭代以查找下一个有效数字。
# Solve Sudoku using backtrackingdef solve(board):
blank = findEmpty(board)
if not blank:
return True
else:
row, col = blank
for i in range(1,10):
if isValid(board, i, blank):
board[row][col] = i
if solve(board):
return True
board[row][col] = 0
return False
由于递归理解起来不是那么直观，不妨让我们尝试使用动态来将整个过程形象化：
正如我们在上面的示例中看到的那样，该算法用有效数字填充空子单元格cell，直到出现死胡同；然后它回溯，直到重新迭代该过程。
6. 性能表现
上述我们的程序需要使用回溯算法来遍历每个单元格的许多潜在值。这当然不是最优的解法，可以预想到我们的解决方法的性能会很慢。
我们使用上述代码，来解决欧拉计划的第96题中的50道数独题目，运行时间为：
The execution time of above program is : 23.56185507774353 s
好吧，确实有点慢。我们后面再来开篇讲解数独算法的优化。
7. 总结
本文讲解了数独游戏的相关规则，以及如何在Python中利用回溯思想来一步一步解决数独问题，并给出了完整的实现。
以上就是使用Python进行数独求解详解(一)的详细内容，更多关于Python数独求解的资料请关注盛行IT软件开发工作室其它相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。