? ? ? ??“芬蘭數學家因卡拉，花費3個月時間設計出了世界上迄今難度最大的數獨游戲，而且它只有一個答案。因卡拉說只有思考能力最快、頭腦最聰明的人才能破解這個游戲。”這是英國《每日郵報》2012年6月30日的一篇報道。看完這個新聞就對數獨有點感興趣了，于是用python解一下玩玩，無意中卻戳穿了某個虛假新聞（下面有鏈接）。

? ? ? ? 上圖就是那個最難數獨。解數獨用的就是深度優先搜索，有幾個方面可以優化一下提高速度：

? ? ? ? 1.把每個空格的可能的點先列舉出來，因為深搜是把遍歷的值寫入sudoku矩陣再判斷，如果不列舉可能的值，那就只能用0-9遍歷，這樣效率會降低，如果空格較少的情況下，先把可能的點列舉出來會使速度翻倍；

? ? ? ? 2.每次把可能情況最少的點優先嘗試寫入值判斷，這個我在程序里沒有加，因為深搜的每個樹節點必須是固定的，這樣當退棧返回上一結點的時候才能正確返回，而我加了這個判斷最優節點功能的代碼中，返回的樹節點不是固定的，因為隨著數獨空格中值的填入，矩陣也發生著變化，每個點的優先級也在同時發生著變化，這樣邏輯就亂了，但我覺得還是可以加上的，這里也算一個小遺憾，希望感興趣的大牛加上這個功能，那速度又是一番提升。

? ? ? ? 好了，代碼如下：

import time t0=time.time() class point:def __init__(self,x,y):self.x=xself.y=yself.available=[]self.value=0def rowNum(p,sudoku):row=set(sudoku[p.y*9:(p.y+1)*9])row.remove(0)return row #set typedef colNum(p,sudoku):col=[]length=len(sudoku)for i in range(p.x,length,9):col.append(sudoku[i])col=set(col)col.remove(0)return col #set typedef blockNum(p,sudoku):block_x=p.x//3block_y=p.y//3block=[]start=block_y*3*9+block_x*3for i in range(start,start+3):block.append(sudoku[i])for i in range(start+9,start+9+3):block.append(sudoku[i])for i in range(start+9+9,start+9+9+3):block.append(sudoku[i])block=set(block)block.remove(0)return block #set typedef initPoint(sudoku):pointList=[]length=len(sudoku)for i in range(length):if sudoku[i]==0:p=point(i%9,i//9)for j in range(1,10):if j not in rowNum(p,sudoku) and j not in colNum(p,sudoku) and j not in blockNum(p,sudoku):p.available.append(j)pointList.append(p)return pointListdef tryInsert(p,sudoku):availNum=p.availablefor v in availNum:p.value=vif check(p,sudoku):sudoku[p.y*9+p.x]=p.valueif len(pointList)<=0:t1=time.time()useTime=t1-t0showSudoku(sudoku)print('\nuse Time: %f s'%(useTime))exit()p2=pointList.pop()tryInsert(p2,sudoku)sudoku[p2.y*9+p2.x]=0sudoku[p.y*9+p.x]=0p2.value=0pointList.append(p2)else:pass def check(p,sudoku):if p.value==0:print('not assign value to point p!!')return Falseif p.value not in rowNum(p,sudoku) and p.value not in colNum(p,sudoku) and p.value not in blockNum(p,sudoku):return Trueelse:return Falsedef showSudoku(sudoku):for j in range(9):for i in range(9):print('%d '%(sudoku[j*9+i]),end='')print('') if __name__=='__main__':sudoku=[8,0,0,0,0,0,0,0,0,0,0,3,6,0,0,0,0,0,0,7,0,0,9,0,2,0,0,0,5,0,0,0,7,0,0,0,0,0,0,0,4,5,7,0,0,0,0,0,1,0,0,0,3,0,0,0,1,0,0,0,0,6,8,0,0,8,5,0,0,0,1,0,0,9,0,0,0,0,4,0,0,]pointList=initPoint(sudoku)showSudoku(sudoku)print('\n')p=pointList.pop()tryInsert(p,sudoku)
? ? ? ? 我用time計時的起始時間是從第一行import time模塊之后就開始了，這樣測出的時間是最長的吧~哈~運行結果如下：

? ? ? ? 在百度上一搜“世界最難數獨”會有一條新聞說江蘇69歲農民3天破解“世界最難數獨”，但是進去看就知道，他把第四行第二個值“5”給改成“8”才揭出來的。。。這是有多坑啊。。。所以他其實沒有解出來，真正的解在上面~附一下他的“錯誤解法”圖吧：

轉載請注明： 轉自?http://blog.csdn.net/littlethunder/article/details/9749509

總結

以上是生活随笔為你收集整理的python解数独--世界最难数独2.3秒完成的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。