最近從GP上翻出了之前玩的一款消磨時間的游戲“數(shù)獨世界” --le.lenovo.sudoku，登陸了GP賬號發(fā)現(xiàn)已經(jīng)取得了一些成就，但之前的記錄沒了，得從新開始玩。懶得費力的去重復(fù)完成之前關(guān)卡，于是想著怎么能自動填充數(shù)獨。

抱著試一試的態(tài)度，開始了研究。

一、反編譯

這款app做了混淆處理，和一些簡單的防反編譯的措施。正常的工具會失敗，得使用強力的反編譯工具才行。

1、去廣告

廣告挺多的，從splash activity、ResumeGameActivity、SudokuActivity等頁面都有廣告。查看了一下，是使用的Android原生廣告，并且程序打印了廣告的一些log出來。順著log可以找到關(guān)鍵地方，然后禁用掉。在AndroidManifest.xml中，也可以看到廣告activity的聲明，直接刪掉就好了。剩下可能殘留一些banner廣告，暫時留著吧，也給開發(fā)者留點收入。

2、分析頁面布局

游戲的主頁面是SudokuActivity，查看布局發(fā)現(xiàn)，棋盤宮格的部分是自定義SuduPuzzleView，使用draw方法繪制出來。因為對Android不了解，沒想到什么辦法能夠識別這塊內(nèi)容。代碼中做了混淆，數(shù)獨的生成的地方也懶得找（不才，沒找到），于是就換了種思路，打算用python來解決。

二、用python解決

總體的方法思路如下：
識別初始化的數(shù)獨 -> 解數(shù)獨 -> 將解填入至游戲中

1、解數(shù)獨

最復(fù)雜的部分就是解數(shù)獨了，好的算法會更快。但是算法什么的目前還搞不定，先找一找解數(shù)獨的相關(guān)資料用現(xiàn)成的。發(fā)現(xiàn)一個排除候選猜測法，感覺還是很不錯的。試驗了一些數(shù)獨，解得很快，具體的算法可以參看他的page。
Python秒解最難數(shù)獨

大概是這樣：先是采用“排除候選法”，確定能確定的數(shù)字，中間還額外增加了隱形排除法用來簡化問題。當(dāng)所有的空位都確定后，仍有一些空位有多個值，這時候就采用作者后半部分的猜測算法。先是進(jìn)行對候選的列表進(jìn)行評分，根據(jù)評分選擇候選列表中數(shù)字最少的一個來開始 猜測-回溯。

2、識別數(shù)獨

有了解數(shù)獨的方法，剩下的就好辦了，只需給他傳一個初始化的data數(shù)組就行。有內(nèi)容的填對應(yīng)的數(shù)字，空內(nèi)容的則填寫0。

初始化數(shù)組的方法打算用圖片處理：先把當(dāng)前游戲頁面截圖，然后分別識別數(shù)獨9x9宮格的對應(yīng)內(nèi)容，之后存入data數(shù)組

處理圖片用的是PIL庫，用到的基本操作都很簡單：

# 讀取image
image = Image.open(ori_img)

# 確定剪裁區(qū)域
box = (x_start, y_start, x_end, y_end)

# 剪裁圖片
newImage = image.crop(box)

#保存剪裁的圖片
newImage.save(save_file)

圖片識別使用的是tesseract-ocr引擎和pytesseract庫。因為游戲中數(shù)字的背景很純（忽略顏色），所以非常容易識別，出錯率很小。使用方法也異常的簡單。需要注意的就是參數(shù)psm，不同情況需要調(diào)整psm參數(shù)才行。

# PIL 打開已經(jīng)剪裁好的圖片
image = Image.open(img)

# 轉(zhuǎn)換為L -> 灰色圖像 方便識別。
# 關(guān)于PIL其他8種模式可以翻閱其他資料，這里采用L模式
image = image.convert('L')

# 使用pytesseract模塊中的image_to_string方法，將圖片識別的數(shù)字轉(zhuǎn)為string。
text = pytesseract.image_to_string(image, config='-psm 9')

# string轉(zhuǎn)int，這里偷懶，沒做校驗。如果出錯的就掛了╥﹏╥...
number = int(text)

# 返回數(shù)字供調(diào)用方
return number

附：psm參數(shù)的說明，可以使用命令tesseract --help-psm查看

$ tesseract --help-psm
Page segmentation modes:
  0    Orientation and script detection (OSD) only.
  1    Automatic page segmentation with OSD.
  2    Automatic page segmentation, but no OSD, or OCR.
  3    Fully automatic page segmentation, but no OSD. (Default)
  4    Assume a single column of text of variable sizes.
  5    Assume a single uniform block of vertically aligned text.
  6    Assume a single uniform block of text.
  7    Treat the image as a single text line.
  8    Treat the image as a single word.
  9    Treat the image as a single word in a circle.
 10    Treat the image as a single character.
 11    Sparse text. Find as much text as possible in no particular order.
 12    Sparse text with OSD.
 13    Raw line. Treat the image as a single text line,
            bypassing hacks that are Tesseract-specific.

這樣通過識別9x9宮格的圖片后，我們就自然而然的轉(zhuǎn)化為我們需要的data數(shù)組。另外，解法中最后提供的類型是numpy的ndarray類型。

3、填充數(shù)字

這里更懶，通過最原始的adb點坐標(biāo)形式。。。將數(shù)獨的81個數(shù)據(jù)與對應(yīng)的81個坐標(biāo)聯(lián)系起來，通過for循環(huán)依次填進(jìn)去。因為只在自己的機器上，所以坐標(biāo)什么的都寫死了??。

# 點擊空格坐標(biāo)定位
adb -s %s shell input tao x y
# 輸入當(dāng)前空格的解
adb -s %s shell input text num_input_from_data 

三、實驗

過程主要耗費在初始化data數(shù)組的時候，因為是線性執(zhí)行的來保證數(shù)組的正確順序，識別完一個后，才識別下一個。關(guān)于順序問題暫時沒想好怎么優(yōu)化，最后填充解的時候也是一個個填進(jìn)去的??。。。

最終效果，點開查看gif。
（不知道為什么，gif有的時候動，有的時候不動??）

四、總結(jié)

其實到了后面，目的就已經(jīng)不是自動解題了。。。而是在這個過程中接觸的新東西。

1、了解了數(shù)獨

之前只是單純的玩兒，但是沒想到解題的過程中運用了很高深的知識，尤其是自己摸索出的一切技巧，居然有一些高大上的對應(yīng)名詞。

2、查看了各種數(shù)獨的解題算法

思路可以理解，但寫不出來。。。

3、接觸了Tesseract-OCR引擎

發(fā)現(xiàn)圖像識別可以運用到自己的工作中，如解決一些需要人工驗證的自動化。感覺非常好玩，在試驗過程中，有一些識別的不是很好，還能通過訓(xùn)練來提高識別度。