自動數獨解答器 | 梓旭的藏書閣

status

date

slug

前言

本篇單純紀錄一下自己開發 Side Project 的過程，雖然是個很簡單的專案，但我寫了一整天._.

在進入教學前，就先看個 Demo 吧 :D

Demo Video(如果不能播放請移駕至 Youtube 觀賞)

功能介紹

從影片中可以看到，該程式能做到的事情如下:

自動流程控制

圖像識別

自動數獨解答

根據難度排序下來大概是 2>3>1，因此本文的講解順序將會反過來，由簡單的部分開始講起。

本文示範的網站是~~隨便找的~~某不知名數獨網站，不過不用擔心會因為網站的差異而寫不出來，

雖然確實會有部分網站的設計會讓程式寫起來比較麻煩，但本文是用土法煉鋼的方式解決，

因此應該是足以應付大部分的情況。

下面的程式碼是主程式中最核心的部分，可以看到主要的流程是流程控制取得截圖(getFullPic) → 透過截圖辨識題目(predictor.predict) → 計算結果(solver.solve)，除了流程控制的程式碼較散以外，另外的兩個部分我會切成獨立的 Module，並且盡量完整的解釋細節，~~流程控制的說明部分真的沒啥東西可以寫==~~

自動流程控制

最為簡單的部分，卻是麻煩至極，如果你有 pyautogui 的基礎的話，大致可以跳過這部分。

但我是出於懶惰才選擇使用 pyautogui，也就註定了沒有什麼泛用性，我個人還是推薦如果條件許可，盡量使用 Selenium 替代。

當然如果你找到的網站有支援使用請求的方式，嘗試全部用發請求的方式是最方便的，但出於~~筆者的~~方便，本文僅使用 pyautogui 做示範。

取得座標點

pyautogui 作為一個可以模擬各種操作的套件，最常見的使用方法就是使用座標來指定鼠標操作的位置，因此我們要先取得各種所需要的座標點，透過以下的程式碼，你只要將滑鼠移到目標物件的位置，按下鍵盤上的 a 鍵，就可以取得該位置的座標了。

要注意的是平常並不會呼叫這個函式，因為一但進去這個無限迴圈就再也出不來了，因此請在拿到想要的資料後要記得把呼叫的部分註解掉。

模擬滑鼠輸入

通常我會習慣將一組動作包成一個函式，並且將各個需要的座標點用註解的方式寫上其代表的意義，不然完全會 Debug 到懷疑人生，相信我==

另外要注意的是要在各個鼠標移動的間隔留下給網頁載入的時間，通常會抓個 1~2 秒左右比較保險。~~或是單純我家網路比較爛~~

截圖

這邊使用 keyboard 套件與 PIL 的 ImageGrab 來做截圖的操作模擬以及剪貼簿的讀取，基本上透過 pyautogui 就可以很輕鬆的完成截圖流程。

模擬鍵盤輸入

作為提交答案的部分，就只有非常簡單的將拿到的答案矩陣做一次完整的 iterate，並且利用該網站的特性(在最右邊的格子再按一次右方向鍵會回到最左邊)，從左至右將答案填入，如果網站沒有這個功能就只能用滑鼠一個一個點了，我是建議珍愛生命遠離麻煩，可以先多測幾個網站確定流程控制好不好寫，畢竟柿子總要挑軟的吃。

小結

至此，流程控制的部分就結束了，基本上該部分就是將作業性的流程用程式模擬出來，雖然非常陽春，但要應付本專案的需求已經綽綽有餘，如果要用兩個字總結這部分的工作，那我想大概是坐牢吧，本專案最無聊的部分就在這邊==

自動數獨解答

回溯法

想當初我在學習算法的時候，回溯法的章節給了我最大的驚訝~~(而 dp 給了我最大的驚嚇)~~，讀到的時候我不禁為剪枝思想的精妙所感到震撼，而用回溯法來解決數獨的問題便是書中的經典案例，也就是當時讓我心中萌生了本專案的雛型，雖然我拖了大概三百年才開始動手寫這專案==

如果你是未曾學過回溯法的人，簡單解釋一下核心概念就是在所有的空格子枚舉所有可能()實在太笨，因此我們可以省去枚舉不可能的部分，當某一格填了 1 後，在同樣的行列與九宮內就不必再枚舉 1，直到發現情況與題目給定的條件發生矛盾，說明該格不可能是 1(如果該格為 1 會導致本局數獨無解)，就這樣一路從 1 枚舉到 9，總會有至少一種可能滿足題目給定的要求，而答案就這樣被輕易的求出來了。就算是世界上公認最難的數獨，使用回溯法也可以保證在一秒內就得出結果。

簡單寫成程式碼如下(用 0 代表空格子):

圖像識別

透過上一段程式碼，我們可以做到的事情是只要給定一個數獨矩陣，我們就能求出正確的解答。

而最後剩下的部分也就是最麻煩的部分，輸入一張數獨網站的截圖，輸出該圖片對應的數獨矩陣，如下圖所示:

本文會教你從頭開始訓練一個 CNN 模型，而訓練模型的第一步就是產生 Dataset，還好以本專案來說，自產 Dataset 的難易度可以說是一塊小蛋糕。

自產 Dataset

如果要教會模型識別數獨的棋盤，可以用兩種方式達成。

第一種是餵模型整張圖片，直接輸出 9*9 的矩陣。

第二種是將圖片切割成 81 格小圖片，並一一對應到 0~9(0代表空白)，再將結果組合在一起。

本文使用的是第二種方法，因為第一種我不會寫QQ

準備 Dataset 的流程如下:

對題目截圖 → 切割成 81 個小格子 → Label → 重覆

截圖部分的程式碼請見上一個段落，而第二個部分的程式碼也不難，這邊就直接用程式帶過。

Label 的部分如果你的網站比較簡單，可能可以透過爬蟲或是封包的方式拿到該格的正確答案，這種方式比直接 OCR 的方式更好更讚，除了更簡單之外還可以保證 100% 的正確率，可是如果跟我一樣不幸的話，我們就只能透過 OCR 的手段來做 Label 了。

原本筆者使用 EasyOCR 卻發現好像沒有支援這麼小的圖片，於是鬼轉 Tesseract OCR 來解決自動 Label 的問題。

不過 Tesseract 的準確率本來就沒有 EasyOCR 高，很容易辨識出一堆妖魔鬼怪，我個人建議將所有辨識出來不是數字的圖片都視為 0，最後再去手動濾掉誤判的結果就好，不過要小心的是正常的結果也有可能誤判，記得訓練前要把所有資料都再看過兩三次，確保餵給模型的資料是對的。

透過辨識出來結果來對圖片用以下的結構做分類，就可以得到很多很多 Dataset 啦，我自己大概每個 Class 準備了 1000 張左右的資料，就可以 Train 出效果不錯的 Model 了。

這邊有個小 tips 是在訓練的時候可以開簡單版的 puzzle，一次可以蒐集到的資料會比較多。

還有這部分要特別注意的事情是持續跑下去，空格的資料一定會比其他的 Class 還要多很多，要嘛手動把多的資料刪掉，要嘛要記得做 downsampling，我自己是兩個都有做，但做前者最主要的原因是因為 Class 0 的資料是最亂的，整理完 1000 筆後面的 4000 筆就不想看了，直接全部刪掉w

Training

Model

生出了足夠的 Dataset 後就可以熱血開 Train 啦，不過在那之前當然要來設計一下我們的 CNN Model了，如果你對 CNN 一無所知也沒關係，簡單直接用程式碼介紹一下他的架構:

Convolution Layer: 主要負責提取特徵，這邊因為第一層輸入的灰階圖只有一個 Channel，所以輸入的參數就是 1，而第二層輸出的 Channel 64 代表會生成 64 個特徵圖。

Fully Connect Layer: 將特徵平坦化，因為最後只有 10 種結果(0~9)，所以給定輸出 10 個 Class。

Max Pooling Layer: 對特徵做模糊化，除了減少計算量之外，還可以避免 Overfitting。

Preprocessing

到了對 dataset 做 preprocessing 的環節，這邊倒是沒有做什麼特殊的處理，除了灰階跟 resize 到 28*28 之外，剩下的就是常見的轉換為 Tensor 和 Normalization，基本上跟其他的 CV 專案沒什麼區別。

至於剩下的 downsampling 就可加可不加，如果你的資料收集的很 balance 可看情況省略。

準備 testing set

這邊撥出兩成的 dataset 來做 testing，直接調用 random_split method 即可。

至於這邊關於 loss function 的選擇，因為我們實際上是在做一個 Classifer，因此直接使用 Cross Entropy 即可。

Training

Training 的部分也沒什麼特別的，跑了 10 個 epoch 左右就有不錯的效果了，甚至 loss 有可能會掉到低於 0.001，但再怎麼低最後的預測都還是有可能會出錯，因此還是建議要對 Model 做例外處理。

最後當然要計算一下 Model 的 Accuracy 與 F1-score，因為是簡單的分類任務，因此應該要很輕易地拿到很高的 Accuracy 與 F1-score。

Predict

通常我個人習慣將 Training 的環境與 Predict 的環境分開，除了不太習慣用 ipynb 之外，Predict 直接調用既存的權重檔可以省去很多時間。

因此我們需要在 predictor.py 重覆宣告同樣的結構，直接複製貼上同樣的架構即可。

出於方便性的考量，我將 Predictor 封裝成一個單獨的 Class，輸入的圖片是完整的 9*9 圖片，而在這個 Class 中會做跟在 DatasetGenerator 中一樣的事情，也就是將 9*9 的圖片切割成 81 個小圖片。

接下來的事情只剩下將每個格子的預測結果依序輸入到 Model 中做 Predict，並將結果寫回提前準備好的 list 中，這部分的工作就大功告成啦。

結語

本次的專案雖然初步構想覺得沒什麼難點，頂多就是流程控制麻煩了一點，結果出乎意料之外的不順利==

一開始模型的輸出無論如何都全是 0，最後換了一種寫法才正常輸出，到現在還是不知道問題在哪==

如果這次的專案能夠幫到你學到更多東西就好啦，所有的 Code 跟 Dataset 都會放上我的 Github，歡迎載下來玩一玩~~然後發PR幫我修BUG~~

很久沒有這麼認真寫教學文了，根據傳統最後肯定要留一句我最近喜歡的話，那麼我們就下個文章再見吧。

再一次談到自己的年齡，前綴是”我才”還是”我已經”?