一、問題描述
一筆畫完就是從起始網格開始，也就是下圖中錦鯉喵所在的網格，用一筆劃過所有可以走(灰底)的網格，不能遺漏，也不能重復。下圖是微信小游戲一筆畫完第1350關的題目：
二、解題思路
利用DFS(深度優(yōu)先搜索)和BFS(廣度優(yōu)先搜索)算法找到所有的路徑，利用基于多線程實現(xiàn)的計時器展示尋找路徑所用的時間，最終圖示所有的解。簡單說下兩個算法的區(qū)別：
DFS(Depth First Search)也就是深度優(yōu)先搜索，也就是從起始網格開始，只要是還有可以去的網格，就一直走下去，直到走不通為止，然后再回溯到最近的一次選擇，再往下走，直到遍歷完所有的路徑。
BFS(Breadth First Search)也就是廣度(寬度)優(yōu)先搜索，也就是從起始網格開始，首先搜索與之相鄰的網格，然后在搜索與這些網格相鄰的網格。換句話說，就是逐漸的向周圍擴散搜索。
兩者利用Python實現(xiàn)的區(qū)別：DFS一般利用遞歸實現(xiàn)，因為涉及到回溯，實現(xiàn)較為復雜。因為Python中對遞歸函數(shù)有調用次數(shù)的限制，因此需要自己實現(xiàn)尾遞歸優(yōu)化。對于BFS而言，實現(xiàn)比較簡單，但是因為需要保存當前的所有路徑，當路徑較多時，占用的內存空間較大，因此需要刪除一些不合理的路徑。
從運行時間上而言，獲取一條路徑優(yōu)先選擇DFS，獲取所有路徑BFS好于DFS。但是當可走的網格數(shù)較大時，優(yōu)先選擇DFS，因為BFS可能導致內存負載超重。
三、Python3實現(xiàn)
利用numpy的數(shù)組形式來描述問題，也就是不同性質的網格給定不同的數(shù)值，便于繪圖。需要根據(jù)謎題題面，自定義輸入數(shù)組的維數(shù)，以及起始網格的索引，不可走網格的索引。根據(jù)這些設置，生成相應的二維數(shù)組，并利用matplotlib繪制出來。下面以上面的謎題為例，需要進行下面的設置：
# 豎直、水平方向網格的個數(shù)
Map_Height = 9
Map_Width = 7
# 起始網格和不能經過的網格的索引
Start_Index = [1, 0]
Stone_Index = [[0, 3], [0, 6], [1, 6], [2, 6], [3, 1], [7, 1], [8, 3], [8, 5], [8, 6]]
上圖為題面的示意圖
根據(jù)題面信息繪制的圖。
下面說一下對路徑合理性的判斷，對于一筆畫完的問題，當走過的網格和不能走的網格，把剩下可以走的網格分為不連通的兩部分時，就可判斷當前的路徑是不合理的，也就沒有在這個路徑上繼續(xù)往下搜索的意義。下圖顯示了加入路徑合理性判斷后的情況對比：
關于兩種算法的實現(xiàn)，尾遞歸的優(yōu)化以及基于多線程的計時器的實現(xiàn)，參見代碼注釋。
考慮到手動輸入題面信息的繁瑣，還實現(xiàn)了自動讀取謎題照片。當然對照片的質量要求較高(屏幕截圖可以(下圖上，第1350關的題面截圖)，相機拍攝(下圖下)會有問題)。
三、結果圖示
第1350關一共有108條路徑解法，上圖上展示了基于BFS方法的第16個，上圖下展示基于DFS方法的第108個。獲取所有路徑前者耗時大約105秒，后者大約186秒。
上圖是根據(jù)DFS，獲取的一條路徑以及所用時間。
上圖上是根據(jù)題面截圖自動讀取出來的結果，上圖下是添加路徑后的結果。因為調用的是DFS方法，所以得到的結果和上圖是一樣的。
點擊獲得更多趣味謎題。歡迎Follow，感謝Star!!! 掃描關注微信公眾號pythonfan，獲取更多。
