言

數(shù)獨（及其前身）已經(jīng)出現(xiàn)了一百多年。當它第一次出現(xiàn)時，人們實際上只能咬著筆抓著頭發(fā)來解決數(shù)獨題目。但現(xiàn)在我們有了強大的電腦！（現(xiàn)在的人就能在手機和電腦上做數(shù)獨題啦！）

在這篇文章中，你會學(xué)到如何搖身一變，成為一名數(shù)獨大師，在幾秒鐘時間內(nèi)就能解出一般人要花幾小時才能解出的難題。當然，更重要的是，你會一步步的學(xué)習(xí)如何使用機器學(xué)習(xí)（Machine Learning）輕松解決每個數(shù)獨。設(shè)想一下，如果有計算機來做數(shù)獨，誰還需要思考呢，當然，多做數(shù)獨還是真的可以健腦的。（我沒有開掛做數(shù)獨啊，不要抓我）

Peter Norvig最先使用Python開發(fā)了一個優(yōu)雅的程序，通過約束網(wǎng)格傳播和搜索以此來解出數(shù)獨。Norvig的解決方案被認為是目前十分經(jīng)典的一個解決數(shù)獨的方案，當人們通過編程來解數(shù)獨時經(jīng)常被引用。在回顧數(shù)獨和一些策略之后，本文將逐步分解Norvig的代碼，以便你能真正了解它的工作方式。

什么是數(shù)獨？

數(shù)獨是源自于18世紀瑞士的一種數(shù)學(xué)游戲。是一種傳統(tǒng)的運用紙、筆進行演算的邏輯游戲。人們需要根據(jù)9×9的盤面上的已知數(shù)字，一一推理出所有剩余空格的數(shù)字，并滿足每一行、每一列、每一個九宮格（3*3）內(nèi)的數(shù)字均含1-9，不重復(fù)

如圖，突出顯示在藍色正方形中的數(shù)字不能在與同列同行和宮相對應(yīng)的任何黃色正方形中重復(fù)

如何解數(shù)獨？

其實一般做數(shù)獨題的時候，只需要不斷做兩件事就OK了。要做的第一件事是就是排除行，列和宮中的已知數(shù)字。您要做的第二件事就是尋找一個可能填寫的候選數(shù)。

在下面給出的示例中，每個正方形中的可能填寫的數(shù)字以較小的字體標注。通過排除出現(xiàn)在同一列，行或?qū)m中的已經(jīng)重復(fù)的數(shù)字來確定剩下可能的數(shù)字。大多數(shù)人僅僅只會一次確定一個宮的可能數(shù)量，而不是直接確定整個網(wǎng)格中所有能填寫的數(shù)字（暗數(shù)、候選數(shù)）。

進行排除操作后，你可以尋找僅剩余一種情況的格子。在下面的示例中，兩個黃色突出顯示的正方形必須包含1和8，因為其他所有的可能性已被排除，它們填在別的格子中會出現(xiàn)重復(fù)。

現(xiàn)在已知以黃色突出顯示的兩個格子，這又排除了其他格子的更多可能性。現(xiàn)在我們可以知道以藍色突出顯示的格子必須填7。

如果你繼續(xù)不斷的按照此法進行排除和確定，最終可能會達到能夠完全確定某個3*3的格子或行或列的情況。

在下面的示例中，我們可以確定以藍色突出顯示的格子的解必須為6，因為數(shù)字6不可能出現(xiàn)在黃色宮中的其他任何的格子中。

有時，我們在求解的時候可能會遇到這種情況，似乎每個未解決的3*3的格子中有多個可能的值。這意味著我們可以選擇多種路徑，但至于哪條路才能最終得到結(jié)果就不知道了。

在這個選擇上，我們必須嘗試每個選項。選擇一條路并繼續(xù)求解，直到按這條路走下去最后只能得到“此路不通”的答案。然后，將不得不回溯到分歧點并嘗試其它的路。

但是我們可以使用二叉搜索樹在計算機上輕松完成此類檢索。當有兩個不同的數(shù)字都可以作為一個3*3的格子的答案時，我們可以嘗試引入兩種不同的可能性。二叉搜索樹將使算法沿選擇的一個分支下降，然后嘗試不同的選擇。

現(xiàn)在，我們將了解用上述方法相似的思路來編寫的Python代碼，以此用來處理數(shù)獨問題。

Peter Norvig的解數(shù)獨代碼

Peter Norvig在他的解決數(shù)獨難題的文章中解釋了做數(shù)獨題的方法與他所使用的代碼。

www.norvig.com/sudoku.html

有些人可能理解他的解釋有些困難，尤其是初學(xué)者。本文將分解這些內(nèi)容，以便讓你更輕松地了解Peter Norvig的代碼是如何工作的。

在本文中，Peter Norvig的代碼已經(jīng)更新為Python3，以方便的在目前的環(huán)境下運行

首先，我們將介紹基本的設(shè)置和表示法。Norvig描述了他在代碼中所使用的基本符號：

數(shù)獨拼圖是一個由81個方格組成網(wǎng)格；廣大愛好者把列1-9、行a-i記為行列標記，把9個方格（列、行或?qū)m）的集合稱為一個單位，把共享一個單位的方格稱為對等方

這是數(shù)獨中每個格子的名稱：

Norvig將數(shù)字，行和列定義為字符串：

digits='123456789'
rows='ABCDEFGHI'
cols=digits

你可能會注意到將cols其設(shè)置為與digits相等。盡管它們具有相同的值，但它們表示不同的事物。該digits變量表示走在數(shù)獨上解決這一難題的數(shù)字。而cols變量代表網(wǎng)格的列名。

整個數(shù)獨盤也被定義為字符串，但是這些字符串是通過以下函數(shù)創(chuàng)建的：

def cross(A, B):
 "a中元素與b中元素的叉積。"
 return [a+b for a in A for b in B]
squares=cross(rows, cols)

cross函數(shù)（[a+b for a in A for b in B]）的返回部分只是編寫這個代碼的一種優(yōu)秀解決方案：

squares=[]
for a in rows:
 for b in cols:
 squares.append(a+b)

運行此函數(shù)后，變量等于所有小方格名稱的列表。

['A1', 'A2', 'A3', 'A4', 'A5', 'A6', 'A7', 'A8', 'A9', 'B1', 'B2', 'B3', 'B4', 'B5', 'B6', 'B7', 'B8', 'B9', 'C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9', 'D1', 'D2', 'D3', 'D4', 'D5', 'D6', 'D7', 'D8', 'D9', 'E1', 'E2', 'E3', 'E4', 'E5', 'E6', 'E7', 'E8', 'E9', 'F1', 'F2', 'F3', 'F4', 'F5', 'F6', 'F7', 'F8', 'F9', 'G1', 'G2', 'G3', 'G4', 'G5', 'G6', 'G7', 'G8', 'G9', 'H1', 'H2', 'H3', 'H4', 'H5', 'H6', 'H7', 'H8', 'H9', 'I1', 'I2', 'I3', 'I4', 'I5', 'I6', 'I7', 'I8', 'I9']

而網(wǎng)格中的每個小格子都有3個單位和20個對等方。小格子的單位是顯示在其中的行，列和九宮格。小格子的對等方是單位中的所有其他小格子。例如，以下是小格子C2中的單位和對等方：

使用cross函數(shù)創(chuàng)建每個小格子的所有單位：

unitlist=([cross(rows, c) for c in cols] +
 [cross(r, cols) for r in rows] +
 [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')])

在Python中，字典是鍵值對的集合。使用以下代碼行創(chuàng)建字典，字典使用小格子的名稱作為鍵，并使用三個單位或20個對等體作為值。

units=dict((s, [u for u in unitlist if s in u]) 
 for s in squares)
peers=dict((s, set(sum(units[s],[]))-set([s]))
 for s in squares)

現(xiàn)在，可以使用來訪問“ C2”的所有3個單位，units['C2']并將得到以下結(jié)果：

接下來，我們需要完整的數(shù)獨網(wǎng)格的兩種表示形式。名為grid的文本將是數(shù)獨的初始狀態(tài)。

還需要網(wǎng)格的另一種表示形式來描述數(shù)獨解題的當前狀態(tài)。它將跟蹤每個格子的所有剩余可能值并命名為values。

與units和peers類似，values將是一個以小格子為鍵的字典。每個鍵的值將是一串數(shù)字，該串數(shù)字是該小格子內(nèi)的所有可能數(shù)字。如果數(shù)字是在拼圖中給出的或已被找出，則vaules中將只有一位數(shù)字。例如，如果存在一個網(wǎng)格，其中A1為6而A2為空，則values的值可能是這樣{'A1': '6', 'A2': '123456789', ...}。

解析網(wǎng)格和網(wǎng)格值函數(shù)

該parse_grid函數(shù)（下面的代碼）可將網(wǎng)格轉(zhuǎn)換為可能值的字典。grid是給定的數(shù)獨題目。grid_values函數(shù)用來提取數(shù)字，0和“.”的重要值。在values字典中，正方形是鍵，而網(wǎng)格中的給定數(shù)字是值。

對于具有給定值的每個格，assign函數(shù)用于將值分配給方框并從對等方排除該值。assign函數(shù)將在下文介紹。如果發(fā)生任何錯誤，該函數(shù)將返回False。

這是parse_grid與grid_values函數(shù)的代碼。

def parse_grid(grid):
 """將網(wǎng)格轉(zhuǎn)換為可能值的dict，{square:digits}，如果檢測到錯誤，則返回false"""
 ## 首先，每個小格子可以是任意數(shù)字；然后從網(wǎng)格中賦值。
 values=dict((s, digits) for s in squares)
 for s,d in grid_values(grid).items():
 if d in digits and not assign(values, s, d):
 return False ## (如果我們不能把d賦給格子s，則失敗。)
 return values
def grid_values(grid):
 "將網(wǎng)格轉(zhuǎn)換為{square:char}的dict，并用'0'或'.'表示清空。"
 chars=[c for c in grid if c in digits or c in '0.']
 assert len(chars)==81
 return dict(zip(squares, chars))

約束傳播（Constraint propagation）

每個方格的初始值將是特定數(shù)字（1-9）或為空值。我們可以將約束應(yīng)用于每個小格子并排除不可能的值。

Norvig使用以下兩種策略來幫助確定平方的正確值（與上述策略相對應(yīng)）：

（1）如果一個方格只有一個可能的值，則從該正方形的對等方中排除該值。

（2）如果一個單位只有一個可能的位置放一個值，則將值放在那里。

第一種策略的示例是：如果我們知道A1的值為5，則可以從其所有20個對等方中刪除5個。

第二種策略的示例是：如果可以確定A1到A8都不包含9作為可能的值，那么我們可以確定A9的值為9，因為9必須出現(xiàn)在單位中的某個位置。

每次更新網(wǎng)格時，都會導(dǎo)致其所有對等方的可能更新。此過程將連續(xù)不斷的進行，稱為約束傳播。

分配功能

該assign(values, s, d)函數(shù)在parse_grid函數(shù)內(nèi)部被調(diào)用。它返回更新的值。它接受三個參數(shù)：values，s和d。

請記住，values是一個字典，它將每個格子與該格子的所有可能的數(shù)字值相關(guān)聯(lián)。s是我們要為其分配值的格子，d是需要分配給該格子的值。D才是我們首先要解決的給定的難題。

它調(diào)用函數(shù)eliminate(values, s, d)以排除S中除D之外的所有值。

如果存在矛盾，例如兩個正方形被分配了相同的數(shù)字，則排除函數(shù)將返回False。

def assign(values, s, d):
 """從值[s]中排除所有其他值（d除外）并傳播。如果存在矛盾，則本函數(shù)將返回False。"""
 other_values=values[s].replace(d, '')
 if all(eliminate(values, s, d2) for d2 in other_values):
 return values
 else:
 return False

消除功能

我們看到assign函數(shù)調(diào)用了eliminate函數(shù)。消除函數(shù)的調(diào)用如下：eliminate(values, s, d2) for d2 in other_values)

eliminate函數(shù)將排除使用上述兩種策略無法解決的值。第一種策略是，當僅存在一個潛在值s時，該值將從s的對等方中刪除。第二種策略是，當值只能存在一個位置時，該值d將從所有對等方中刪除。

這是它的全部功能：

def eliminate(values, s, d):
 """從值[s]中刪除d；當值或位置<=2時傳播。如果存在矛盾，則本函數(shù)將返回False。"""
 if d not in values[s]:
 return values ## 已被排除
 values[s]=values[s].replace(d,'')
 ## （1）如果方格s減去一個值d2，則從對等點中消除d2。
 if len(values[s])==0:
 return False ## 矛盾：去掉最后一個值
 elif len(values[s])==1:
 d2=values[s]
 if not all(eliminate(values, s2, d2) for s2 in peers[s]):
 return False
 ##（2）如果一個單位u的值d減少到只剩一個地方，那么就不動它。
 for u in units[s]:
 dplaces=[s for s in u if d in values[s]]
 if len(dplaces)==0:
 return False ## 矛盾：沒有這個值的地方
 elif len(dplaces)==1:
 #d只能在一個單元中的其中一個位置；將它分配到那里
 if not assign(values, dplaces[0], d):
 return False
 return values

顯示功能

本display函數(shù)將在調(diào)用后顯示結(jié)果parse_grid。

def display(values):
 "將這些值顯示為二維網(wǎng)格。"
 width=1+max(len(values[s]) for s in squares)
 line='+'.join(['-'*(width*3)]*3)
 for r in rows:
 print(''.join(values[r+c].center(width)+('|' if c in '36' else '') for c in cols))
 if r in 'CF': 
 print(line)
 print()

這是一個示例，它在解析一個網(wǎng)格之后調(diào)用顯示函數(shù)后，顯示的網(wǎng)格依然是個候選數(shù)的集合

您會注意到，許多格具有多個候選數(shù)，而有些則完全解決了。上面的網(wǎng)格是上面兩種策略死記硬背應(yīng)用的結(jié)果。但是正如你所看到的，僅憑這些策略還不足以完全解決數(shù)獨。

搜索（Search）

解決數(shù)獨問題的??方法有很多，但有些方法效率更高。Norvig建議使用一種特定類型的搜索算法。

搜索算法可以做這些事情。首先，它可以確保還沒有找到解決方案。然后，它選擇一個未填充的正方形，并考慮所有可能的值。最后，它一次一次嘗試為格子分配每個值，然后從結(jié)果位置再次進行搜索。

可變順序用于選擇要開始搜索的格子。這是Norvig的描述方式：

我們將使用一種稱為最小剩余值的通用啟發(fā)式方法，這意味著我們將選擇具有最小可能值數(shù)量的格子（或其中之一）。為什么？考慮上面的grid。假設(shè)我們首先選擇了B3。它有7種可能性（1256789），因此我們期望以6/7的概率猜測錯誤。如果取而代之，我們選擇G2，它只有2種可能性（89），那么我們期望錯的概率只有1/2。因此，我們選擇可能性最小，直接得到正確答案的期望也就越大。

這些數(shù)值按自然數(shù)順序排列。

這是本search函數(shù)以及solve解析初始網(wǎng)格并調(diào)用的函數(shù)search。

def solve(grid): return search(parse_grid(grid))
def search(values):
 "使用深度優(yōu)先搜索和傳播，嘗試所有可能的值。"
 if values is False:
 return False ## 失敗了
 if all(len(values[s])==1 for s in squares): 
 return values ## 解出來辣!
 ## 選擇可能性最小的未填充正方形
 n,s=min((len(values[s]), s) for s in squares if len(values[s]) > 1)
 return some(search(assign(values.copy(), s, d)) 
 for d in values[s])

根據(jù)數(shù)獨的規(guī)則，當每個格子只有一個值時， 問 題 就解決了。該search函數(shù)將遞歸調(diào)用，直到解決難題為止。它通過values復(fù)制以避免復(fù)雜。

some是用于檢查嘗試是否成功解決難題的函數(shù)。

def some(seq):
 "返回seq的某個元素，該元素為true。"
 for e in seq:
 if e: return e
 return False

完整代碼（在Python3.x下測試通過）

這些代碼組合起來將會讓你變成數(shù)獨大師，以下給出完整代碼。

def cross(A, B):
 "a中元素與b中元素的叉積。"
 return [a+b for a in A for b in B]
digits='123456789'
rows='ABCDEFGHI'
cols=digits
squares=cross(rows, cols)
unitlist=([cross(rows, c) for c in cols] +
 [cross(r, cols) for r in rows] +
 [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')])
units=dict((s, [u for u in unitlist if s in u])
 for s in squares)
peers=dict((s, set(sum(units[s],[]))-set([s]))
 for s in squares)
def parse_grid(grid):
 """將網(wǎng)格轉(zhuǎn)換為可能值的dict，{square:digits}，如果檢測到錯誤，則返回false"""
 ## 首先，每個小格子可以是任意數(shù)字；然后從網(wǎng)格中賦值。
 values=dict((s, digits) for s in squares)
 for s,d in grid_values(grid).items():
 if d in digits and not assign(values, s, d):
 return False ## (如果我們不能把d賦給格子s，則失敗。)
 return values
def grid_values(grid):
 "將網(wǎng)格轉(zhuǎn)換為{square:char}的dict，并用'0'或'.'表示清空。"
 chars=[c for c in grid if c in digits or c in '0.']
 assert len(chars)==81
 return dict(zip(squares, chars))
def assign(values, s, d):
 """從值[s]中排除所有其他值（d除外）并傳播。如果存在矛盾，則本函數(shù)將返回False。"""
 other_values=values[s].replace(d, '')
 if all(eliminate(values, s, d2) for d2 in other_values):
 return values
 else:
 return False
def eliminate(values, s, d):
 """從值[s]中刪除d；當值或位置<=2時傳播。如果存在矛盾，則本函數(shù)將返回False。"""
 if d not in values[s]:
 return values ## ## 已被排除
 values[s]=values[s].replace(d,'')
## （1）如果方格s減去一個值d2，則從對等點中消除d2。
 if len(values[s])==0:
 return False ## 矛盾：去掉最后一個值
 elif len(values[s])==1:
 d2=values[s]
 if not all(eliminate(values, s2, d2) for s2 in peers[s]):
 return False
 ##（2）如果一個單位u的值d減少到只剩一個地方，那么就不動它。
 for u in units[s]:
 dplaces=[s for s in u if d in values[s]]
 if len(dplaces)==0:
 return False ## 矛盾：沒有這個值的地方
 elif len(dplaces)==1:
 #d只能在一個單元中的其中一個位置；將它分配到那里
 if not assign(values, dplaces[0], d):
 return False
 return values
def solve(grid): return search(parse_grid(grid))
def search(values):
 "使用深度優(yōu)先搜索和傳播，嘗試所有可能的值。"
 if values is False:
 return False ## 已False
 if all(len(values[s])==1 for s in squares):
 return values ## 解出來拉!
 ## 以最少的可能性選擇未填充的正方形
 n,s=min((len(values[s]), s) for s in squares if len(values[s]) > 1)
 return some(search(assign(values.copy(), s, d))
 for d in values[s])
def display(values):
 "Display these values as a 2-D grid."
 width=1+max(len(values[s]) for s in squares)
 line='+'.join(['-'*(width*3)]*3)
 for r in rows:
 print(''.join(values[r+c].center(width)+('|' if c in '36' else '') for c in cols))
 if r in 'CF':
 print(line)
 print()
def some(seq):
 "返回seq的某個元素，該元素為true。"
 for e in seq:
 if e: return e
 return False

調(diào)試

測試用Grid數(shù)獨題,同時它也是一個最小數(shù)獨（供讀者自己測試python時調(diào)試用）：

grid='4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'

苦逼作者碼字不易，各位看官老爺們給個關(guān)注吧！