使用Python进行数独求解详解(二)
1. 引言
本文是数独游戏问题求解的第二篇,在前文中我们使用回溯算法实现了最简单版本的数独游戏求解方案。本文主要在前文解决方案的基础上,来思考如何通过改进来提升数独问题求解算法的性能。
闲话少说,我们直接开始吧。 :)
2. 前文回顾
我们首先来回顾下前文的回溯算法,如下图示:
在前文中,我们引入了回溯算法来对数独问题求解,通过迭代每个子单元格cell的所有可能取值来暴力解决该问题,直到引入数独九宫格中的新值与属于同一行,列或block块的子单元格中确定值之间没有冲突为止。这种解决方案虽然可以有效解决该问题,但是它绝对不是最佳的解决方案,因为它没有合理利用数独九宫格中提供的附加先验信息。下面,我们来一步步对前文算法进行优化吧。。。
3. 减少非比要的迭代次数
优化上述算法的第一个想法来自于这样的观察,我们的算法按顺序迭代所有数字1到9,直到它找到一个与已经包含相同值的同一行,列或block块中的另一个单元格不冲突的值。但是,数独九宫格中一些确定值会已经为我们提供了一些信息,说明哪些数字不可能添加到某个子单元格cell中。
# Solve Sudoku using backtracking def 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
我们优化的思路是首先扫描我们的数独九宫格,将每个子单元格的所有可能的合法候选值保存在内存中然后再逐个迭代它们,而不是迭代所有数字。参考下图,演示了数独九宫格的 2 个子单元格的候选值的集合。正如我们的游戏规则所暗示的那样,每行,每列和每个block块不能包含相同的数字,因此在属于给定子单元格的同一行,列和所属block块的单元格中已经确定的所有数字都被排除在外。
既然有了优化思路,那么我们接下来就可以来用代码实现上述想法啦.
3.1 生成候选值字典
接着我们需要一个数据结构(这里我们选用字典)来保存每个子单元格的候选值列表,该函数通过遍历整个九宫格中空的子单元格并调用我们的allowedValues()函数来返回子单元格的候选值列表.
样例代码如下:
# Store in a dictionary the legitimate # values for each individual cell def cacheValidValues(board): cache = dict() for i in range(9): for j in range(9): if board[i][j] == 0: cache[(i,j)] = allowedValues(board,i,j) return cache
3.2 生成候选值列表
在上小节中的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数独求解内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
原文出处:https://blog.csdn.net/sgzqc/article/details/123015338
相关文章
- 这篇文章主要介绍了python-opencv-画外接矩形框的实例代码,代码简单易懂,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-04
Python astype(np.float)函数使用方法解析
这篇文章主要介绍了Python astype(np.float)函数使用方法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-06-08- 2022虎年新年即将来临,小编为大家带来了一个利用Python编写的虎年烟花特效,堪称全网最绚烂,文中的示例代码简洁易懂,感兴趣的同学可以动手试一试...2022-02-14
- 在本篇文章里小编给大家分享的是一篇关于python中numpy.empty()函数实例讲解内容,对此有兴趣的朋友们可以学习下。...2021-02-06
python-for x in range的用法(注意要点、细节)
这篇文章主要介绍了python-for x in range的用法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-10- 这篇文章主要介绍了Python 图片转数组,二进制互转操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-09
- 这篇文章主要介绍了Python中的imread()函数用法说明,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-16
- 这篇文章主要介绍了python如何实现b站直播自动发送弹幕,帮助大家更好的理解和学习使用python,感兴趣的朋友可以了解下...2021-02-20
python Matplotlib基础--如何添加文本和标注
这篇文章主要介绍了python Matplotlib基础--如何添加文本和标注,帮助大家更好的利用Matplotlib绘制图表,感兴趣的朋友可以了解下...2021-01-26- 这篇文章主要介绍了解决python 使用openpyxl读写大文件的坑,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-13
- 今天小编就为大家分享一篇python 计算方位角实例(根据两点的坐标计算),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-27
- 这篇文章主要为大家详细介绍了python实现双色球随机选号,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-05-02
- 在本篇文章里小编给大家整理的是一篇关于python中使用np.delete()的实例方法,对此有兴趣的朋友们可以学习参考下。...2021-02-01
- 这篇文章主要介绍了使用Python的pencolor函数实现渐变色功能,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-09
- 这篇文章主要介绍了python自动化办公操作PPT的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-05
Python getsizeof()和getsize()区分详解
这篇文章主要介绍了Python getsizeof()和getsize()区分详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-20- 这篇文章主要介绍了解决python 两个时间戳相减出现结果错误的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-12
- 这篇文章主要为大家详细介绍了python实现学生通讯录管理系统,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-25
- 这篇文章主要介绍了PyTorch一小时掌握之迁移学习篇,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-08
- 这篇文章主要介绍了Python绘制的爱心树与表白代码,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-06