用Python玩燒腦小游戲《一筆畫完》，瞬間闖到100關

作者：奶權 2018-10-24 09:40:33

開發后端開發工具

昨天和朋友出去外面吃飯，吃完飯后朋友打開了一個小程序玩了起來......

[[247317]]

游戲長這樣

大概玩法是：從地圖中貓的位置開始出發，并且經過所有的格子就算過關。游戲還算挺有意思的，經過我的不斷努力終于過到了 30 來關的樣子。

并且隨著游戲關卡的增加，游戲難度也變得越來越大，過一關需要非常久的時間。

最近也正好在研究算法，就打算看能不能寫個通用的算法來找出每個地圖的解。

哥尼斯堡的"七橋問題"

這個游戲的玩法和哥尼斯堡的"七橋問題"有點類似。

哥尼斯堡的"七橋問題"：18 世紀著名古典數學問題之一。在哥尼斯堡的一個公園里，有七座橋將普雷格爾河中兩個島及島與河岸連接起來(如下圖)。是否可能從這四塊陸地中任一塊出發，恰好通過每座橋一次，再回到起點?

當時人們想到的證明方法是把七座橋的走法都列出來一個一個試驗，用排列組合的知識很容易得到七座橋所有的走法大概有 7! = 5040 種，如果真的逐一試驗，會是個很大的工作量。

但數學家歐拉沒有這樣想，歐拉把兩座島和河兩岸抽象成頂點，七座橋抽象成連接每個頂點的七條邊，那么這個問題就能被抽象成下面的圖：

假設每座橋都恰好走過一次，那么對于 A、B、C、D 四個頂點中的每一個頂點，需要從某條邊進入，同時從另一條邊離開，進入和離開頂點的次數是相同的，即每個頂點有多少條進入的邊，就有多少條出去的邊。

也就是說：每個頂點相連的邊是成對出現的，即每個頂點的相連邊的數量必須是偶數。

很明顯，上圖中 A、C、D 三個頂點相連的邊都有 3 條，B 頂點的相連邊為 5 條，都是奇數。因此這個圖無法從一個頂點出發，且恰好走過每座橋一次。

由此次證明，人們又得到了歐拉路關系，要使得一個圖形可以一筆畫完，必須滿足如下兩個條件：

圖形必須是連通的不能有孤立的點。
圖中擁有奇數連接邊的點必須是 0 或 2。

對于一個連通圖，通常把從某結點出發一筆畫成所經過的路線叫做歐拉路。那么這個游戲是不是就是讓我們找到一條歐拉路呢?

對游戲進行抽象

按照上面證明七橋問題的方法，我們可以將游戲的地圖抽象成這樣：

其中 14 號頂點為起點。
頂點和邊的關系在程序中可以刻畫成一個二維列表。

graph = [ 
    [1, 6],    #0 
    [0, 2],    #1 
    [1, 7, 3], #2 
    ... 
    [24, 19]   #25 
]

graph 列表的***層表示每一個頂點，第二層則是與當前頂點有邊的頂點。

抽象完這張游戲地圖后可以很清楚知道，這游戲并不是讓我們找到一條歐拉路。

因為找到一條歐拉路，需要的是經過每一座橋，且只經過一次，也就是說每個頂點可以被多次經過。

而這個游戲需要的是經過每一個頂點，并不要求走完每一座橋，且頂點只能被經過一次。

哈密頓通路

在研究了七橋問題發現并不能解決這類問題后，我開始向團隊的表哥們請教，其中一個表哥告訴我此類問題叫做哈密頓圖 (這里感謝下團隊的**@xq17**表哥)。

這里說的哈密頓圖，實際上是哈密頓通路的一種特殊情況，指的是：由指定的起點出發，途中經過所有其他頂點且只經過一次，***返回起點，稱之為哈密頓回路。如果給定的圖 G 具有哈密頓回路，則稱圖 G 為哈密頓圖。

那么現在目標明確了，這個游戲的解法就是找到某個給定圖的哈密頓通路。

但是問題來了！！！哈密頓通路問題，在上世紀七十年代初，被證明是 NP-hard 問題：

一個復雜問題如果能在多項式時間內解決，那么它便被稱為 P 類問題。
一個復雜問題如果不能確定在多項式時間內解決，那么它便被稱為 NP 類問題。

什么意思呢？就拿質因數分解來說吧：

P 類問題：23x37=?
NP 類問題：已知 axb=740914799，且 a 和 b 都是質數，求 a 和 b 的值

讓我們來看看這個問題有多復雜：

因為 axb=740914799，且 a 和 b 都是質數
設 P={x|2<=x<740914799/2，x 是質數}
易得 (a，b)∈PxP，即 P 與它自身的笛卡爾積

我們用一種叫做篩法的算法來求一下 P 集合的元素個數：

#! /usr/bin/env python 
# -*- coding: utf-8 -*- 
# Coding with love by Naiquan. 
import math 
import time 
start = time.clock() 
number = int(740914799/2) 
marks_list = [True] * (number + 1) 
marks_list[0] = marks_list[1] = False 
for i in range(2, int(math.sqrt(number)) + 1): 
    j = i 
    t = j 
    # 去掉倍數 
    while j * t <= number: 
        marks_list[j * t] = False 
        t += 1 
elapsed = str(time.clock() - start) 
print marks_list.count(True) 
print "Time used:" + elapsed

一共有 19841519 個質數，算了我大概 14 分鐘。

PxP 的元素個數一共有 19841519^2 個，要一個個驗證是否等于 740914799，無疑又是一項很大的工程，這就是典型的 NP 類問題。NP 類問題雖然難，但是可以很快驗證一個給定的答案，是否正確。

比如上面的題，我告訴你答案 a=22229，b=33331，你很快就能驗證答案是否正確了。而 NP-hard 問題則是比 NP 問題更難的問題，例如：圍棋。

也就是說并不能找到一個友好的算法，來解決哈密頓通路問題。

算法設計

雖然找到一個圖的哈密頓通路是 NP 困難的，但是好在游戲中的頂點不算太多，還是可以使用暴力一點的方法實現的，例如：圖的深度優先遍歷法(DFS) 即遞歸和回溯法思想。

算法流程：

①將當前頂點壓入已訪問棧和路徑棧中。

②將與當前頂點相通的頂點列出來。

③隨機選取一個相通的頂點，并判斷此頂點是否在已訪問棧中：

在已訪問棧中則取另一個相通的頂點。
不在則將這個相通的頂點作為當前頂點。
若所有相通的頂點都在已訪問棧中，則判斷路徑棧是否包含所有頂點。
路徑棧中包含所有頂點，則路徑棧為當前圖的哈密頓通路。
不包含所有頂點則回到父頂點，并從已訪問棧和路徑棧中刪除。

④反復執行 1~3。

算法實現

上面說過圖的頂點和邊的關系可以用一個二維列表來描述：

graph = [ 
    [1, 6],    #0 
    [0, 2],    #1 
    [1, 7, 3], #2 
    ... 
    [24, 19]   #25 
]

但是要手動輸入這些頂點和邊的關系還是太麻煩了。仔細想了下，如果每個頂點的上下左右有頂點，就一定與上下左右的頂點有邊。

那么這個二維列表就可以簡化成

graph = [ 
    [1,1,1,1,1,1], 
    [1,0,1,1,0,1], 
    [1,1,1,1,1,1], 
    [1,0,1,1,0,1], 
    [1,1,1,1,1,1], 
    [0,0,0,0,0,0]    #每個1代表一個頂點 1與上下左右的1都有邊 與0則沒有 長寬相等易于編寫代碼 
]

還可以再簡化成一維列表：

graph = [ 
    '111111', 
    '101101', 
    '111111', 
    '101101', 
    '111111', 
    '000000' 
]

簡直機智如我啊！于是我寫了個函數對一維列表進行轉換：

def get_index(i, j, G): 
    num = 0 
    for a in xrange(i): 
        num += G[a].count('0') 
    for b in xrange(j): 
        if G[i][b] == '0': 
            num += 1 
    return i * len(G) + j - num 
def get_graph(G): 
    G = [list(x) for x in G] 
    EG = [] 
    for i in xrange(len(G)): 
        for j in range(len(G[i])): 
            if G[i][j] == '0': 
                continue 
            side_list = [] 
            if j+1 <= len(G[i]) - 1: 
                if G[i][j+1] == '1': 
                    index = get_index(i, j+1, G) 
                    side_list.append(index) 
            if j-1 >= 0: 
                if G[i][j-1] == '1': 
                    index = get_index(i, j-1, G) 
                    side_list.append(index) 
            if i+1 <= len(G) - 1: 
                if G[i+1][j] == '1': 
                    index = get_index(i+1, j, G) 
                    side_list.append(index) 
            if i-1 >= 0: 
                if G[i-1][j] == '1': 
                    index = get_index(i-1, j, G) 
                    side_list.append(index) 
            EG.append(side_list) 
    return EG

而算法的實現用圖的鄰接矩陣則更為方便，因此我寫了一個將上列二位列表轉換成鄰接矩陣形式的函數：

def get_matrix(graph): 
    result = [[0]*len(graph) for _ in xrange(len(graph))]  # 初始化 
    for i in xrange(len(graph)): 
        for j in graph[i]: 
            result[i][j] = 1  # 有邊則為1 
    return result

主要的 DFS 算法如下：

# graph為圖的鄰接矩陣 used為已訪問棧 path為路徑棧 step為已經遍歷的頂點的個數 
def dfs(graph, path, used, step): 
    if step == len(graph): # 判斷頂點是否被遍歷完畢 
        print path 
        return True 
    else: 
        for i in xrange(len(graph)): 
            if not used[i] and graph[path[step-1]][i] == 1: 
                used[i] = True 
                path[step] = i 
                if dfs(graph, path, used, step+1): 
                    return True 
                else: 
                    used[i] = False  # 回溯 返回父節點 
                    path[step] = -1 
    return False 
def main(graph, v): 
    used = []  # 已訪問棧 
    path = []  # 路徑棧 
    for i in xrange(len(graph)): 
        used.append(False)  # 初始化 所有頂點均未被遍歷 
        path.append(-1)     # 初始化 未選中起點及到達任何頂點 
    used[v] = True          # 表示從起點開始遍歷 
    path[0] = v             # 表示哈密頓通路的***個頂點為起點 
    dfs(graph, path, used, 1)

完整代碼如下：

#! /usr/bin/env python 
# -*- coding: utf-8 -*- 
# Coding with love by Naiquan. 
def dfs(graph, path, used, step): 
    if step == len(graph): 
        print path 
        return True 
    else: 
        for i in xrange(len(graph)): 
            if not used[i] and graph[path[step-1]][i] == 1: 
                used[i] = True 
                path[step] = i 
                if dfs(graph, path, used, step+1): 
                    return True 
                else: 
                    used[i] = False 
                    path[step] = -1 
    return False 
def main(graph, v): 
    used = [] 
    path = [] 
    for i in xrange(len(graph)): 
        used.append(False) 
        path.append(-1) 
    used[v] = True 
    path[0] = v 
    dfs(graph, path, used, 1) 
def get_index(i, j, G): 
    num = 0 
    for a in xrange(i): 
        num += G[a].count('0') 
    for b in xrange(j): 
        if G[i][b] == '0': 
            num += 1 
    return i * len(G) + j - num 
def get_graph(G): 
    G = [list(x) for x in G] 
    EG = [] 
    for i in xrange(len(G)): 
        for j in range(len(G[i])): 
            if G[i][j] == '0': 
                continue 
            side_list = [] 
            if j+1 <= len(G[i]) - 1: 
                if G[i][j+1] == '1': 
                    index = get_index(i, j+1, G) 
                    side_list.append(index) 
            if j-1 >= 0: 
                if G[i][j-1] == '1': 
                    index = get_index(i, j-1, G) 
                    side_list.append(index) 
            if i+1 <= len(G) - 1: 
                if G[i+1][j] == '1': 
                    index = get_index(i+1, j, G) 
                    side_list.append(index) 
            if i-1 >= 0: 
                if G[i-1][j] == '1': 
                    index = get_index(i-1, j, G) 
                    side_list.append(index) 
            EG.append(side_list) 
    return EG 
def get_matrix(graph): 
    result = [[0]*len(graph) for _ in xrange(len(graph))] 
    for i in xrange(len(graph)): 
        for j in graph[i]: 
            result[i][j] = 1 
    return result 
if __name__ == '__main__': 
    map_list = [ 
        '111111', 
        '101101', 
        '111111', 
        '101101', 
        '111111', 
        '000000' 
    ] 
    G = get_graph(map_list) 
    map_matrix = get_matrix(G) 
    # print map_matrix 
    SP = 14 
    main(map_matrix, SP)