摘要：而此處針對進(jìn)一步的搜索，有兩個(gè)問題需要考慮如何選取搜索起點(diǎn)方格確定哪種搜索策略深度優(yōu)先搜索，廣度優(yōu)先搜索關(guān)于第一個(gè)問題，無論選擇哪個(gè)方格起始搜索，對于能否解決問題來說并不存在差異。

Github倉庫地址

學(xué)習(xí)是為了尋找解決問題的答案，若脫離了問題只為知曉而進(jìn)行的打call，那么隨時(shí)間流逝所沉淀下來的，估計(jì)就只有“重在參與”的虛幻存在感了，自學(xué)的人就更應(yīng)善于發(fā)現(xiàn)可供解決的問題。為了入門AI，定個(gè)小目標(biāo)，解決數(shù)獨(dú)問題。

一個(gè)9*9的方格中，部分方格已預(yù)先填入數(shù)字，目的是按照如下規(guī)則將空白方格填上1-9中的一個(gè)：

每個(gè)方格中填且僅填一個(gè)數(shù)字，數(shù)字取值范圍1-9

以每行九個(gè)方格為單元來看，1-9每個(gè)數(shù)字都要出現(xiàn)，且僅出現(xiàn)一次

以每列九個(gè)方格為單元來看，1-9每個(gè)數(shù)字都要出現(xiàn)，且僅出現(xiàn)一次

以3*3九個(gè)方格為單元來看，1-9每個(gè)數(shù)字都要出現(xiàn)，且僅出現(xiàn)一次

描述問題是解決問題的第一步（將問題轉(zhuǎn)化為程序所能理解的數(shù)據(jù)模型，才能做進(jìn)一步有效地思考）

從左到右從上到下，以一個(gè)字符串的方式記下所有方格中的內(nèi)容，有數(shù)字記數(shù)字，空白記作點(diǎn)（.），如：..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..

以字典的方式記錄，將每行標(biāo)記為ABCDEFGHI，每列標(biāo)記為123456789，字典的key值為標(biāo)記的單元格描述，如：A1,G4等；字典的value值為方格中的記錄：有數(shù)字記數(shù)字，空白記作點(diǎn)（.）

{
  "A1": "."
  "A2": ".",
  "A3": "3",
  "A4": ".",
  "A5": "2",
  ...
  "I9": "."
}

字符串方式，記錄簡潔占用空間小，但處理起來比較麻煩；字典方式，方便查找處理，但記錄空間較大。

所以，我們以字符串方式記錄存儲，以字典方式進(jìn)行運(yùn)算求解。那么在運(yùn)算求解前需要對記錄方式的轉(zhuǎn)換。

rows = "ABCDEFGHI"
cols = "123456789"

def cross(a, b):
    return [s+t for s in a for t in b]

boxes = cross(rows, cols)

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

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

def grid_values(grid):
    return dict(zip(boxes, grid))

zip() 將可迭代的對象作為參數(shù)，把對象中對應(yīng)的元素打包成一個(gè)個(gè)元組，然后返回由這些元組組成的列表

首先明確一個(gè)概念：

規(guī)則單元：一個(gè)方格所屬的水平行、垂直列以及3*3方陣的所有方格

規(guī)則同胞：一個(gè)方格的規(guī)則單元中除了自己的其他方格

如果沒有任何限制，每個(gè)方格可填入的數(shù)字可以是123456789中的任何一個(gè)，而根據(jù)數(shù)獨(dú)游戲規(guī)則，預(yù)先填入數(shù)字的方格會限制，該方格的規(guī)則單元中，其他待填數(shù)方格的數(shù)字取值范圍。所以顯而易見的解決策略，便是根據(jù)限制規(guī)則，縮小取值范圍。

開始進(jìn)行過濾淘汰之前，我們需要的初始數(shù)獨(dú)方格字典中，代表空方格的（.）用可取值的數(shù)字范圍替換，初始范圍為123456789

def grid_values(grid):
    valueLst = []
    digits = "123456789"
    for item in grid:
        if item == ".":
            valueLst.append(digits)
        elif item in digits:
            valueLst.append(item)
    return dict(zip(boxes, valueLst))

如此獲得的初始數(shù)獨(dú)方格字典為：

{
    "A1": "123456789",
    "A2": "123456789",
    "A3": "3",
    "A4": "123456789"
    "A5": "2",
    ...
    "I9": "123456789"
}

過濾淘汰策略：找到已確定的數(shù)獨(dú)方格，再依次遍歷這些方格的規(guī)則同胞方格，從待確定方格的取值范圍中，把已確定的數(shù)字去掉，以縮小取值范圍。

def eliminate(values):
    solvedBoxes = [box for box in values.keys() if len(values[box]) == 1]
    for box in solvedBoxes:
        value = values[box]
        for peer in peers[box]:
            values[peer] = values[peer].replace(value, "")
    return values

過濾淘汰策略，是在規(guī)則單元上進(jìn)行取值范圍縮小的。這只覆蓋了數(shù)獨(dú)游戲規(guī)則的一部分，而數(shù)獨(dú)規(guī)則還包括：
每個(gè)最小規(guī)則單元中九個(gè)方格中的數(shù)字123456789僅出現(xiàn)一次。特別說明一下，最小規(guī)則單元：
單行的九個(gè)方格，單列的九個(gè)方格，或3*3的九個(gè)方格，也可以說一個(gè)規(guī)則單元包含了三個(gè)最小規(guī)則單元。

根據(jù)最小規(guī)則單元，進(jìn)一步縮小規(guī)則同胞中待填數(shù)的取值范圍，便引出了第二條規(guī)則：唯一可選策略

如果最小規(guī)則單元中，只有一個(gè)方格出現(xiàn)了某個(gè)數(shù)字，那么這個(gè)方格就該填這個(gè)數(shù)字

def only_choice(values):
    for unit in unitlist:
        for digit in "123456789":
            places = [box for box in unit if digit in values[box]]
            if len(places) == 1:
                values[places[0]] = digit
    return values

交替使用過濾淘汰策略和唯一可選策略便可將數(shù)獨(dú)問題中，所有待填數(shù)方格的取值范圍縮減至最小，但由于這兩種策略循環(huán)使用的終止條件，是不再有新確定的填數(shù)方格出現(xiàn)，所以這并不充分能解決所有數(shù)獨(dú)問題。

def reduce_puzzle(values):
    stalled = False
    while not stalled:
        solved_values_before = len([box for box in values.keys() if len(values[box]) == 1])
        values = eliminate(values)
        values = only_choice(values)
        solved_values_after = len([box for box in values.keys() if len(values[box]) == 1])
        stalled = solved_values_before == solved_values_after
        if len([box for box in values.keys() if len(values[box]) == 0]):
            return False
    return values

對于方格預(yù)設(shè)數(shù)字比較多的數(shù)獨(dú)問題，或許可以直接通過上述縮減取值范圍的方法解決。但當(dāng)所給預(yù)設(shè)數(shù)字方格比較少時(shí)，在完成取值范圍縮小后，必然還會有一些取值不確定的方格存在。如此問題的求解，就需要從多個(gè)可選值的方格中，分別假定其中一個(gè)進(jìn)行搜索。

而此處針對進(jìn)一步的搜索，有兩個(gè)問題需要考慮：

如何選取搜索起點(diǎn)方格？

確定哪種搜索策略：深度優(yōu)先搜索，廣度優(yōu)先搜索？

關(guān)于第一個(gè)問題，無論選擇哪個(gè)方格起始搜索，對于能否解決問題來說并不存在差異。而從求解過程的性能和效率來考慮，就有了差別。而在思考第二個(gè)問題之前，還需要明確一點(diǎn)：數(shù)獨(dú)問題的解是否唯一？顯然如果預(yù)設(shè)的方格過多且彼此矛盾，問題必然無解，而預(yù)設(shè)的方格過少，勢必也會存在多個(gè)滿足規(guī)則的解。所以為了優(yōu)先求得一個(gè)確定解，我們采取深度優(yōu)先搜索，而若是求可能的所有解，多線程進(jìn)行廣度優(yōu)先搜索，可以獲得較好的時(shí)間復(fù)雜度，但卻需要暫存許多中間信息。

def search(values):
    values = reduce_puzzle(values)
    if values is False:
        return False
    if all(len(values[s]) == 1 for s in boxes):
        return values
    n,s = min((len(values[s]), s) for s in boxes if len(values[s]) > 1)
    for value in values[s]:
        new_values = values.copy()
        new_values[s] = value
        attemp = search(new_values)
        if attemp:
            return attemp

如此數(shù)獨(dú)問題得解，但能解決速度問題的程序就能成為AI么？