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

更新時間：2017年04月12日 08:45:11 作者：未曾見海

最近在帶孩子學(xué)習(xí)數(shù)獨，職業(yè)使然，就上網(wǎng)搜了下相關(guān)程序的解法，這里分享給大家，希望對大家學(xué)習(xí)python有所幫助

偶然發(fā)現(xiàn)linux系統(tǒng)附帶的一個數(shù)獨游戲，打開玩了幾把。無奈是個數(shù)獨菜鳥，以前沒玩過，根本就走不出幾步就一團(tuán)漿糊了。

于是就打算借助計算機(jī)的強(qiáng)大運算力來暴力解數(shù)獨，還是很有樂趣的。

下面就記錄一下我寫解數(shù)獨程序的一些思路和心得。

一.數(shù)獨游戲的基本解決方法

編程籠統(tǒng)的來說,就是個方法論。不論什么程序，都必須將問題的解決過程分解成計算機(jī)可以實現(xiàn)的若干個簡單方法。俗話說，大道至簡。對于只能明白0和1的計算機(jī)來說，就更需要細(xì)分步驟，一步一步的解決問題了。

首先來思考一下解數(shù)獨的基本概念。

數(shù)獨橫九豎九共八十一個格子，同時又分為9個九宮格。規(guī)則很簡單——需要每一個格中的數(shù)字，都保證與其所在橫排和豎排以及九宮格內(nèi)無相同數(shù)字。

所以我們的大概思路就是，從第一個空格開始試著填數(shù)，從 1 開始填，如果 1 不滿足橫排豎排九宮格無重復(fù)的話，就再填入 2 ，以此類推，直到填入一個暫時滿足規(guī)則的數(shù)，中斷此格，移動到下一個空格重復(fù)這個過程。

如果到達(dá)某個空格發(fā)現(xiàn)已經(jīng)無數(shù)可選了，說明前面某一格填錯了，那就返回上一格，從上一格的中斷處繼續(xù)往 9 嘗試，直到這樣回朔到填錯的那一格。

這樣的話，我們就可以整理出重要的步驟了：

•尋找到下一個空格
•輪流填入格中數(shù)字 1 到 9
•遞歸判斷填入數(shù)是否符合規(guī)則

二.程序

首先測試數(shù)獨使用的是芬蘭數(shù)學(xué)家因卡拉花費3個月時間設(shè)計出的世界上迄今難度最大的數(shù)獨。如下

將空格用 0 表示，同時將數(shù)獨表示成嵌套的列表，這樣每格的行數(shù)和列數(shù)就正好是列表中每個對應(yīng)數(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 '\ncost 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()

值得注意的是使用的遞歸判斷能夠很巧妙的在走錯分支時回朔到上一層。具體實現(xiàn)是通過 for 循環(huán)來從 1 到 9 不斷填入數(shù)字同時達(dá)到記錄中斷點的作用。通過下一層的返回值來確定是否回朔。

程序輸出如下：

[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

可以看到程序雖然運算次數(shù)比較多，但是速度還是很快的。

您可能感興趣的文章: