????????江蘇老人花了3天破解了史上最難數(shù)獨，我們用Python試試需要多少時間？

????????

1 識別程序中的對象

?????????在實際編程中，可以將game對象保存在csv文件中，region對象的職責用board完成，所以只需要設計兩個對象：cell和board。

2 識別對象行為

?

?????????我們可以看到三個對象行為，均可劃分為board的職責

3 算法設計

? ? ? ? 可采用遞歸+回溯法解決該問題，從左向右，從上到下，依次用1-9試探每一個非預設格子，如果某數(shù)填入該格子不存在沖突，則填入，試探下一個格子（遞歸）,否則清空該格子，回溯上一個格子繼續(xù)試探。當試探推進完全部格子，則問題得解。

4 代碼

import csv class cell:def __init__(self,number):self.number=numberif number==0:self.filled=Falseelse:self.filled = True class board:gridList=[]def readSudoku(self):with open("s1.csv", "r") as csvfile:read = csv.reader(csvfile)for line in read:gLine = []for item in line:gLine.append(cell(int(item)))self.gridList.append(gLine)def printSudoku(self):for line in self.gridList:for aCell in line:print(aCell.number, ' ',end='')print()def lineConflict(self,line,number):numberList=[]for j in range(0,9):numberList.append(self.gridList[line][j].number)return number in numberListdef columnConflict(self,column,number):numberList=[]for i in range(0,9):numberList.append(self.gridList[i][column].number)return number in numberListdef rangeConflict(self,line,column,number):startI=3*(line//3) #確定range的行起點startIstartJ=3*(column//3) #確定range的列起點startJnumberList = []for i in range(startI,startI+3):for j in range(startJ,startJ+3):numberList.append(self.gridList[i][j].number)return number in numberListdef conflict(self,line,column,number):return self.lineConflict(line,number) or \self.columnConflict(column,number) \or self.rangeConflict(line,column,number)def solve(self,i,j):if j > 8: #試探下一行j = 0i = i + 1if i>8 : #得解self.printSudoku()else:if not self.gridList[i][j].filled: #試探非預設格子for k in range(1,10):if not self.conflict(i,j,k):self.gridList[i][j].number=k #填入kself.solve(i,j+1) #試探下一格 （遞歸）self.gridList[i][j].number=0 #回溯上一格else:self.solve(i, j+1) #預設格子直接跳過 aGrid=board() aGrid.readSudoku() aGrid.printSudoku() print("答案：") aGrid.solve(0,0)

5 數(shù)據(jù)（s1.csv）

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

6?結論

我們的程序需要花幾秒就可以得到答案，與報道的答案稍有不同

?

總結

以上是生活随笔為你收集整理的Python练手项目：求解史上最难数独问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。