用Python玩燒腦小游戲《一筆畫完》，瞬間闖到100關
昨天和朋友出去外面吃飯，吃完飯后朋友打開了一個小程序玩了起來......
游戲長這樣
大概玩法是：從地圖中貓的位置開始出發(fā)，并且經(jīng)過所有的格子就算過關。游戲還算挺有意思的，經(jīng)過我的不斷努力終于過到了 30 來關的樣子。
并且隨著游戲關卡的增加，游戲難度也變得越來越大，過一關需要非常久的時間。
最近也正好在研究算法，就打算看能不能寫個通用的算法來找出每個地圖的解。
哥尼斯堡的"七橋問題"
這個游戲的玩法和哥尼斯堡的"七橋問題"有點類似。
哥尼斯堡的"七橋問題"：18 世紀著名古典數(shù)學問題之一。在哥尼斯堡的一個公園里，有七座橋?qū)⑵绽赘駹柡又袃蓚€島及島與河岸連接起來(如下圖)。是否可能從這四塊陸地中任一塊出發(fā)，恰好通過每座橋一次，再回到起點?
當時人們想到的證明方法是把七座橋的走法都列出來一個一個試驗，用排列組合的知識很容易得到七座橋所有的走法大概有 7! = 5040 種，如果真的逐一試驗，會是個很大的工作量。
但數(shù)學家歐拉沒有這樣想，歐拉把兩座島和河兩岸抽象成頂點，七座橋抽象成連接每個頂點的七條邊，那么這個問題就能被抽象成下面的圖：
假設每座橋都恰好走過一次，那么對于 A、B、C、D 四個頂點中的每一個頂點，需要從某條邊進入，同時從另一條邊離開，進入和離開頂點的次數(shù)是相同的，即每個頂點有多少條進入的邊，就有多少條出去的邊。
也就是說：每個頂點相連的邊是成對出現(xiàn)的，即每個頂點的相連邊的數(shù)量必須是偶數(shù)。
很明顯，上圖中 A、C、D 三個頂點相連的邊都有 3 條，B 頂點的相連邊為 5 條，都是奇數(shù)。因此這個圖無法從一個頂點出發(fā)，且恰好走過每座橋一次。
由此次證明，人們又得到了歐拉路關系，要使得一個圖形可以一筆畫完，必須滿足如下兩個條件：
- 圖形必須是連通的不能有孤立的點。
- 圖中擁有奇數(shù)連接邊的點必須是 0 或 2。
對于一個連通圖，通常把從某結(jié)點出發(fā)一筆畫成所經(jīng)過的路線叫做歐拉路。那么這個游戲是不是就是讓我們找到一條歐拉路呢?
對游戲進行抽象
按照上面證明七橋問題的方法，我們可以將游戲的地圖抽象成這樣：
- 其中 14 號頂點為起點。
- 頂點和邊的關系在程序中可以刻畫成一個二維列表。
- graph = [
- [1, 6], #0
- [0, 2], #1
- [1, 7, 3], #2
- ...
- [24, 19] #25
- ]
graph 列表的***層表示每一個頂點，第二層則是與當前頂點有邊的頂點。
抽象完這張游戲地圖后可以很清楚知道，這游戲并不是讓我們找到一條歐拉路。
因為找到一條歐拉路，需要的是經(jīng)過每一座橋，且只經(jīng)過一次，也就是說每個頂點可以被多次經(jīng)過。
而這個游戲需要的是經(jīng)過每一個頂點，并不要求走完每一座橋，且頂點只能被經(jīng)過一次。
哈密頓通路
在研究了七橋問題發(fā)現(xiàn)并不能解決這類問題后，我開始向團隊的表哥們請教，其中一個表哥告訴我此類問題叫做哈密頓圖 (這里感謝下團隊的**@xq17**表哥)。
這里說的哈密頓圖，實際上是哈密頓通路的一種特殊情況，指的是：由指定的起點出發(fā)，途中經(jīng)過所有其他頂點且只經(jīng)過一次 ，***返回起點，稱之為哈密頓回路。如果給定的圖 G 具有哈密頓回路，則稱圖 G 為哈密頓圖。
那么現(xiàn)在目標明確了，這個游戲的解法就是找到某個給定圖的哈密頓通路。
但是問題來了?。?！哈密頓通路問題，在上世紀七十年代初，被證明是 NP-hard 問題：
- 一個復雜問題如果能在多項式時間內(nèi)解決，那么它便被稱為 P 類問題。
- 一個復雜問題如果不能確定在多項式時間內(nèi)解決，那么它便被稱為 NP 類問題。
什么意思呢？就拿質(zhì)因數(shù)分解來說吧：
- P 類問題：23x37=?
- NP 類問題：已知 axb=740914799，且 a 和 b 都是質(zhì)數(shù)，求 a 和 b 的值
讓我們來看看這個問題有多復雜：
- 因為 axb=740914799，且 a 和 b 都是質(zhì)數(shù)
- 設 P={x|2<=x<740914799/2，x 是質(zhì)數(shù)}
- 易得 (a，b)∈PxP，即 P 與它自身的笛卡爾積
我們用一種叫做篩法的算法來求一下 P 集合的元素個數(shù)：
- #! /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
- # 去掉倍數(shù)
- 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 個質(zhì)數(shù)，算了我大概 14 分鐘。
PxP 的元素個數(shù)一共有 19841519^2 個，要一個個驗證是否等于 740914799，無疑又是一項很大的工程，這就是典型的 NP 類問題。NP 類問題雖然難，但是可以很快驗證一個給定的答案，是否正確。
比如上面的題，我告訴你答案 a=22229，b=33331，你很快就能驗證答案是否正確了。而 NP-hard 問題則是比 NP 問題更難的問題，例如：圍棋。
也就是說并不能找到一個友好的算法，來解決哈密頓通路問題。
算法設計
雖然找到一個圖的哈密頓通路是 NP 困難的，但是好在游戲中的頂點不算太多，還是可以使用暴力一點的方法實現(xiàn)的，例如：圖的深度優(yōu)先遍歷法(DFS) 即遞歸和回溯法思想。
算法流程：
①將當前頂點壓入已訪問棧和路徑棧中。
②將與當前頂點相通的頂點列出來。
③隨機選取一個相通的頂點，并判斷此頂點是否在已訪問棧中：
- 在已訪問棧中則取另一個相通的頂點。
- 不在則將這個相通的頂點作為當前頂點。
- 若所有相通的頂點都在已訪問棧中， 則判斷路徑棧是否包含所有頂點。
- 路徑棧中包含所有頂點，則路徑棧為當前圖的哈密頓通路。
- 不包含所有頂點則回到父頂點， 并從已訪問棧和路徑棧中刪除。
④反復執(zhí)行 1~3。
算法實現(xiàn)
上面說過圖的頂點和邊的關系可以用一個二維列表來描述：
- 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'
- ]
簡直機智如我啊！于是我寫了個函數(shù)對一維列表進行轉(zhuǎn)換：
- 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
而算法的實現(xiàn)用圖的鄰接矩陣則更為方便，因此我寫了一個將上列二位列表轉(zhuǎn)換成鄰接矩陣形式的函數(shù)：
- 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為已經(jīng)遍歷的頂點的個數(shù)
- 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 # 回溯 返回父節(jié)點
- 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)
結(jié)束
在實現(xiàn)了功能后，我拿著這個程序成功過到了差不多一百關，然后就玩膩了，哈哈哈哈哈哈哈哈哈
本文參考資料：
- 七橋問題_百度百科
https://baike.baidu.com/item/七橋問題/2580504?fr=aladdin
- 哈密頓圖_百度百科
https://baike.baidu.com/item/哈密頓圖/2587317?fr=aladdin
- 這個數(shù)學題我做可以，但世界毀滅了別怪我
https://www.bilibili.com/video/av19009866
- 基于回溯法尋找哈密頓回路
http://www.cnblogs.com/cielosun/p/5654577.html
