你會玩數(shù)獨么?

周六去公園晃了一圈，來了頓有儀式感的野餐下午茶。周日宅在家里，實在無聊的很，睡個懶覺，半天就打發(fā)過去了。看看沖天在哪里啊的電視劇，轉(zhuǎn)眼到了晚上。鑒于仙女實在無聊的很，于是我主動挑事，要和仙女一起做數(shù)獨。
“哎呀，做數(shù)獨一點都不鍛煉腦子的，實在是無聊的很”，仙女名言。作為一個純粹的工科生，我是一點都不信的，數(shù)獨還是很考驗綜合能力的，眼睛要掃描的快，排除要迅速，驗證可能性要準(zhǔn)確。遇到不確定的地方還要做假設(shè)。
前幾場的戰(zhàn)績，很慘淡，每次都是以我惜敗告終。（其實不是惜敗，是大敗，被仙女甩幾條街了）。今天我又不服，想靠運氣戰(zhàn)勝仙女。話不多說，上題。

一場沒有硝煙的戰(zhàn)爭一觸即發(fā)。刷刷刷一頓操作，前幾個填數(shù)還算順利，然后中間就卡住了。過了幾分鐘，仙女說她做完了，而我才完成了三分之一。不服輸?shù)奈也辉敢獬姓J(rèn)這個事實，于是我裝模作樣繼續(xù)做下去了，希望我能很快填完，這樣不至于輸?shù)奶珣K。恰逢飯點，一邊吃飯，一邊想這個數(shù)獨題，思緒斷斷續(xù)續(xù)。吃完飯一下子來靈感了，很快做完?？磥磉€是吃飽了干活利索。
距離困覺時間還早，我不服氣向仙女發(fā)出第二次挑戰(zhàn)。這次是在電腦上做題目，我一下子就來勁了，腦子放光。因為電腦上excel，多建幾個sheet，每個框多填幾個可選數(shù)字還是非常方便的。于是網(wǎng)上找了個題目，新一輪battle開始。

時間一下子穿越到40分鐘之后，除了極少數(shù)確定的，我一點進展都沒有，已經(jīng)新建了好幾個excel里面的sheet，還沒遇到一個碰壁回頭嘗試失敗的，也沒有哪種情況順利做到最后。而此時，仙女在她眾多的猜測里，終于找到了一個答案。頓時感覺智商被碾壓。接下來放一下我和仙女的思路對比。

先把能確定的數(shù)字體填好，再把所有空里可能的數(shù)字填出來，然后挑可能性較少的格子，開始嘗試。

一頓分叉，從total總的數(shù)據(jù)，到total11111,total11112,還在繼續(xù)分叉。仙女的思路差不多，不過她的執(zhí)行效率更高，對excel的熟練度也相當(dāng)高。仙女解題過程如下：先列出總的數(shù)據(jù)，這步驟和我一樣。

接著就各種分叉，是的，你沒有看錯。這么優(yōu)雅簡潔清晰的分類標(biāo)記出自仙女之手，我一碼農(nóng)自愧不如。

數(shù)獨做不過仙女，那我肯定不能自己吃這個悶虧。沒關(guān)系，我還可以寫代碼！利用python來解數(shù)獨。下面進入具體介紹。
第一個要考慮的問題是，怎樣表示數(shù)獨。這里使用一個嵌套的list?？盏牡胤教?，其他地方把題目中的數(shù)據(jù)填進來。

board = [    [0,0,0,8,0,0,0,0,0],    [0,3,0,0,9,2,0,0,1],    [0,9,0,0,0,0,0,0,0],    [7,0,0,0,0,0,8,0,0],    [0,0,5,7,0,0,9,0,0],    [2,0,0,0,0,0,0,0,0],    [0,0,3,5,2,0,1,0,0],    [0,5,0,0,0,0,4,0,2],????[0,0,6,0,0,4,0,0,0],????]

參考了網(wǎng)上一些寫好的數(shù)獨程序，發(fā)現(xiàn)基本沒有做原始數(shù)據(jù)檢查的，看來很信得過出題的人。鑒于題目錄入的時候，有輸錯的可能性，所以在正式解數(shù)獨之前，先檢查一下板子的數(shù)據(jù)是否正常。板子的檢查，包括每一行，每一列，還有每個九宮格。這里的檢查方法，使用Counter把每一行列九宮格中的數(shù)據(jù)檢查一下數(shù)量?？罩臄?shù)據(jù)用0表示，所以0會有多個，其他數(shù)據(jù)應(yīng)該只有1個或者是沒有。

def check_repeat(self,data):    #檢查輸入的9個數(shù)是否有重復(fù)    c = dict(Counter(data))    # print(c)    for key, v in c.items():        if key == 0:            pass        else:            if v != 1:                # print('有重復(fù)數(shù)據(jù)')                return False    return True
def check_row(self):    #檢查所有行是否有重復(fù)數(shù)據(jù)    for row in range(0,9):        result = self.check_repeat(self.b[row])        if result == False:            return result    return True
def check_column(self):    #檢查所有列是否有重復(fù)數(shù)據(jù)    list = np.array(self.b)    for column in range(0, 9):        result = self.check_repeat(list.T[column])        if result == False:            return result    return True
def check_square(self):    #檢查所有九宮格是否有重復(fù)數(shù)據(jù)    square = []    for i in range(0,9):        row, col = int(i / 3) * 3, int(i % 3) * 3        square.append(self.b[row][col:col+3]+self.b[row+1][col:col+3]+self.b[row+2][col:col+3])        # print(square[i])        result = self.check_repeat(square[i])        if result == False:            return result    return True
def check_board(self):    #檢查輸入的數(shù)獨是否有輸入錯誤    result = self.check_row() and self.check_column() and self.check_square()    return result

在這頓沒啥用的操作之后，可以正式開始解題了。我相信大多數(shù)小伙伴都會想到窮舉法，沒錯這是個萬能的方法，我就一個一個去試唄。但是這樣做很蠢，效率也不高。

可以使用遞歸算法加上剪枝。（在算法面前，我個弱雞不值一提) 遞歸的思想很重要，如果不理解遞歸的思想，是很難把代碼寫好的。在這里我們以青蛙跳為例子：一只青蛙一次可以跳1個臺階或者2個臺階，現(xiàn)有一個10級高的臺階，青蛙跳上去一共有多少種方案？這是個很典型的遞歸，思考方法可以逆推。最后青蛙是跳完了這10個臺階，那么最后一步要么是跳了1步，要么是跳了2步。所以總的方法就等于最后一步跳1與跳2的方案之和，這樣一直一直往前推，就能推到初始沒有跳的狀態(tài)。

遞歸的核心，有明確的初始狀態(tài)值，每一步計算的表達式清晰，每一步計算前后有關(guān)聯(lián)性。以斐波拉契為例，f(1)=1,f(2)=1,f(3)=2... ??可以看到f(3) = f(2)+f(1)。本題求解數(shù)獨問題，最后一個步驟肯定是填寫最后一個空格上的數(shù)據(jù)，如果填對了，那么數(shù)獨計算結(jié)束。如果找不到合適的值，那么就往上回歸，上一個步驟是錯的，得換個值來計算。理論不多說，直接上代碼。

def cal_count(self,x,y):    count = 9    value = [1,2,3,4,5,6,7,8,9]    row = self.b[x]   #一行數(shù)據(jù)    column = list(np.array(self.b).T[y])   #一列數(shù)據(jù)    x, y = int(x / 3) * 3, int(y / 3) * 3    square = self.b[x][y:y + 3] + self.b[x + 1][y:y + 3] + self.b[x + 2][y:y + 3]    data = list(set(row+column+square))    data.remove(0)    count = count-len(data)    for i in range(len(data)):        value.remove(data[i])    return count,value
def cal_count_all(self):    count = []    value = []    # index = 0    for i in range(0, 9):        for j in range(0, 9):    #遍歷整個數(shù)獨，每個位置檢查橫向縱向九宮格            # index = index+1            if self.b[i][j] != 0:                value.append(self.b[i][j])                count.append(10)    #題目中填好的數(shù)字            else:                tmp_count,temp_value = self.cal_count(i,j)                # 增加一個打斷，如果檢測到一個格子里只有1種或者2種解法，后面的就不用計算了                # if (tmp_count == 1):                #     print(tmp_count, index, temp_value)                #     return tmp_count, index, temp_value                count.append(tmp_count)                value.append(temp_value)    #遍歷完之后，每個格子都有3種或者以上的填法    # print(count)    min = np.min(count)    index = int(np.argmin(count))    # print(min,index)    return min,index,value[index]
def try_it(self,min,index,value):#主循環(huán)    self.t += 1    if min == 10:        print('數(shù)獨破解完成，一種可能的結(jié)果如下:')        for i in self.b:            print(i)        # print(self.b)        return True  # 返回True    else:        x, y = int(index / 9), int(index % 9)        for i in value:    #從篩選過后的值填入            self.b[x][y]=i    #將符合條件的填入0格            next_min,next_index,next_value= self.cal_count_all() #找出下一個可填數(shù)字最少的格子            end=self.try_it(next_min,next_index,next_value)            if not end:   #在遞歸過程中存在不符合條件的，即 使try_it函數(shù)返回False的項                self.b[x][y] = 0    #回朔到上一層繼續(xù)            #不添加以下兩句的話，數(shù)組得出一個方案之后不會結(jié)束，會繼續(xù)測試value里面的其他值，可以用于求解多解法的數(shù)獨，加上之后，只會打印一種方案            else:                return True        return False    #屏幕上填滿數(shù)字，最后一次try還是失敗了，返回false

?根據(jù)人做數(shù)獨的思路，先找到每個格子上可以填的數(shù)字的個數(shù)和具體內(nèi)容是什么。然后挑選可填數(shù)字?jǐn)?shù)量最小的開始嘗試。見cal_count和cal_count_all（如果數(shù)字是1，說明只有1種選擇，那么這個數(shù)字填寫起來就很快。如果有2種數(shù)字可以填，那么就需要填好一個繼續(xù)往下面試試。出題自帶的原始數(shù)據(jù)，使用10來表示）try_it函數(shù)需要結(jié)合剛才說的遞歸的思想好好理解一下。最后運行程序，biu~? 780ms，出來了15種數(shù)獨解決方案，可見這一題是多解。如果只要做出一種方案，運行時間為80ms。運行速度，還算湊合，使用c，c++來解題，速度可以再高一檔次。眾所周知，c的運行效率是python的10倍。（我瞎說的），但是編程時間卻是python的10倍不止。

算法工程師的作用是將平時遇到的問題，使用算法找到更好的計算解決方案，然后借由程序員之手寫代碼實現(xiàn)，算法是很核心重要的一部分。
雖然沒使用上高級的算法，好多判斷方法不是最高效，有重復(fù)檢查計算的部分，沒有及時砍枝再繼續(xù)計算。但總的來說，ms級就可以把問題解決，相比于兩個憨憨寫個40分鐘還不一定寫的出來答案來說，已經(jīng)很不錯了。完整代碼點擊閱讀原文，進入git。好了，以后做數(shù)獨，仙女再也不是我的對手，接下來該PK什么新技能呢？

---

相關(guān)文章：

• 玩游戲你還在自己動手玩？
  
• VIP視頻只能試看6分鐘？
  
• 快遞單號導(dǎo)出再也不費事
  

• 最美的不是下雨天
  

• 今天你網(wǎng)易云了么？
  

• 今天你下廚房了么？