作者：AchillesL
若轉(zhuǎn)載文章，請(qǐng)標(biāo)明文章出處

1 序

?　　數(shù)獨(dú)是源自18世紀(jì)瑞士的一種數(shù)學(xué)游戲逞盆。是一種運(yùn)用紙者铜、筆進(jìn)行演算的邏輯游戲。玩家需要根據(jù)9×9盤(pán)面上的已知數(shù)字六孵，推理出所有剩余空格的數(shù)字凑兰，并滿(mǎn)足每一行底洗、每一列、每一個(gè)粗線宮（3*3）內(nèi)的數(shù)字均含1-9智蝠，不重復(fù)腾么。

數(shù)獨(dú)

?　　最近一段時(shí)間經(jīng)常做數(shù)獨(dú)題，并思考了一下能不能編寫(xiě)一個(gè)APP杈湾，可以自動(dòng)求解數(shù)獨(dú)解虱、最后將結(jié)果填入該APP中。

.............................................摸魚(yú)的開(kāi)發(fā)過(guò)程漆撞，此處省略10^N行字.....................................

?　　最終寫(xiě)一個(gè)APP：數(shù)獨(dú)X殴泰。可以針對(duì)筆者常用的數(shù)獨(dú)APP(本文的實(shí)現(xiàn)都基于該APP)浮驳，實(shí)現(xiàn)數(shù)獨(dú)的識(shí)別悍汛、求解、并把答案自動(dòng)填入至会。專(zhuān)家級(jí)別的平均1秒完成求解(包括圖像數(shù)字提取离咐，識(shí)別過(guò)程)，8s完成全部操作奉件。

?　　本文將簡(jiǎn)單介紹相關(guān)功能的實(shí)現(xiàn)宵蛀。文章有點(diǎn)長(zhǎng)，有需要的童鞋可善用瀏覽器的頁(yè)面搜索功能县貌。數(shù)獨(dú)X的使用效果术陶，如下圖：

效果圖，加載會(huì)有點(diǎn)慢

2 下載鏈接

??數(shù)獨(dú) APP鏈接：https://pan.baidu.com/s/1b67LlZcr7K3d3ZTxgwUobg
??數(shù)獨(dú)X APP鏈接：https://pan.baidu.com/s/1xJMTxO1dMza_mjHGrdiyHQ
??數(shù)獨(dú)X 源代碼鏈接：https://github.com/AchillesL/jianshu-sudokuX

??［注］數(shù)獨(dú)X對(duì)手機(jī)要求：Android 7.0 或以上煤痕。

3 本文內(nèi)容

• 實(shí)現(xiàn)思路介紹
• 項(xiàng)目結(jié)構(gòu)介紹
• 如何創(chuàng)建懸浮窗
• 如何獲取第三方應(yīng)用中的控件信息
• 如何無(wú)Root實(shí)現(xiàn)跨應(yīng)用截屏
• 如何提取數(shù)獨(dú)九宮格中的數(shù)字
• 如何實(shí)現(xiàn)數(shù)字識(shí)別
• 如何編寫(xiě)代碼求解數(shù)獨(dú)
• 如何實(shí)現(xiàn)模擬屏幕點(diǎn)擊
• 后記
• 參考文章

4 實(shí)現(xiàn)思路介紹

? ??步驟一：我們需要獲得數(shù)獨(dú)APP中的九宮格數(shù)字梧宫。由于數(shù)獨(dú)App是第三方應(yīng)用接谨，數(shù)獨(dú)信息當(dāng)然是無(wú)法直接獲取的，筆者的思路是打開(kāi)數(shù)獨(dú)界面后調(diào)用截屏塘匣，再通過(guò)圖片處理提取九宮格的數(shù)字脓豪。同時(shí)，為了避免截屏?xí)r遮擋應(yīng)用馆铁，數(shù)獨(dú)X的工作窗口應(yīng)該使用懸浮窗形式跑揉。

???步驟二：截屏后锅睛，我們需要進(jìn)一步截取數(shù)獨(dú)面板圖片埠巨，以便數(shù)字提取用。我們可以寫(xiě)死面板坐標(biāo)现拒、寬高來(lái)提取截圖中的面板辣垒。在這里，當(dāng)然有更好的方法印蔬，就是通過(guò)輔助功能AccessibilityService獲得數(shù)獨(dú)應(yīng)用的數(shù)獨(dú)面板坐標(biāo)信息勋桶。

???步驟三：在獲得數(shù)獨(dú)面板的圖片后，使用openCV框架提取數(shù)字的輪廓侥猬，生成數(shù)字圖片例驹，再調(diào)用TessTwo框架將圖片轉(zhuǎn)為數(shù)字，并生成原始數(shù)獨(dú)二維數(shù)組退唠。

???步驟四：數(shù)獨(dú)求解鹃锈，生成答案，并生成需要填充的數(shù)字序列瞧预。

??步驟五：最后通過(guò)輔助功能AccessibilityService類(lèi)的相關(guān)方法屎债，模擬屏幕點(diǎn)擊，輸入填充數(shù)獨(dú)的數(shù)字垢油。

流程圖

5 項(xiàng)目結(jié)構(gòu)介紹

??項(xiàng)目主要包含文件如下圖：

項(xiàng)目主要文件

時(shí)序圖

6 如何創(chuàng)建懸浮窗

?　　Android的界面繪制，都是通過(guò)WindowMananger的服務(wù)來(lái)實(shí)現(xiàn)的裁良。要實(shí)現(xiàn)一個(gè)能夠在自身應(yīng)用界面外的懸浮窗凿将，我們就要利用WindowManager類(lèi)。同時(shí)价脾，為了讓?xiě)腋〈芭cActivity脫離牧抵，讓?xiě)?yīng)用處于后臺(tái)時(shí)懸浮窗仍然可以正常運(yùn)行，這里使用Service來(lái)啟動(dòng)懸浮窗并做為其背后邏輯支撐侨把。

6.1 申請(qǐng)權(quán)限

?　　在創(chuàng)建懸浮窗前犀变，必須先申請(qǐng)權(quán)限，代碼十分簡(jiǎn)單：

（MainActivity.java）

...
private boolean startOverLay() {
    if (!Settings.canDrawOverlays(MainActivity.this)) {
        Intent intent = new Intent(Settings.ACTION_MANAGE_OVERLAY_PERMISSION);
        Toast.makeText(this, "需要取得權(quán)限以使用懸浮窗",Toast.LENGTH_SHORT).show();
        startActivity(intent);
        return false;
    }
    return true;
}
...

6.2 在service中創(chuàng)建懸浮窗

（SudokuXService.java）

...
private void initView() {
    //注意Android O版本與其他系統(tǒng)的差異
    if (Build.VERSION.SDK_INT >= Build.VERSION_CODES.O) {
        mParams.type = WindowManager.LayoutParams.TYPE_APPLICATION_OVERLAY;
    } else {
        mParams.type = WindowManager.LayoutParams.TYPE_SYSTEM_ALERT;
    }
    mParams.format = PixelFormat.RGBA_8888;
    mParams.flags = WindowManager.LayoutParams.FLAG_NOT_FOCUSABLE;
    mParams.gravity = Gravity.START | Gravity.TOP;
    mParams.x = SudokuXUtils.getScreenWidth();
    mParams.y = SudokuXUtils.getScreenHeight();
    mParams.width = SudokuXUtils.SMALL_SIZE_WIDTH;
    mParams.height = SudokuXUtils.SMALL_SIZE_HIGH;
    LinearLayout linearLayout = (LinearLayout) LayoutInflater.from(getApplication()).inflate(R.layout.layout, null);
    mBtn = linearLayout.findViewById(R.id.btn);
    
    //添加懸浮窗布局到WindowManager中
    mWindowManager.addView(linearLayout, mParams);
    ...
}
...

?　　最后在首頁(yè)啟動(dòng)SudokuXService即可秋柄，講述Android懸浮窗的文章很多获枝，讀者可自行查閱，在此不再贅述骇笔。
　　【注】這部分的代碼主要在SudokuXService.java中實(shí)現(xiàn)省店。

7 如何獲得其他APP中的控件信息

?　　本項(xiàng)目使用Android的輔助服務(wù)AccessibilityService來(lái)獲取數(shù)獨(dú)APP的控件信息。

7.1 介紹

? AccessibilityService設(shè)計(jì)初衷在于幫助殘障用戶(hù)使用android設(shè)備和應(yīng)用笨触，在后臺(tái)運(yùn)行懦傍，可以監(jiān)聽(tīng)用戶(hù)界面的一些狀態(tài)轉(zhuǎn)換，例如頁(yè)面切換芦劣、焦點(diǎn)改變粗俱、通知、Toast等持寄，并在觸發(fā)AccessibilityEvents時(shí)由系統(tǒng)接收回調(diào)源梭。后來(lái)被開(kāi)發(fā)者另辟蹊徑，用于一些插件開(kāi)發(fā)稍味，比如微信紅包助手废麻，還有一些需要監(jiān)聽(tīng)第三方應(yīng)用的插件。

? 我們可以把AccessibilityService理解為——『按鍵精靈』模庐。相信很多開(kāi)發(fā)者都玩過(guò)PC上的這款軟件烛愧，他的作用，就是將你一次操作的整個(gè)記錄掂碱，錄制下來(lái)怜姿，然后就可以根據(jù)這個(gè)記錄，重復(fù)的執(zhí)行這些操作疼燥，例如：先點(diǎn)擊某個(gè)輸入框沧卢，再輸入XXXX，再輸入驗(yàn)證碼醉者，最后點(diǎn)擊某按鈕但狭，這些操作如果需要重復(fù)執(zhí)行披诗，那么顯然是一套機(jī)械的步驟，那么通過(guò)按鍵精靈立磁，記錄下這些操作后呈队，直接通過(guò)腳本就可以完成這些操作。其實(shí)AccessibilityService跟這個(gè)是一樣的唱歧，我們記錄的宪摧，實(shí)際上就是我們的操作步驟，或者稱(chēng)之為『腳本』颅崩，那么系統(tǒng)在監(jiān)控整個(gè)手機(jī)的各種AccessibilityService事件時(shí)几于，就會(huì)根據(jù)我們的邏輯來(lái)判斷該使用哪一個(gè)腳本。

? 因此挨摸，我們完全可以抽象出一個(gè)基類(lèi)AccessibilityService孩革，并抽象出一些腳本的事件岁歉，例如得运，根據(jù)Text查找對(duì)應(yīng)的View、點(diǎn)擊某個(gè)View锅移、滑動(dòng)熔掺、返回等等。

7.2 配置

?　　首先非剃，要使用AccessibilityService實(shí)際上非常簡(jiǎn)單置逻，一般來(lái)說(shuō)，只需要以下三步即可备绽。

7.2.1 繼承系統(tǒng)AccessibilityService

public class SudokuAccessibility extends AccessibilityService {

    private static final String TAG = "lzg";

    @Override
    public void onAccessibilityEvent(AccessibilityEvent event) {
        Log.d(TAG, "onAccessibilityEvent: " + event.toString());
    }

    @Override
    public void onInterrupt() {
    }
}

?　　強(qiáng)制重新的有兩個(gè)方法：onAccessibilityEvent和onInterrupt券坞。重點(diǎn)關(guān)注onAccessibilityEvent方法，在該方法中肺素，我們可以接收所監(jiān)聽(tīng)的事件恨锚。

7.2.2 新建配置文件

?　　在資源目錄res下新建xml文件夾，新建accessibility.xml文件倍靡，寫(xiě)入：

<?xml version="1.0" encoding="utf-8"?>
<accessibility-service xmlns:android="http://schemas.android.com/apk/res/android"
    android:accessibilityEventTypes="typeAllMask"
    android:accessibilityFeedbackType="feedbackSpoken"
    android:canRetrieveWindowContent="true"
    android:canPerformGestures="true"
    android:packageNames = "com.easybrain.sudoku.android"
    android:notificationTimeout="1000"/>

?　　里面有一些比較簡(jiǎn)單的配置猴伶。本項(xiàng)目要輔助的是數(shù)獨(dú)應(yīng)用，在xml的android:packageNames處指定輔助應(yīng)用的包名塌西，即com.easybrain.sudoku.android他挎。當(dāng)沒(méi)有指定時(shí)，默認(rèn)輔助所有的應(yīng)用捡需，建議大家在使用時(shí)办桨，指定需要監(jiān)聽(tīng)的包名（你可以通過(guò)|來(lái)進(jìn)行分隔），而不是所有的包名站辉。typeAllMask是設(shè)置響應(yīng)事件的類(lèi)型呢撞，feedbackGeneric是設(shè)置回饋給用戶(hù)的方式贸街，有語(yǔ)音播出和振動(dòng)。

7.2.3 注冊(cè)

?　　最后狸相，在AndroidMainifest中注冊(cè)service信息：

<service
    android:name="com.example.sudokux.SudokuAccessibility"
    android:permission="android.permission.BIND_ACCESSIBILITY_SERVICE">
    <intent-filter>
        <action android:name="android.accessibilityservice.AccessibilityService" />
    </intent-filter>

    <meta-data
        android:name="android.accessibilityservice"
        android:resource="@xml/accessibility" />
</service>

?　　完成以上步驟后薛匪，一個(gè)輔助服務(wù)就可以使用了，AccessibilityService具有很高的系統(tǒng)權(quán)限脓鹃，所以逸尖，系統(tǒng)不會(huì)讓App直接設(shè)置是否啟用，需要用戶(hù)進(jìn)入設(shè)置-輔助功能中去手動(dòng)啟用瘸右，這樣在一定程度上娇跟，保護(hù)了用戶(hù)數(shù)據(jù)的安全。

??這里不再贅述AccessibilityService的基本用法太颤，有需要的讀者可參考相關(guān)文章苞俘，例如：AccessibilityService從入門(mén)到出軌。

7.3 使用

?　　本節(jié)介紹如何數(shù)獨(dú)APP的控件信息以及代碼編寫(xiě)龄章。

7.3.1 通過(guò)Layout Inspector工具吃谣，獲取數(shù)獨(dú)APP的控件信息

?　　使用AccessibilityService拿到數(shù)獨(dú)APP的控件信息，我們必須先知道對(duì)應(yīng)的控件id做裙。這一步岗憋，我們可以使用Android Studio的Layout Inspector工具來(lái)完成。

??先啟動(dòng)數(shù)獨(dú)APP锚贱，在Android Studio中仔戈，點(diǎn)擊Tools->Layout Inspector，選中包名：com.easybrain.sudoku.android拧廊，即可以看到一下畫(huà)面：

?　　可見(jiàn)數(shù)獨(dú)面板id為sudoku_board监徘，1-9的數(shù)字按鈕id分別是button_1至button_9。

7.3.2 相關(guān)代碼

?　　當(dāng)數(shù)獨(dú)APP窗口發(fā)生變化時(shí)吧碾，將觸發(fā)SudokuAccessibility中onAccessibilityEvent方法凰盔。在此方法中，通過(guò)控件id獲取數(shù)獨(dú)面板與1-9數(shù)字按鈕控件的信息滤港，然后計(jì)算并將相關(guān)信息使用SharedPreferences保存至本地廊蜒。

?　　關(guān)鍵代碼：

(SudokuAccessibility.java)

public class SudokuAccessibility extends AccessibilityService {
    //記錄1-9數(shù)字按鈕的中心點(diǎn)坐標(biāo)
    private List<Point> mTypeNumberPointList = new ArrayList<>(9);
    //記錄數(shù)獨(dú)面板中81個(gè)小格子的中心點(diǎn)坐標(biāo)
    private List<List<Point>> mShuDuPanelPointList = new ArrayList<>(9);
    ...
    @Override
    public void onAccessibilityEvent(AccessibilityEvent event) {
        Log.d(TAG, "onAccessibilityEvent: " + event.toString());

        if (!mInitDataFlag) {
            initViewData(event);
        }
    }

    private void initViewData(AccessibilityEvent event) {
        AccessibilityNodeInfo root = getRootInActiveWindow();
        if (root == null) return;

        //初始化等待區(qū)數(shù)字1-9的中心位置
        for (int i = 0; i < 9; i++) {
            String id = String.format("com.easybrain.sudoku.android:id/button_%d", i + 1);
            List<AccessibilityNodeInfo> nodeInfos = root.findAccessibilityNodeInfosByViewId(id);
            if (!nodeInfos.isEmpty()) {
                Rect rect = new Rect();
                nodeInfos.get(0).getBoundsInScreen(rect);
                Point point = new Point(rect.centerX(), rect.centerY());
                mTypeNumberPointList.add(point);
            }
        }

        //生成數(shù)獨(dú)面板81個(gè)格子的中心位置
        String id = String.format("com.easybrain.sudoku.android:id/sudoku_board");
        List<AccessibilityNodeInfo> nodeInfos = root.findAccessibilityNodeInfosByViewId(id);
        if (!nodeInfos.isEmpty()) {
            Rect rect = new Rect();
            nodeInfos.get(0).getBoundsInScreen(rect);

            int step = (rect.bottom - rect.top) / 9;
            //計(jì)算81格中，第一個(gè)格子的中心點(diǎn)
            int x = rect.left + step / 2;
            int y = rect.top + step / 2;

            /*保存數(shù)獨(dú)面板的左上角頂點(diǎn)溅漾、高度信息山叮，便于截取數(shù)獨(dú)面板時(shí)使用。*/
            saveSudokuBroadInfo(rect);

            for (int i = 0; i < 9; i++) {
                List<Point> points = new ArrayList<>(9);
                for (int j = 0; j < 9; j++) {
                    Point point = new Point(x + step * j, y + step * i);
                    points.add(point);
                }
                mShuDuPanelPointList.add(points);
            }
        }

        if (mShuDuPanelPointList.size() == 9 && mTypeNumberPointList.size() == 9) {
            mInitDataFlag = true;
            Toast.makeText(this, "數(shù)獨(dú)信息獲取成功!", Toast.LENGTH_SHORT).show();
        }
    }
    //保存數(shù)獨(dú)面板的坐標(biāo)信息添履，便于截取數(shù)獨(dú)面板圖片時(shí)使用
    private void saveSudokuBroadInfo(Rect rect) {
        SPUtils.put(SudokuAccessibility.this, SudokuXUtils.SP_RECT_LEFT, rect.left - 5);
        SPUtils.put(SudokuAccessibility.this, SudokuXUtils.SP_RECT_TOP, rect.top - 5);
        SPUtils.put(SudokuAccessibility.this, SudokuXUtils.SP_RECT_HEIGH, rect.bottom - rect.top + 10);
    }
    ...
}

?　　【注】這部分代碼主要在SudokuAccessibility類(lèi)中實(shí)現(xiàn)屁倔。

8 如何實(shí)現(xiàn)無(wú)Root權(quán)限截屏

?　　Android在5.0之后提供了官方的截屏API，現(xiàn)在的手機(jī)Android版本普遍在Android 5.0以上暮胧，該方法還是有比較高的適用性锐借。此時(shí)问麸，再也不需要通過(guò)root權(quán)限調(diào)用adb指令，或者使用輔助服務(wù)模擬截屏按鍵實(shí)現(xiàn)截屏了钞翔。

?　　由于節(jié)省文章篇幅严卖，具體的實(shí)現(xiàn)讀者可參考筆者的另一篇文章《Android 5.0 無(wú)Root權(quán)限實(shí)現(xiàn)截屏》。

9 如何提取數(shù)獨(dú)九宮格中的數(shù)字

?　　要求解數(shù)獨(dú)布轿，需要進(jìn)行計(jì)算哮笆，圖片格式的數(shù)字肯定是不行的，所以必須把圖片上的數(shù)字轉(zhuǎn)換為實(shí)實(shí)在在的數(shù)字才能進(jìn)行計(jì)算汰扭。要得到實(shí)實(shí)在在的數(shù)字稠肘，我們需要做的是對(duì)圖片上的數(shù)字進(jìn)行提取和識(shí)別。

?　　本小節(jié)主要介紹數(shù)獨(dú)圖片中數(shù)字的提嚷苊（即獲取數(shù)字圖像區(qū)域）项阴，該功能本項(xiàng)目使用openCV實(shí)現(xiàn)。

9.1 介紹

OpenCV于1999年由Intel建立笆包，如今由Willow Garage提供支持环揽。OpenCV是一個(gè)基于BSD許可（開(kāi)源）發(fā)行的跨平臺(tái)計(jì)算機(jī)視覺(jué)庫(kù)，可以運(yùn)行在Linux色查、Windows和Mac OS操作系統(tǒng)上薯演。它輕量級(jí)而且高效——由一系列 C 函數(shù)和少量 C++ 類(lèi)構(gòu)成撞芍，同時(shí)提供了Python秧了、Ruby、MATLAB等語(yǔ)言的接口序无，實(shí)現(xiàn)了圖像處理和計(jì)算機(jī)視覺(jué)方面的很多通用算法验毡。

9.2 openCV的配置

?　　在Android中配置openCV其實(shí)也非常簡(jiǎn)單，可見(jiàn)筆者的另一篇文章《在Android Studio中配置openCV項(xiàng)目》帝嗡，在此不再贅述晶通。

9.3 openCV的使用

?　　提取圖片內(nèi)容的輪廓，我們可以使用openCV視覺(jué)庫(kù)Imgproc類(lèi)中findContours()方法來(lái)實(shí)現(xiàn)哟玷。在對(duì)圖片進(jìn)行輪廓識(shí)別時(shí)狮辽，先需要對(duì)圖片進(jìn)行灰度化與二值化處理，這里先簡(jiǎn)單介紹這兩個(gè)操作巢寡。

9.3.1 灰度化

?　　我們從findContours的參數(shù)要求中得知喉脖，第一個(gè)參數(shù)是圖像二值化后的Mat對(duì)象。在生成二值化的圖像前抑月，我們需要對(duì)圖像進(jìn)行灰度化處理树叽。

灰度化，在RGB模型中谦絮，如果R=G=B時(shí)题诵，則彩色表示一種灰度顏色洁仗，其中R=G=B的值叫灰度值，因此性锭，灰度圖像每個(gè)像素只需一個(gè)字節(jié)存放灰度值（又稱(chēng)強(qiáng)度值赠潦、亮度值），灰度范圍為0-255草冈。一般有分量法 最大值法平均值法加權(quán)平均法四種方法對(duì)彩色圖像進(jìn)行灰度化祭椰。

?　　使用openCV中對(duì)圖片灰度化的實(shí)現(xiàn)很簡(jiǎn)單，只需要一行代碼即可：Imgproc.cvtColor(rgbMat, grayMat, Imgproc.COLOR_RGB2GRAY);

灰度化

cvtColor方法的定義：

cvtColor(Mat src, Mat dst, int code)

9.3.2 二值化

?　　接下來(lái)要做圖像的二值化方淤，簡(jiǎn)單來(lái)說(shuō)，就是把圖片變成只有黑色和白色的像素點(diǎn)蹄殃。

圖像的二值化携茂，就是將圖像上的像素點(diǎn)的灰度值設(shè)置為0或255，也就是將整個(gè)圖像呈現(xiàn)出明顯的只有黑和白的視覺(jué)效果诅岩。

?　　同樣地讳苦，圖像二值化的實(shí)現(xiàn)也只需一行代碼：Imgproc.threshold(grayMat, binaryMat, 100, 255, Imgproc.THRESH_BINARY);

threshold方法的定義：

threshold(Mat src, Mat dst, double thresh, double maxval, int type)

?　　在本項(xiàng)目中，thresh取值為100腊状，type為THRESH_BINARY诱咏，即像素值超過(guò)100的都置為255，否則置為0寿酌。注意這里的thresh值的選用：可以剛好將九宮格內(nèi)的縱橫線去掉胰苏，在做數(shù)字提取的時(shí)候?qū)?huì)少判斷一層父輪廓。

二值化

9.3.3 輪廓識(shí)別

?　　終于，我們要對(duì)圖像進(jìn)行輪廓識(shí)別硕并。這一步將使用openCV視覺(jué)庫(kù)位于Imgproc類(lèi)中findContours()方法實(shí)現(xiàn)法焰。該方法定義如下：

findContours(Mat image, List<MatOfPoint> contours, Mat hierarchy, int mode, int method)

??由于數(shù)獨(dú)面板的輪廓包括各種的嵌套關(guān)系牙言，此時(shí)mode參數(shù)選用RETR_TREE 酸钦。另外我們只需要數(shù)字輪廓的矩陣信息即可，所以method參數(shù)選用CHAIN_APPROX_SIMPLE咱枉。

9.3.4 關(guān)于層次（Hierarchy）的理解

?　　檢測(cè)輪廓的時(shí)候卑硫，有時(shí)候可能會(huì)出現(xiàn)其中一個(gè)輪廓包含了另外一個(gè)輪廓徒恋，比如同心圓。這里我們認(rèn)為外側(cè)輪廓為父輪廓欢伏，內(nèi)側(cè)被包含的為子輪廓入挣。同一級(jí)別的又有前一個(gè)輪廓和后一個(gè)輪廓∠跖。總的來(lái)說(shuō)径筏，hierarchy表達(dá)的是不同輪廓之間的聯(lián)系。

?　　舉一個(gè)例子障陶，下圖產(chǎn)生了7個(gè)輪廓信息：

?　　數(shù)組List<MatOfPoint> contours中共有7個(gè)輪廓信息滋恬，每個(gè)輪廓的id則為數(shù)組下標(biāo)i。如id為0的輪廓a是整個(gè)圖片的最外層輪廓抱究、黑色邊框共有里外兩個(gè)id為1和2的輪廓b和c夷恍、數(shù)字1,3各自有一個(gè)輪廓f和g、數(shù)字4有兩個(gè)輪廓d和e媳维，其中輪廓c是輪廓efg的父輪廓酿雪。

??第i個(gè)輪廓的前、后侄刽、子指黎、父輪廓會(huì)保存在hierarchy[i][0], hiearchy[i][1], hiearchy[i][2]和 hiearchy[i][3]中。要找到上圖中的4州丹、3醋安、1三個(gè)數(shù)字輪廓，相對(duì)于要找到以輪廓c為父輪廓的contour[i]即可墓毒。

?　　我們處理數(shù)獨(dú)面板圖片時(shí)吓揪，也是一樣的思路，只是數(shù)獨(dú)面板比上圖再多了一層父輪廓所计。為了理清楚輪廓關(guān)系柠辞，我們在調(diào)用findContours方法生成輪廓信息后，用log打印出所有的輪廓信息主胧，先找到9個(gè)九宮格的輪廓id叭首，存放在數(shù)組tmp中。再遍歷contours數(shù)組踪栋，所有以tmp的元素為父輪廓的輪廓焙格，則是我們最終需要的數(shù)字輪廓。如下圖所示夷都，可以看到父輪廓id為1的都是九宮格的輪廓（紅框所示）眷唉，以九宮格輪廓為父輪廓的都是數(shù)字輪廓（綠框所示）。

?　　最后，我們得到的輪廓信息可以通過(guò)Imgproc類(lèi)的rectangle(Mat img, Point pt1, Point pt2, Scalar color)方法將輪廓繪制到圖像中冬阳，以便調(diào)試蛤虐。

輪廓識(shí)別

?　　使用openCV識(shí)別數(shù)字的部分已經(jīng)完成，在這就不貼代碼了摩泪，有需要的讀者可參考項(xiàng)目中代碼笆焰。

??【注】這部分的代碼主要在SudokuXOrc類(lèi)中實(shí)現(xiàn)。

10 如何實(shí)現(xiàn)數(shù)字識(shí)別

?　　上一小節(jié)见坑，我們已經(jīng)可以獲得數(shù)獨(dú)圖片中的數(shù)字輪廓信息嚷掠，可以產(chǎn)生數(shù)獨(dú)數(shù)字圖片。在本小節(jié)荞驴，將介紹如何識(shí)別圖像中的文字不皆。本項(xiàng)目使用tess-two ORC引擎實(shí)現(xiàn)圖像識(shí)別。

10.1 介紹

Tesseract是Ray Smith于1985到1995年間在惠普布里斯托實(shí)驗(yàn)室開(kāi)發(fā)的一個(gè)OCR引擎熊楼，曾經(jīng)在1995 UNLV精確度測(cè)試中名列前茅霹娄。但1996年后基本停止了開(kāi)發(fā)。2006年鲫骗，Google邀請(qǐng)Smith加盟犬耻，重啟該項(xiàng)目。目前項(xiàng)目的許可證是Apache 2.0执泰。該項(xiàng)目目前支持Windows枕磁、Linux和Mac OS等主流平臺(tái)。但作為一個(gè)引擎术吝，它只提供命令行工具计济。 現(xiàn)階段的Tesseract由Google負(fù)責(zé)維護(hù)，是最好的開(kāi)源OCR Engine之一排苍，并且支持中文沦寂。

tess-two是Tesseract在Android平臺(tái)上的移植。

10.2 tess-two的配置

?　　tess-two在Android Studio中的配置非常簡(jiǎn)單淘衙，只需要以下三步即可传藏。

10.2.1 在Android Studio中的引入依賴(lài)

dependencies {
    implementation 'com.rmtheis:tess-two:9.0.0'
}

10.2.2 下載tessdata語(yǔ)言數(shù)據(jù)文件

?　　數(shù)據(jù)文件 下載鏈接。我們只需要識(shí)別數(shù)字幔翰，因此下載英文的語(yǔ)言數(shù)據(jù)eng.traineddata就可以了漩氨。

語(yǔ)言數(shù)據(jù)

10.2.3 配置tessdata語(yǔ)言數(shù)據(jù)文件

??這一步很重要！在手機(jī)的SD卡根目錄創(chuàng)建一個(gè)名為tessdata的文件夾(必須是根目錄和tessdata命名)遗增，將下載好的語(yǔ)言數(shù)據(jù)文件eng.traineddata放入其中。

??【注】在實(shí)際的應(yīng)用款青，我們不可能要求用戶(hù)手動(dòng)完成這步操作做修。一般的做法是將eng.traineddata文件存放在android項(xiàng)目的asset目錄中，在應(yīng)用啟動(dòng)時(shí)將其復(fù)制到SD卡中。

10.3 tess-two使用

??本項(xiàng)目將tess-two的使用封裝在TessTwoHelper類(lèi)中饰及，代碼十分簡(jiǎn)單蔗坯。使用前，需要調(diào)用TessBaseAPI的init方法進(jìn)行初始化燎含，第一個(gè)參數(shù)傳入手機(jī)的根目錄宾濒，第二個(gè)參數(shù)傳入語(yǔ)言數(shù)據(jù)包名字。我們可以根據(jù)識(shí)別的文字圖片類(lèi)型設(shè)置白名單和黑名單屏箍，以便提高準(zhǔn)確率绘梦。因?yàn)樽R(shí)別的是一個(gè)單獨(dú)的文本塊，所以調(diào)用setPageSegMode方法將模式設(shè)為PSM_SINGLE_BLOCK_VERT_TEXT赴魁。

???相關(guān)代碼：

(TessTwoHelper.java)

public class TessTwoHelper {

    public static final String DATA_DIR_PATH = "/storage/emulated/0/tessdata";
    public static final String DATA_NAME = "eng.traineddata";
    private TessBaseAPI tessBaseAPI = new TessBaseAPI();

    public void init() {
        tessBaseAPI.init("/storage/emulated/0/", "eng");
        tessBaseAPI.setDebug(true);
        tessBaseAPI.setVariable(TessBaseAPI.VAR_CHAR_WHITELIST, "123456789");
        tessBaseAPI.setVariable(TessBaseAPI.VAR_CHAR_BLACKLIST, "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0!@#$%^&*()_+=-[]}{;:'\"\\|~`,./<>?");
        tessBaseAPI.setPageSegMode(TessBaseAPI.PageSegMode.PSM_SINGLE_BLOCK_VERT_TEXT);
    }

    public String getText(Bitmap bitmap) {
        tessBaseAPI.setImage(bitmap);
        return tessBaseAPI.getUTF8Text();
    }
}

??在SudokuXOrc類(lèi)的getOriginShuDuArray方法中卸奉，使用數(shù)字輪廓坐標(biāo)截取數(shù)字圖片，使用tess-two識(shí)別颖御，實(shí)測(cè)識(shí)別準(zhǔn)確率還是相當(dāng)高榄棵。

(SudokuXOrc.java)

public class SudokuXOrc {
    ...
    public int[][] getOriginShuDuArray(Bitmap bitmapSource) {
        ...
        //根據(jù)輪廓截取數(shù)字圖片，進(jìn)行文字識(shí)別
        Bitmap tmpBitmap = Bitmap.createBitmap(bitmapSource, rect.x, rect.y, rect.width, rect.height);
        int number = mTessTwoHelper.getText(tmpBitmap).charAt(0) - '0';
        saveBitmap(tmpBitmap, "bitmap" + rect.x + "" + rect.y + "tag:" + number);
        ...
    }
    ...
}

?　　【注】這部分代碼主要在TessTwoHelper類(lèi)實(shí)現(xiàn)潘拱。

11 如何編寫(xiě)代碼求解數(shù)獨(dú)

?　　數(shù)獨(dú)求解算法疹鳄，聽(tīng)起來(lái)感覺(jué)很高大上的東西，但筆者認(rèn)為這可能是本文中最簡(jiǎn)單的內(nèi)容芦岂，畢竟可以利用機(jī)器算力來(lái)解決瘪弓。（づ￣3￣）づ╭?～

?　　筆者還沒(méi)去了解過(guò)高效的數(shù)獨(dú)求解算法，在這里用了一個(gè)相對(duì)容易理解的思路：

?　　步驟一：按先行后列的順序遍歷二維數(shù)組盔腔，找到第一個(gè)空白格子杠茬，根據(jù)游戲規(guī)則，找到該格子所有可能填入的數(shù)字的序列（下文稱(chēng)作數(shù)字序列）弛随。如此重復(fù)填充空白格子瓢喉。

?　　步驟二：若步驟一中填入數(shù)字有誤，必將導(dǎo)致未來(lái)有一空白格子（假設(shè)格子A）找不到任何可以填入的數(shù)字舀透。此時(shí)游標(biāo)回退到上一個(gè)數(shù)字序列不為空的格子（假設(shè)格子B）中栓票，并將格子B到A的所有填入的數(shù)字清除（置0）。

?　　步驟三：在格子B中填入數(shù)字序列的下一個(gè)數(shù)字愕够。如此重復(fù)走贪，直到填滿(mǎn)全部空格。

?　　筆者實(shí)現(xiàn)該算法惑芭，用到棧stack和鍵值對(duì)Pair<key,value>坠狡。其中棧stack用于按序儲(chǔ)存多余的數(shù)字序列，鍵值對(duì)Pair<key,value>中的key表示某個(gè)格子的坐標(biāo)遂跟，value表示該格子的多余數(shù)字序列逃沿。

??實(shí)測(cè)該算法的速度還是可以的婴渡，筆者使用小米5的手機(jī)測(cè)試，解一個(gè)專(zhuān)家級(jí)數(shù)獨(dú)（包括圖像處理）平均只需1秒凯亮。

?　　關(guān)鍵代碼：

(SudokuXAnalyse.java)

public class SudokuXAnalyse {
    /*數(shù)獨(dú)二維數(shù)組*/
    private int[][] mShuDu = new int[9][9];
    /*二維數(shù)組边臼，標(biāo)記某個(gè)格子是否被修改過(guò)，初始化全為false假消，填入數(shù)字后置為true*/
    private boolean[][] mShuDuFlag = new boolean[9][9];

    public SudokuXAnalyse(int[][] shuDu) {...}

    /*得到某個(gè)格子可能填入的數(shù)字序列*/
    private  ArrayList<Integer> getPendingQueue(int x, int y)  {...}

    /*把坐標(biāo)（beginX,beginY）到（endX,endY）全部被修改過(guò)的格子置為0柠并，在回溯時(shí)使用*/
    private void clear(int beginX, int beginY, int endX, int endY) {...}
    
    /*數(shù)獨(dú)求解，無(wú)解時(shí)返回null*/
    public int[][] getAns() throws InterruptedException {
        int i = 0, j = 0;
        boolean needContinue = true;
        /*棧中存放鍵值對(duì)富拗，key為某格子的下標(biāo)臼予，value為該格子可能填入數(shù)字的序列*/
        Stack<Pair<String, ArrayList<Integer>>> stack = new Stack<>();

        while (needContinue) {
            needContinue = false;
            while (i < 9) {
                while (j < 9) {
                    if (mShuDu[i][j] == 0) {
                        needContinue = true;
                        ArrayList<Integer> arrayList = getPendingQueue(i, j);
                        //當(dāng)某格子沒(méi)有可以填入的數(shù)字時(shí)，回溯
                        if (arrayList.size() == 0) {
                            //椕较浚空瘟栖，無(wú)解
                            if (stack.size() == 0) {
                                return null;
                            }
                            int tmpI = stack.peek().first.charAt(0) - '0';
                            int tmpJ = stack.peek().first.charAt(1) - '0';

                            clear(tmpI, tmpJ, i, j);

                            //重新更新當(dāng)前下標(biāo)
                            i = tmpI; 
                            j = tmpJ;

                            //填入某格子的下一個(gè)可能數(shù)字
                            mShuDu[i][j] = stack.peek().second.remove(0);

                            if (stack.peek().second.size() == 0) {
                                stack.pop();
                            }
                        } else {
                            mShuDu[i][j] = arrayList.remove(0);
                            mShuDuFlag[i][j] = true;
                            //保存某格子可能填入的其余數(shù)字
                            if (!arrayList.isEmpty()) {
                                String key = i + "" + j;
                                Pair<String, ArrayList<Integer>> pair = new Pair<>(key, arrayList);
                                stack.push(pair);
                            }
                        }
                    }
                    j++;
                }
                i++;
                j = 0;
            }
        }
        return mShuDu;
    }
}

?　　【注】數(shù)獨(dú)APP提供的題目都是有解的，若測(cè)試發(fā)現(xiàn)提示無(wú)解谅阿，極有可能是使用tess-two做圖像轉(zhuǎn)文字時(shí)識(shí)別錯(cuò)誤半哟，導(dǎo)致產(chǎn)生的數(shù)獨(dú)無(wú)解。一般而言签餐，使用tess-two來(lái)識(shí)別印刷體數(shù)字的準(zhǔn)確率非常高寓涨，若識(shí)別出錯(cuò)，很可能是TessBaseAPI的setPageSegMode方法傳入的模式不正確氯檐。
?　　【注】這部分的代碼主要在類(lèi)SudokuXAnalyse中戒良。

12 如何實(shí)現(xiàn)模擬屏幕點(diǎn)擊操作

?　　在求出數(shù)獨(dú)的答案之后，需要實(shí)現(xiàn)數(shù)字的填入冠摄，人工填入數(shù)字太慢糯崎，比較炫酷的是APP自動(dòng)填入。此時(shí)用到模擬屏幕的點(diǎn)擊河泳，可以在幾秒內(nèi)填好數(shù)十個(gè)數(shù)字沃呢。在Android程序中模擬屏幕的點(diǎn)擊操作，比較可行的有兩種方式：

?　　1. 獲取root權(quán)限拆挥，執(zhí)行adb指令薄霜，如adb shell input tap 250 250,表示在點(diǎn)擊坐標(biāo)(250,250)的位置。

?　　2. 使用AccessibilityService進(jìn)行模擬點(diǎn)擊纸兔。

?　　筆者最初是采用在APP中調(diào)用adb指令的方法惰瓜，但實(shí)測(cè)該方法中指令運(yùn)行速度非常慢，因?yàn)樵跀?shù)獨(dú)輸入一個(gè)數(shù)字汉矿，需要執(zhí)行兩條指令（原因可見(jiàn)備注）崎坊，完成整個(gè)操作最快需要1分鐘左右，跟人工輸入沒(méi)任何區(qū)別洲拇。這樣當(dāng)然是不行的流强，因此轉(zhuǎn)向使用AccessibilityService實(shí)現(xiàn)模擬點(diǎn)擊痹届。

?　　使用AccessibilityService時(shí)呻待，根據(jù)目標(biāo)控件的id打月，通過(guò)findAccessibilityNodeInfosByViewId方法得到對(duì)應(yīng)的AccessibilityNodeInfo對(duì)象，再用performAction(AccessibilityNodeInfo.ACTION_CLICK)方法可以完成一次模擬點(diǎn)擊蚕捉，但筆者在實(shí)踐中發(fā)現(xiàn)奏篙，該方法失效了！迫淹！筆者認(rèn)為很可能是該數(shù)獨(dú)APP的按鈕點(diǎn)擊處理采用onTouch而非onClick的方法秘通，進(jìn)而屏蔽了該輔助功能的模擬點(diǎn)擊。

?　　最后看到一篇文章中提到AccessibilityService新增了dispatchGesture方法敛熬，可發(fā)送手勢(shì)肺稀。首先這個(gè)方法是7.0之后加入的，所以最小版本改為24应民。執(zhí)行的手勢(shì)類(lèi)為GestureDescription话原，需要一段path路徑來(lái)實(shí)例化，若path路徑是一個(gè)點(diǎn)诲锹，則模擬點(diǎn)擊事件繁仁。

?　　我們?cè)谇懊嬉呀?jīng)使用AccessibilityService獲得了數(shù)獨(dú)面板、1-9數(shù)字按鈕的位置信息归园，只需要進(jìn)一步計(jì)算出數(shù)獨(dú)面板每個(gè)格子以及1-9數(shù)字按鈕的中心點(diǎn)黄虱，再使用dispatchGesture方法，則可以完成模擬點(diǎn)擊操作庸诱。

?　　通過(guò)dispatchGesture完成模擬點(diǎn)擊捻浦，關(guān)鍵代碼：

(SudokuAccessibility.java)

public void dispatchGestureView(int startTime, int x, int y) {
    Point position = new Point(x, y);
    GestureDescription.Builder builder = new GestureDescription.Builder();
    Path p = new Path();
    p.moveTo(position.x, position.y);
    /**
     * StrokeDescription參數(shù)：
     * path：筆畫(huà)路徑
     * startTime：時(shí)間 (以毫秒為單位)，從手勢(shì)開(kāi)始到開(kāi)始筆劃的時(shí)間桥爽，非負(fù)數(shù)
     * duration：筆劃經(jīng)過(guò)路徑的持續(xù)時(shí)間(以毫秒為單位)朱灿，非負(fù)數(shù)*/
    builder.addStroke(new GestureDescription.StrokeDescription(p, startTime, 1));
    dispatchGesture(builder.build(), null, null);
}

?　　計(jì)算數(shù)獨(dú)面板81個(gè)小格子以及1-9按鈕的中心坐標(biāo)：

(SudokuAccessibility.java)

private void initViewData(AccessibilityEvent event) {
    ...
    //獲取1-9數(shù)字按鈕的中心位置
    for (int i = 0; i < 9; i++) {
        String id = String.format("com.easybrain.sudoku.android:id/button_%d", i + 1);
        List<AccessibilityNodeInfo> nodeInfos = root.findAccessibilityNodeInfosByViewId(id);
        if (!nodeInfos.isEmpty()) {
            //獲取控件的矩形區(qū)域
            Rect rect = new Rect();
            nodeInfos.get(0).getBoundsInScreen(rect);
            Point point = new Point(rect.centerX(), rect.centerY());
            mTypeNumberPointList.add(point);
        }
    }
    //獲取數(shù)獨(dú)面板81個(gè)格子的中心位置
    String id = String.format("com.easybrain.sudoku.android:id/sudoku_board");
    List<AccessibilityNodeInfo> nodeInfos = root.findAccessibilityNodeInfosByViewId(id);
    if (!nodeInfos.isEmpty()) {
        //獲取控件的矩形區(qū)域
        Rect rect = new Rect();
        nodeInfos.get(0).getBoundsInScreen(rect);
        int step = (rect.bottom - rect.top) / 9;
        //計(jì)算81格中，第一個(gè)格子的中心點(diǎn)
        int x = rect.left + step / 2;
        int y = rect.top + step / 2;
        /*保存數(shù)獨(dú)面板的左上角頂點(diǎn)聚谁、高度信息母剥，便于截圖分析數(shù)獨(dú)面板數(shù)字時(shí)使用。*/
        saveSudokuBroadInfo(rect);
        for (int i = 0; i < 9; i++) {
            List<Point> points = new ArrayList<>(9);
            for (int j = 0; j < 9; j++) {
                Point point = new Point(x + step * j, y + step * i);
                points.add(point);
            }
            mShuDuPanelPointList.add(points);
        }
    }
    ...
}

?　　通過(guò)Handler模擬延時(shí)點(diǎn)擊形导，關(guān)鍵代碼：

(SudokuAccessibility.java)
...
private Handler mHandler = new Handler(new Handler.Callback() {
    int i = 0;
    /**
     * 設(shè)置tag可以實(shí)現(xiàn)輪流按下數(shù)獨(dú)面板和選擇區(qū)按鈕环疼，
     * 同時(shí)配合變量@param fillingFlag，實(shí)現(xiàn)避免某些區(qū)域點(diǎn)擊失效的情況朵耕。
     * */
    boolean tag = true;
    @Override
    public boolean handleMessage(Message msg) {
        if (i < mLocTextInfos.size()) {
            LocTextInfo locTextInfo = mLocTextInfos.get(i);
            if (tag == true) {
                Point numberPoint = mShuDuPanelPointList.get(locTextInfo.locX).get(locTextInfo.locY);
                dispatchGestureView(0, numberPoint.x, numberPoint.y);
            } else {
                Point typeNumberPoint = mTypeNumberPointList.get(locTextInfo.number - 1);
                dispatchGestureView(0, typeNumberPoint.x, typeNumberPoint.y);
                i++;
            }
            tag = !tag;
            mHandler.sendEmptyMessageDelayed(0, 25);
        } else {
            i = 0;
            tag = true;
            mHandler.removeCallbacksAndMessages(null);
            mLocalBroadcastManager.sendBroadcast(new Intent(SudokuXUtils.ACTION_FILLING_COMPLETE));
        }
        return false;
    }
});
...

?　　最后需要在xml配置文件中添加允許執(zhí)行手勢(shì)：

(accessibility.xml)
...
android:canPerformGestures="true"
...

?　　【注】首先需要注意炫隶，把一個(gè)數(shù)字填入數(shù)獨(dú)面板的小格子中，需要執(zhí)行兩次點(diǎn)擊操作：第一次點(diǎn)擊1-9的數(shù)字按鈕阎曹，選中要填入的數(shù)字伪阶，第二次點(diǎn)擊數(shù)獨(dú)面板對(duì)應(yīng)的小格子煞檩，填入數(shù)字。（該數(shù)獨(dú)APP的默認(rèn)規(guī)則）

?　　【注】這部分代碼主要在SudokuAccessibility類(lèi)中實(shí)現(xiàn)栅贴。

13 后記

??該軟件還有很多有待改進(jìn)的地方斟湃，比如：

??1. 直接集成openCV和tess-two包，沒(méi)有做優(yōu)化處理檐薯，導(dǎo)致軟件安裝包有100多M凝赛。

??2. 只能針對(duì)特定的APP完成求解、填入操作坛缕，后序可加入用戶(hù)框選數(shù)獨(dú)面板墓猎，軟件自動(dòng)識(shí)別當(dāng)前應(yīng)用的功能，使能夠填入任何的數(shù)獨(dú)APP赚楚。

??本文只做拋磚引玉之用毙沾，若有讀者改進(jìn)了上述缺點(diǎn)請(qǐng)告知...

14 參考文章

OpenCV玩九宮格數(shù)獨(dú)（一）——九宮格圖片中提取數(shù)字

Android學(xué)習(xí)八---OpenCV JAVA API

Android7.0 AccessibilityService新增gesturedescription使用詳解

AccessibilityService從入門(mén)到出軌