????????江苏老人花了3天破解了史上最难数独，我们用Python试试需要多少时间？
????????
 |  |
1 识别程序中的对象
?????????在实际编程中，可以将game对象保存在csv文件中，region对象的职责用board完成，所以只需要设计两个对象：cell和board。
2 识别对象行为
?
?????????我们可以看到三个对象行为，均可划分为board的职责
3 算法设计
? ? ? ? 可采用递归+回溯法解决该问题，从左向右，从上到下，依次用1-9试探每一个非预设格子，如果某数填入该格子不存在冲突，则填入，试探下一个格子（递归）,否则清空该格子，回溯上一个格子继续试探。当试探推进完全部格子，则问题得解。
4 代码
import csv
class cell:
def __init__(self,number):
self.number=number
if number==0:
self.filled=False
else:
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 numberList
def columnConflict(self,column,number):
numberList=[]
for i in range(0,9):
numberList.append(self.gridList[i][column].number)
return number in numberList
def rangeConflict(self,line,column,number):
startI=3*(line//3) #确定range的行起点startI
startJ=3*(column//3) #确定range的列起点startJ
numberList = []
for i in range(startI,startI+3):
for j in range(startJ,startJ+3):
numberList.append(self.gridList[i][j].number)
return number in numberList
def 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 = 0
i = i + 1
if 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 #填入k
self.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 数据（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?结论
我们的程序需要花几秒就可以得到答案，与报道的答案稍有不同
?