使用Python進行數(shù)獨求解詳解(二)
1. 引言
本文是數(shù)獨游戲問題求解的第二篇，在前文中我們使用回溯算法實現(xiàn)了最簡單版本的數(shù)獨游戲求解方案。本文主要在前文解決方案的基礎上，來思考如何通過改進來提升數(shù)獨問題求解算法的性能。
閑話少說，我們直接開始吧。 ：）
2. 前文回顧
我們首先來回顧下前文的回溯算法，如下圖示：
在前文中，我們引入了回溯算法來對數(shù)獨問題求解，通過迭代每個子單元格cell的所有可能取值來暴力解決該問題，直到引入數(shù)獨九宮格中的新值與屬于同一行，列或block塊的子單元格中確定值之間沒有沖突為止。這種解決方案雖然可以有效解決該問題，但是它絕對不是最佳的解決方案，因為它沒有合理利用數(shù)獨九宮格中提供的附加先驗信息。下面，我們來一步步對前文算法進行優(yōu)化吧。。。
3. 減少非比要的迭代次數(shù)
優(yōu)化上述算法的第一個想法來自于這樣的觀察，我們的算法按順序迭代所有數(shù)字1到9，直到它找到一個與已經(jīng)包含相同值的同一行，列或block塊中的另一個單元格不沖突的值。但是，數(shù)獨九宮格中一些確定值會已經(jīng)為我們提供了一些信息，說明哪些數(shù)字不可能添加到某個子單元格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
我們優(yōu)化的思路是首先掃描我們的數(shù)獨九宮格，將每個子單元格的所有可能的合法候選值保存在內(nèi)存中然后再逐個迭代它們，而不是迭代所有數(shù)字。參考下圖,演示了數(shù)獨九宮格的 2 個子單元格的候選值的集合。正如我們的游戲規(guī)則所暗示的那樣，每行，每列和每個block塊不能包含相同的數(shù)字，因此在屬于給定子單元格的同一行，列和所屬block塊的單元格中已經(jīng)確定的所有數(shù)字都被排除在外。
既然有了優(yōu)化思路,那么我們接下來就可以來用代碼實現(xiàn)上述想法啦.
3.1 生成候選值字典
接著我們需要一個數(shù)據(jù)結構(這里我們選用字典)來保存每個子單元格的候選值列表,該函數(shù)通過遍歷整個九宮格中空的子單元格并調(diào)用我們的allowedValues()函數(shù)來返回子單元格的候選值列表.
樣例代碼如下:
# 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 生成候選值列表
在上小節(jié)中的allowValues() 函數(shù)與我們在前篇文中看到的isValid() 函數(shù)具有類似的邏輯，但在本例中，它返回值為每個子單元格所提取到的合法數(shù)字的列表。
樣例代碼如下:
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 函數(shù)調(diào)用
有了我們的單元格候選值緩存字典，下面我們準備測試該方案是否會顯著提高我們的程序性能。
為此我們還需要將 solve() 函數(shù)替換為一個新的函數(shù)solveWithCache()，該函數(shù)只迭代每個子單元格cell的合法值列表，而不是所有數(shù)字 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
在實現(xiàn)所有改動后測試我們的代碼為我們提供了所需的結果，與我們的第一個版本相比，跑同樣50組測試用例執(zhí)行時間明顯縮短：
The execution time of above program is : 15.41820478439331 s
4. 總結
本文為數(shù)獨游戲求解的第二篇,主要基于第一篇的回溯思想來思考如何利用數(shù)獨九宮格的先驗思想來減少回溯的迭代次數(shù),進而提升算法提升效率,并給出了完整代碼實現(xiàn).
到此這篇關于使用Python進行數(shù)獨求解詳解(二)的文章就介紹到這了,更多相關Python數(shù)獨求解內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了Pygame做一期吃豆子游戲的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-03-03
Flask 是一個流行的 Python Web 框架,它提供了多種方法來添加路由,本文詳細的介紹了Flask添加路由的三種方法,感興趣的可以了解一下2023-11-11
這篇文章主要介紹了Python3 pandas.concat的用法說明，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-03-03
python中的property及屬性與特性之間的優(yōu)先權
這篇文章主要介紹了python中的property及屬性與特性之間的優(yōu)先權，文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-07-07
這篇文章主要介紹了簡單介紹Python中的round()方法,是Python入門的基礎知識,需要的朋友可以參考下2015-05-05
字符串是?字符的序列?。字符串基本上就是一組單詞。我?guī)缀蹩梢员ＷC你在每個Python程序中都要用到字符串。本文為大家總結了15個常用的方法，希望對大家有所幫助2022-12-12
下面小編就為大家分享一篇Python和Java進行DES加密和解密的實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-01-01
Python如何根據(jù)關鍵字逐行提取文本內(nèi)容問題
這篇文章主要介紹了Python如何根據(jù)關鍵字逐行提取文本內(nèi)容問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
這篇文章主要給大家介紹了關于pytest中文文檔之編寫斷言的相關資料，文中通過示例代碼介紹的非常詳細，對大家學習或者使用pytest具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧2019-09-09
python實現(xiàn)指定字符串補全空格、前面填充0的方法
這篇文章主要介紹了python實現(xiàn)指定字符串補全空格、前面填充0的方法 ,非常不錯，具有一定的參考借鑒價值，需要的朋友可以參考下2018-11-11