python實現(xiàn)解數(shù)獨程序的代碼示例

 #coding=utf-8
 import datetime
 class solution(object):
 def __init__(self,board):
 self.b = board
 self.t = 0
 
 def check(self,x,y,value):#檢查每行每列及每宮是否有相同項
 for row_item in self.b[x]:
 if row_item == value:
 return False
 for row_all in self.b:
 if row_all[y] == value:
 return False
 row,col=x/3*3,y/3*3
 row3col3=self.b[row][col:col+3]+self.b[row+1][col:col+3]+self.b[row+2][col:col+3]
 for row3col3_item in row3col3:
 if row3col3_item == value:
 return False
 return True
 
 def get_next(self,x,y):#得到下一個未填項
 for next_soulu in range(y+1,9):
 if self.b[x][next_soulu] == 0:
 return x,next_soulu
 for row_n in range(x+1,9):
 for col_n in range(0,9):
 if self.b[row_n][col_n] == 0:
 return row_n,col_n
 return -1,-1 #若無下一個未填項，返回-1
 
 def try_it(self,x,y):#主循環(huán)
 if self.b[x][y] == 0:
 for i in range(1,10):#從1到9嘗試
 self.t+=1
 if self.check(x,y,i):#符合 行列宮均無條件 的
 self.b[x][y]=i #將符合條件的填入0格
 next_x,next_y=self.get_next(x,y)#得到下一個0格
 if next_x == -1: #如果無下一個0格
 return True #返回True
 else: #如果有下一個0格，遞歸判斷下一個0格直到填滿數(shù)獨
 end=self.try_it(next_x,next_y)
 if not end: #在遞歸過程中存在不符合條件的，即 使try_it函數(shù)返回None的項
 self.b[x][y] = 0 #回朔到上一層繼續(xù)
 else:
 return True
 
 def start(self):
 begin = datetime.datetime.now()
 if self.b[0][0] == 0:
 self.try_it(0,0)
 else:
 x,y=self.get_next(0,0)
 self.try_it(x,y)
 for i in self.b:
 print i
 end = datetime.datetime.now()
 print '
cost time:', end - begin
 print 'times:',self.t
 return
 
 
 s=solution([[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,8,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]])
 73 s.start()

[8, 1, 2, 7, 5, 3, 6, 4, 9]
[9, 4, 3, 6, 8, 2, 1, 7, 5]
[6, 7, 5, 4, 9, 1, 2, 8, 3]
[1, 5, 4, 2, 3, 7, 8, 9, 6]
[3, 6, 9, 8, 4, 5, 7, 2, 1]
[2, 8, 7, 1, 6, 9, 5, 3, 4]
[5, 2, 1, 9, 7, 4, 3, 6, 8]
[4, 3, 8, 5, 2, 6, 9, 1, 7]
[7, 9, 6, 3, 1, 8, 4, 5, 2]

cost time: 0:00:00.060687
times: 45360