python解数独,完成数独的算法 python

　　对于用Python解数独，我们可以用回溯算法实现一个简单的版本。在此基础上，本文改进了数独问题求解算法的性能。需要什么可以参考。

　　00-1010 1.导言2。上一篇评论3。减少不必要的迭代3.1候选字典的生成3.2候选列表的生成3.3函数调用4。摘要

1. 引言

　　首先，我们来回顾一下之前的回溯算法，如下图：

　　在上一篇文章中，我们引入了回溯算法来解决数独问题，通过迭代每个子单元格所有可能的值来暴力解决问题，直到数独九宫格中引入的新值与属于同一行、列或块的子单元格中确定的值不冲突。虽然这种方案可以有效解决这个问题，但肯定不是最佳方案，因为它没有合理利用数独九宫格中提供的额外先验信息。现在，让我们一步一步优化上面的算法。

2. 前文回顾

　　优化上述算法的第一个想法来自于我们的算法按顺序迭代所有数字1到9，直到它找到一个与同一行、列或块中已经包含相同值的另一个单元格不冲突的值。但是，数独九宫格中的某些特定值已经为我们提供了某些特定子单元格中哪些数字不能相加的信息。

　　#使用回溯解决数独

　　定义求解(板):

　　blank=findEmpty(纸板)

　　如果不是空白：

　　返回True

　　else:

　　行，列=空白

　　对于(1，10):范围内的I

　　if isValid(板，I，空白):

　　board[row][col]=i

　　如果解决(板):

　　返回True

　　board[row][col]=0

　　返回False

　　我们的优化思路是先扫描我们的数独九宫格，把每个子格所有可能的合法候选值保存在内存中，然后逐个迭代，而不是迭代所有的数字。参考下图，展示了数独九宫格的2个子单元格的候选值集合。正如我们的游戏规则所暗示的，每个行、列和块不能包含相同的数字，因此所有在属于给定子单元的相同行、列和块单元中确定的数字都被排除。

　　既然有了优化的想法，那么就可以用代码来实现上面的想法。

3. 减少非比要的迭代次数

　　接下来，我们需要一个数据结构(这里我们选择一个字典)来存储每个子单元格的候选列表。该函数通过遍历整个九方形格子空心子单元格并调用allowedValues()函数来返回子单元格的候选列表。

　　示例代码如下：3360

　　#把合法的储存在字典里

　　#每个单元格的值

　　def cacheValidValues(板):

　　cache=dict()

　　对于范围(9):中的I

　　对于范围(9):内的j

　　if板[i][j]==0:

　　cache[(i，j)]=allowedValues(board，I，j)

　　返回缓存

3.1 生成候选值字典

　　上一节中的allowValues()函数与我们在上一篇文章中看到的isValid()函数具有相似的逻辑，但是在本例中，它的返回值是

　　每个子单元格所提取到的合法数字的列表。

　　样例代码如下:

def allowedValues(board,row,col):
　　 numbersList = list()
　　 for number in range(1,10):
　　 found = False
　　 # Check if all row elements include this number
　　 for j in range(9):
　　 if board[row][j] == number:
　　 found = True
　　 break
　　 # Check if all column elements include this number
　　 if found == True:
　　 continue
　　 else:
　　 for i in range(9):
　　 if board[i][col] == number:
　　 found = True
　　 break
　　 # Check if the number is already included in the block
　　 if found == True:
　　 continue
　　 else:
　　 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] == number:
　　 found = True
　　 break
　　 if found == False:
　　 numbersList.append(number)
　　 return numbersList

3.3 函数调用

　　有了我们的单元格候选值缓存字典，下面我们准备测试该方案是否会显着提高我们的程序性能。

　　为此我们还需要将 solve() 函数替换为一个新的函数solveWithCache()，该函数只迭代每个子单元格cell的合法值列表，而不是所有数字 1–9。

　　代码如下:

def solveWithCache(board, cache):
　　 blank = findEmpty(board)
　　 if not blank:
　　 return True
　　 else:
　　 row, col = blank
　　 for value in cache[(row,col)]:
　　 if isValid(board, value, blank):
　　 board[row][col] = value
　　 if solveWithCache(board, cache):
　　 return True
　　 board[row][col] = 0
　　 return False

　　在实现所有改动后测试我们的代码为我们提供了所需的结果，与我们的第一个版本相比，跑同样50组测试用例执行时间明显缩短：

The execution time of above program is : 15.41820478439331 s

4. 总结

　　本文为数独游戏求解的第二篇,主要基于第一篇的回溯思想来思考如何利用数独九宫格的先验思想来减少回溯的迭代次数,进而提升算法提升效率,并给出了完整代码实现.

　　到此这篇关于使用Python进行数独求解详解(二)的文章就介绍到这了,更多相关Python数独求解内容请搜索盛行IT软件开发工作室以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT软件开发工作室！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。