记数独X--Android openCV识别数独并自动求解填充APP开发过程

作者：AchillesL
若转载文章，请标明文章出处

1 序

​　　数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。

数独

​　　最近一段时间经常做数独题，并思考了一下能不能编写一个APP，可以自动求解数独、最后将结果填入该APP中。

.............................................摸鱼的开发过程，此处省略10N行字.....................................

​　　最终写一个APP：数独X。可以针对笔者常用的数独APP(本文的实现都基于该APP)，实现数独的识别、求解、并把答案自动填入。专家级别的平均1秒完成求解(包括图像数字提取，识别过程)，8s完成全部操作。

​　　本文将简单介绍相关功能的实现。文章有点长，有需要的童鞋可善用浏览器的页面搜索功能。数独X的使用效果，如下图：

效果图，加载会有点慢

2 下载链接

  数独 APP链接：https://pan.baidu.com/s/1b67LlZcr7K3d3ZTxgwUobg
  数独X APP链接：https://pan.baidu.com/s/1xJMTxO1dMza_mjHGrdiyHQ
  数独X 源代码链接：https://github.com/AchillesL/jianshu-sudokuX

  ［注］数独X对手机要求：Android 7.0 或以上。

3 本文内容

  • 实现思路介绍
  • 项目结构介绍
  • 如何创建悬浮窗
  • 如何获取第三方应用中的控件信息
  • 如何无Root实现跨应用截屏
  • 如何提取数独九宫格中的数字
  • 如何实现数字识别
  • 如何编写代码求解数独
  • 如何实现模拟屏幕点击
  • 后记
  • 参考文章

4 实现思路介绍

​   步骤一：我们需要获得数独APP中的九宫格数字。由于数独App是第三方应用，数独信息当然是无法直接获取的，笔者的思路是打开数独界面后调用截屏，再通过图片处理提取九宫格的数字。同时，为了避免截屏时遮挡应用，数独X的工作窗口应该使用悬浮窗形式。

​  步骤二：截屏后，我们需要进一步截取数独面板图片，以便数字提取用。我们可以写死面板坐标、宽高来提取截图中的面板。在这里，当然有更好的方法，就是通过辅助功能AccessibilityService获得数独应用的数独面板坐标信息。

​  步骤三：在获得数独面板的图片后，使用openCV框架提取数字的轮廓，生成数字图片，再调用TessTwo框架将图片转为数字，并生成原始数独二维数组。

​  步骤四：数独求解，生成答案，并生成需要填充的数字序列。

  步骤五：最后通过辅助功能AccessibilityService类的相关方法，模拟屏幕点击，输入填充数独的数字。

流程图

5 项目结构介绍

  项目主要包含文件如下图：

项目主要文件
类名 功能
FileStorageHelper 该类封装了把asset目录下复制到SD卡的相关方法
LocTextInfo 该类记录数独某格子的行列号，及对应的数字
MainActivity 该类实现应用的启动窗口，主要用于申请权限、截图等操作
ScreenShotHelper 该类为截图助手类，封装了获取截屏图片的一些方法
SPUtils 该类封装了SharedPreferences的一些操作
SudokuAccessibility 该类继承AccessibilityService，实现第三方应用的控件获取、屏幕模拟点击
SudokuXAnalyse 该类用于数独求解，输入原始的数独二维数组，返回求解后的数独二维数组
SudokuXOrc 该类用于数独识别，输入数独图片Bitmap，返回原始的数独二维数组
SudokuXService 该类用于实现悬浮窗，实现应用的工作窗口，实现数独X的主要逻辑
SudokuXUtils 该类存放了广播的Action，屏幕大小等常量信息
TessTwoHelper 该类封装了TessBaseApi的相关方法，实现文字识别
时序图

6 如何创建悬浮窗

​　　Android的界面绘制，都是通过WindowMananger的服务来实现的。要实现一个能够在自身应用界面外的悬浮窗，我们就要利用WindowManager类。同时，为了让悬浮窗与Activity脱离，让应用处于后台时悬浮窗仍然可以正常运行，这里使用Service来启动悬浮窗并做为其背后逻辑支撑。

6.1 申请权限

​　　在创建悬浮窗前，必须先申请权限，代码十分简单：

（MainActivity.java）

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

6.2 在service中创建悬浮窗

（SudokuXService.java）

...
private void initView() {
    //注意Android O版本与其他系统的差异
    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);
    ...
}
...

​　　最后在首页启动SudokuXService即可，讲述Android悬浮窗的文章很多，读者可自行查阅，在此不再赘述。
　　【注】这部分的代码主要在SudokuXService.java中实现。

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

​　　本项目使用Android的辅助服务AccessibilityService来获取数独APP的控件信息。

7.1 介绍

​ AccessibilityService设计初衷在于帮助残障用户使用android设备和应用，在后台运行，可以监听用户界面的一些状态转换，例如页面切换、焦点改变、通知、Toast等，并在触发AccessibilityEvents时由系统接收回调。后来被开发者另辟蹊径，用于一些插件开发，比如微信红包助手，还有一些需要监听第三方应用的插件。

​ 我们可以把AccessibilityService理解为——『按键精灵』。相信很多开发者都玩过PC上的这款软件，他的作用，就是将你一次操作的整个记录，录制下来，然后就可以根据这个记录，重复的执行这些操作，例如：先点击某个输入框，再输入XXXX，再输入验证码，最后点击某按钮，这些操作如果需要重复执行，那么显然是一套机械的步骤，那么通过按键精灵，记录下这些操作后，直接通过脚本就可以完成这些操作。其实AccessibilityService跟这个是一样的，我们记录的，实际上就是我们的操作步骤，或者称之为『脚本』，那么系统在监控整个手机的各种AccessibilityService事件时，就会根据我们的逻辑来判断该使用哪一个脚本。

​ 因此，我们完全可以抽象出一个基类AccessibilityService，并抽象出一些脚本的事件，例如，根据Text查找对应的View、点击某个View、滑动、返回等等。

7.2 配置

​　　首先，要使用AccessibilityService实际上非常简单，一般来说，只需要以下三步即可。

7.2.1 继承系统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() {
    }
}

​　　强制重新的有两个方法：onAccessibilityEvent和onInterrupt。重点关注onAccessibilityEvent方法，在该方法中，我们可以接收所监听的事件。

7.2.2 新建配置文件

​　　在资源目录res下新建xml文件夹，新建accessibility.xml文件，写入：

<?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"/>

​　　里面有一些比较简单的配置。本项目要辅助的是数独应用，在xml的android:packageNames处指定辅助应用的包名，即com.easybrain.sudoku.android。当没有指定时，默认辅助所有的应用，建议大家在使用时，指定需要监听的包名（你可以通过|来进行分隔），而不是所有的包名。typeAllMask是设置响应事件的类型，feedbackGeneric是设置回馈给用户的方式，有语音播出和振动。

7.2.3 注册

​　　最后，在AndroidMainifest中注册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>

​　　完成以上步骤后，一个辅助服务就可以使用了，AccessibilityService具有很高的系统权限，所以，系统不会让App直接设置是否启用，需要用户进入设置-辅助功能中去手动启用，这样在一定程度上，保护了用户数据的安全。

  这里不再赘述AccessibilityService的基本用法，有需要的读者可参考相关文章，例如：AccessibilityService从入门到出轨。

7.3 使用

​　　本节介绍如何数独APP的控件信息以及代码编写。

7.3.1 通过Layout Inspector工具，获取数独APP的控件信息

​　　使用AccessibilityService拿到数独APP的控件信息，我们必须先知道对应的控件id。这一步，我们可以使用Android Studio的Layout Inspector工具来完成。

  先启动数独APP，在Android Studio中，点击Tools->Layout Inspector，选中包名：com.easybrain.sudoku.android，即可以看到一下画面：

​　　可见数独面板id为sudoku_board，1-9的数字按钮id分别是button_1至button_9。

7.3.2 相关代码

​　　当数独APP窗口发生变化时，将触发SudokuAccessibility中onAccessibilityEvent方法。在此方法中，通过控件id获取数独面板与1-9数字按钮控件的信息，然后计算并将相关信息使用SharedPreferences保存至本地。

​　　关键代码：

(SudokuAccessibility.java)

public class SudokuAccessibility extends AccessibilityService {
    //记录1-9数字按钮的中心点坐标
    private List<Point> mTypeNumberPointList = new ArrayList<>(9);
    //记录数独面板中81个小格子的中心点坐标
    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;

        //初始化等待区数字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);
            }
        }

        //生成数独面板81个格子的中心位置
        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;
            //计算81格中，第一个格子的中心点
            int x = rect.left + step / 2;
            int y = rect.top + step / 2;

            /*保存数独面板的左上角顶点、高度信息，便于截取数独面板时使用。*/
            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, "数独信息获取成功!", Toast.LENGTH_SHORT).show();
        }
    }
    //保存数独面板的坐标信息，便于截取数独面板图片时使用
    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类中实现。

8 如何实现无Root权限截屏

​　　Android在5.0之后提供了官方的截屏API，现在的手机Android版本普遍在Android 5.0以上，该方法还是有比较高的适用性。此时，再也不需要通过root权限调用adb指令，或者使用辅助服务模拟截屏按键实现截屏了。

​　　由于节省文章篇幅，具体的实现读者可参考笔者的另一篇文章《Android 5.0 无Root权限实现截屏》。

9 如何提取数独九宫格中的数字

​　　要求解数独，需要进行计算，图片格式的数字肯定是不行的，所以必须把图片上的数字转换为实实在在的数字才能进行计算。要得到实实在在的数字，我们需要做的是对图片上的数字进行提取和识别。

​　　本小节主要介绍数独图片中数字的提取（即获取数字图像区域），该功能本项目使用openCV实现。

9.1 介绍

OpenCV于1999年由Intel建立，如今由Willow Garage提供支持。OpenCV是一个基于BSD许可（开源）发行的跨平台计算机视觉库，可以运行在Linux、Windows和Mac OS操作系统上。它轻量级而且高效——由一系列 C 函数和少量 C++ 类构成，同时提供了Python、Ruby、MATLAB等语言的接口，实现了图像处理和计算机视觉方面的很多通用算法。

9.2 openCV的配置

​　　在Android中配置openCV其实也非常简单，可见笔者的另一篇文章《在Android Studio中配置openCV项目》，在此不再赘述。

9.3 openCV的使用

​　　提取图片内容的轮廓，我们可以使用openCV视觉库Imgproc类中findContours()方法来实现。在对图片进行轮廓识别时，先需要对图片进行灰度化与二值化处理，这里先简单介绍这两个操作。

9.3.1 灰度化

​　　我们从findContours的参数要求中得知，第一个参数是图像二值化后的Mat对象。在生成二值化的图像前，我们需要对图像进行灰度化处理。

灰度化，在RGB模型中，如果R=G=B时，则彩色表示一种灰度颜色，其中R=G=B的值叫灰度值，因此，灰度图像每个像素只需一个字节存放灰度值（又称强度值、亮度值），灰度范围为0-255。一般有分量法 最大值法平均值法加权平均法四种方法对彩色图像进行灰度化。

​　　使用openCV中对图片灰度化的实现很简单，只需要一行代码即可：Imgproc.cvtColor(rgbMat, grayMat, Imgproc.COLOR_RGB2GRAY);

灰度化

cvtColor方法的定义：

cvtColor(Mat src, Mat dst, int code)

参数名 含义
Mat src 原Mat对象
Mat dst 目标Mat对象
int code 本项目使用的是Imgproc.COLOR_RGB2GRAY，即RGB图像转灰度图像

9.3.2 二值化

​　　接下来要做图像的二值化，简单来说，就是把图片变成只有黑色和白色的像素点。

图像的二值化，就是将图像上的像素点的灰度值设置为0或255，也就是将整个图像呈现出明显的只有黑和白的视觉效果。

​　　同样地，图像二值化的实现也只需一行代码：Imgproc.threshold(grayMat, binaryMat, 100, 255, Imgproc.THRESH_BINARY);

threshold方法的定义：

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

参数名 含义
Mat src 原Mat对象
Mat dst 目标Mat对象
double thresh 阈值的具体值
double maxval type取THRESH_BINARY 或THRESH_BINARY_INV阈值类型时的最大值
int type THRESH_BINARY：像素值大于阈值时，取Maxval,也就是第四个参数，否则置为0。
THRESH_BINARY_INV：当前点值大于阈值时，设置为0，否则设置为Maxval。
THRESH_TRUNC: 当前点值大于阈值时，设置为阈值，否则不改变。
THRESH_TOZERO: 当前点值大于阈值时，不改变，否则设置为0。
THRESH_TOZERO_INV: 当前点值大于阈值时，设置为0，否则不改变。

​　　在本项目中，thresh取值为100，type为THRESH_BINARY，即像素值超过100的都置为255，否则置为0。注意这里的thresh值的选用：可以刚好将九宫格内的纵横线去掉，在做数字提取的时候将会少判断一层父轮廓。

二值化

9.3.3 轮廓识别

​　　终于，我们要对图像进行轮廓识别。这一步将使用openCV视觉库位于Imgproc类中findContours()方法实现。该方法定义如下：

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

参数名 含义
Mat image 单通道图像矩阵，一般是经过Canny、拉普拉斯等边缘检测算子处理过的二值图像。
List<MatOfPoint> contours MatOfPoint是保存Point的Mat，继承自Mat。
contours表示检测到的轮廓，轮廓是由一系列的点构成，存储在java 的list中，每个list的元素是MatOfPoint。
Mat hierarchy 包含着图像的拓扑信息，有和contours相同数量的元素。
对于每个contours[i],对应的hierarchy[i][0], hiearchy[i][1], hiearchy[i][2]和 hiearchy[i][3]分别被设置同一层次的下一个，上一个，第一个孩子和父亲的轮廓。 如果contour [i]不存在对应的contours,那么相应的hierarchy[i] 就被设置成-1。
int mode contour的估计方式（4种）:
RETR_EXTERNAL ：只检测最外围的轮廓。
RETR_LIST ：检测所有轮廓，不建立等级关系，彼此独立。
RETR_CCOMP ：检测所有轮廓，但所有轮廓都只建立两个等级关系 。
RETR_TREE ：检测所有轮廓，并且所有轮廓建立一个树结构，层次完整。（本项目使用该参数）
RETR_FLOODFILL ：洪水填充法。
int method contour的检索方式（4种）：
CHAIN_APPROX_NONE：保存物体边界上所有连续的轮廓点。
CHAIN_APPROX_SIMPLE：压缩水平方向，垂直方向，对角线方向的元素，只保留该方向的终点坐标，例如一个矩形轮廓只需4个点来保存轮廓信息。（本项目使用该参数)
CV_CHAIN_APPROX_TC89_L1：使用Teh-Chin 链近似算法。
CV_CHAIN_APPROX_TC89_KCOS：使用Teh-Chin 链近似算法。

  由于数独面板的轮廓包括各种的嵌套关系，此时mode参数选用RETR_TREE 。另外我们只需要数字轮廓的矩阵信息即可，所以method参数选用CHAIN_APPROX_SIMPLE。

9.3.4 关于层次（Hierarchy）的理解

​　　检测轮廓的时候，有时候可能会出现其中一个轮廓包含了另外一个轮廓，比如同心圆。这里我们认为外侧轮廓为父轮廓，内侧被包含的为子轮廓。同一级别的又有前一个轮廓和后一个轮廓。总的来说，hierarchy表达的是不同轮廓之间的联系。

​　　举一个例子，下图产生了7个轮廓信息：

​　　数组List<MatOfPoint> contours中共有7个轮廓信息，每个轮廓的id则为数组下标i。如id为0的轮廓a是整个图片的最外层轮廓、黑色边框共有里外两个id为1和2的轮廓b和c、数字1,3各自有一个轮廓f和g、数字4有两个轮廓d和e，其中轮廓c是轮廓efg的父轮廓。

  第i个轮廓的前、后、子、父轮廓会保存在hierarchy[i][0], hiearchy[i][1], hiearchy[i][2]和 hiearchy[i][3]中。要找到上图中的4、3、1三个数字轮廓，相对于要找到以轮廓c为父轮廓的contour[i]即可。

​　　我们处理数独面板图片时，也是一样的思路，只是数独面板比上图再多了一层父轮廓。为了理清楚轮廓关系，我们在调用findContours方法生成轮廓信息后，用log打印出所有的轮廓信息，先找到9个九宫格的轮廓id，存放在数组tmp中。再遍历contours数组，所有以tmp的元素为父轮廓的轮廓，则是我们最终需要的数字轮廓。如下图所示，可以看到父轮廓id为1的都是九宫格的轮廓（红框所示），以九宫格轮廓为父轮廓的都是数字轮廓（绿框所示）。

​　　最后，我们得到的轮廓信息可以通过Imgproc类的rectangle(Mat img, Point pt1, Point pt2, Scalar color)方法将轮廓绘制到图像中，以便调试。

轮廓识别

​　　使用openCV识别数字的部分已经完成，在这就不贴代码了，有需要的读者可参考项目中代码。

  【注】这部分的代码主要在SudokuXOrc类中实现。

10 如何实现数字识别

​　　上一小节，我们已经可以获得数独图片中的数字轮廓信息，可以产生数独数字图片。在本小节，将介绍如何识别图像中的文字。本项目使用tess-two ORC引擎实现图像识别。

10.1 介绍

Tesseract是Ray Smith于1985到1995年间在惠普布里斯托实验室开发的一个OCR引擎，曾经在1995 UNLV精确度测试中名列前茅。但1996年后基本停止了开发。2006年，Google邀请Smith加盟，重启该项目。目前项目的许可证是Apache 2.0。该项目目前支持Windows、Linux和Mac OS等主流平台。但作为一个引擎，它只提供命令行工具。 现阶段的Tesseract由Google负责维护，是最好的开源OCR Engine之一，并且支持中文。

tess-two是Tesseract在Android平台上的移植。

10.2 tess-two的配置

​　　tess-two在Android Studio中的配置非常简单，只需要以下三步即可。

10.2.1 在Android Studio中的引入依赖

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

10.2.2 下载tessdata语言数据文件

​　　数据文件 下载链接。我们只需要识别数字，因此下载英文的语言数据eng.traineddata就可以了。

语言数据

10.2.3 配置tessdata语言数据文件

  这一步很重要！在手机的SD卡根目录创建一个名为tessdata的文件夹(必须是根目录和tessdata命名)，将下载好的语言数据文件eng.traineddata放入其中。

  【注】在实际的应用，我们不可能要求用户手动完成这步操作。一般的做法是将eng.traineddata文件存放在android项目的asset目录中，在应用启动时将其复制到SD卡中。

10.3 tess-two使用

  本项目将tess-two的使用封装在TessTwoHelper类中，代码十分简单。使用前，需要调用TessBaseAPI的init方法进行初始化，第一个参数传入手机的根目录，第二个参数传入语言数据包名字。我们可以根据识别的文字图片类型设置白名单和黑名单，以便提高准确率。因为识别的是一个单独的文本块，所以调用setPageSegMode方法将模式设为PSM_SINGLE_BLOCK_VERT_TEXT。

​  相关代码：

(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类的getOriginShuDuArray方法中，使用数字轮廓坐标截取数字图片，使用tess-two识别，实测识别准确率还是相当高。

(SudokuXOrc.java)

public class SudokuXOrc {
    ...
    public int[][] getOriginShuDuArray(Bitmap bitmapSource) {
        ...
        //根据轮廓截取数字图片，进行文字识别
        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类实现。

11 如何编写代码求解数独

​　　数独求解算法，听起来感觉很高大上的东西，但笔者认为这可能是本文中最简单的内容，毕竟可以利用机器算力来解决。（づ￣3￣）づ╭❤～

​　　笔者还没去了解过高效的数独求解算法，在这里用了一个相对容易理解的思路：

​　　步骤一：按先行后列的顺序遍历二维数组，找到第一个空白格子，根据游戏规则，找到该格子所有可能填入的数字的序列（下文称作数字序列）。如此重复填充空白格子。

​　　步骤二：若步骤一中填入数字有误，必将导致未来有一空白格子（假设格子A）找不到任何可以填入的数字。此时游标回退到上一个数字序列不为空的格子（假设格子B）中，并将格子B到A的所有填入的数字清除（置0）。

​　　步骤三：在格子B中填入数字序列的下一个数字。如此重复，直到填满全部空格。

​　　笔者实现该算法，用到栈stack和键值对Pair<key,value>。其中栈stack用于按序储存多余的数字序列，键值对Pair<key,value>中的key表示某个格子的坐标，value表示该格子的多余数字序列。

  实测该算法的速度还是可以的，笔者使用小米5的手机测试，解一个专家级数独（包括图像处理）平均只需1秒。

​　　关键代码：

(SudokuXAnalyse.java)

public class SudokuXAnalyse {
    /*数独二维数组*/
    private int[][] mShuDu = new int[9][9];
    /*二维数组，标记某个格子是否被修改过，初始化全为false，填入数字后置为true*/
    private boolean[][] mShuDuFlag = new boolean[9][9];

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

    /*得到某个格子可能填入的数字序列*/
    private  ArrayList<Integer> getPendingQueue(int x, int y)  {...}

    /*把坐标（beginX,beginY）到（endX,endY）全部被修改过的格子置为0，在回溯时使用*/
    private void clear(int beginX, int beginY, int endX, int endY) {...}
    
    /*数独求解，无解时返回null*/
    public int[][] getAns() throws InterruptedException {
        int i = 0, j = 0;
        boolean needContinue = true;
        /*栈中存放键值对，key为某格子的下标，value为该格子可能填入数字的序列*/
        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);
                        //当某格子没有可以填入的数字时，回溯
                        if (arrayList.size() == 0) {
                            //栈空，无解
                            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);

                            //重新更新当前下标
                            i = tmpI; 
                            j = tmpJ;

                            //填入某格子的下一个可能数字
                            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;
                            //保存某格子可能填入的其余数字
                            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;
    }
}

​　　【注】数独APP提供的题目都是有解的，若测试发现提示无解，极有可能是使用tess-two做图像转文字时识别错误，导致产生的数独无解。一般而言，使用tess-two来识别印刷体数字的准确率非常高，若识别出错，很可能是TessBaseAPI的setPageSegMode方法传入的模式不正确。
​　　【注】这部分的代码主要在类SudokuXAnalyse中。

12 如何实现模拟屏幕点击操作

​　　在求出数独的答案之后，需要实现数字的填入，人工填入数字太慢，比较炫酷的是APP自动填入。此时用到模拟屏幕的点击，可以在几秒内填好数十个数字。在Android程序中模拟屏幕的点击操作，比较可行的有两种方式：

​　　1. 获取root权限，执行adb指令，如adb shell input tap 250 250,表示在点击坐标(250,250)的位置。

​　　2. 使用AccessibilityService进行模拟点击。

​　　笔者最初是采用在APP中调用adb指令的方法，但实测该方法中指令运行速度非常慢，因为在数独输入一个数字，需要执行两条指令（原因可见备注），完成整个操作最快需要1分钟左右，跟人工输入没任何区别。这样当然是不行的，因此转向使用AccessibilityService实现模拟点击。

​　　使用AccessibilityService时，根据目标控件的id，通过findAccessibilityNodeInfosByViewId方法得到对应的AccessibilityNodeInfo对象，再用performAction(AccessibilityNodeInfo.ACTION_CLICK)方法可以完成一次模拟点击，但笔者在实践中发现，该方法失效了！！笔者认为很可能是该数独APP的按钮点击处理采用onTouch而非onClick的方法，进而屏蔽了该辅助功能的模拟点击。

​　　最后看到一篇文章中提到AccessibilityService新增了dispatchGesture方法，可发送手势。首先这个方法是7.0之后加入的，所以最小版本改为24。执行的手势类为GestureDescription，需要一段path路径来实例化，若path路径是一个点，则模拟点击事件。

​　　我们在前面已经使用AccessibilityService获得了数独面板、1-9数字按钮的位置信息，只需要进一步计算出数独面板每个格子以及1-9数字按钮的中心点，再使用dispatchGesture方法，则可以完成模拟点击操作。

​　　通过dispatchGesture完成模拟点击，关键代码：

(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参数：
     * path：笔画路径
     * startTime：时间 (以毫秒为单位)，从手势开始到开始笔划的时间，非负数
     * duration：笔划经过路径的持续时间(以毫秒为单位)，非负数*/
    builder.addStroke(new GestureDescription.StrokeDescription(p, startTime, 1));
    dispatchGesture(builder.build(), null, null);
}

​　　计算数独面板81个小格子以及1-9按钮的中心坐标：

(SudokuAccessibility.java)

private void initViewData(AccessibilityEvent event) {
    ...
    //获取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);
        }
    }
    //获取数独面板81个格子的中心位置
    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;
        //计算81格中，第一个格子的中心点
        int x = rect.left + step / 2;
        int y = rect.top + step / 2;
        /*保存数独面板的左上角顶点、高度信息，便于截图分析数独面板数字时使用。*/
        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);
        }
    }
    ...
}

​　　通过Handler模拟延时点击，关键代码：

(SudokuAccessibility.java)
...
private Handler mHandler = new Handler(new Handler.Callback() {
    int i = 0;
    /**
     * 设置tag可以实现轮流按下数独面板和选择区按钮，
     * 同时配合变量@param fillingFlag，实现避免某些区域点击失效的情况。
     * */
    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配置文件中添加允许执行手势：

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

​　　【注】首先需要注意，把一个数字填入数独面板的小格子中，需要执行两次点击操作：第一次点击1-9的数字按钮，选中要填入的数字，第二次点击数独面板对应的小格子，填入数字。（该数独APP的默认规则）

​　　【注】这部分代码主要在SudokuAccessibility类中实现。

13 后记

  该软件还有很多有待改进的地方，比如：

  1. 直接集成openCV和tess-two包，没有做优化处理，导致软件安装包有100多M。

  2. 只能针对特定的APP完成求解、填入操作，后序可加入用户框选数独面板，软件自动识别当前应用的功能，使能够填入任何的数独APP。

  本文只做抛砖引玉之用，若有读者改进了上述缺点请告知...

14 参考文章

OpenCV玩九宫格数独（一）——九宫格图片中提取数字

Android学习八---OpenCV JAVA API

Android7.0 AccessibilityService新增gesturedescription使用详解

AccessibilityService从入门到出轨

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 206,839评论 6赞 482
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 88,543评论 2赞 382
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 153,116评论 0赞 344
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 55,371评论 1赞 279
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 64,384评论 5赞 374
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,111评论 1赞 285
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,416评论 3赞 400
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,053评论 0赞 259
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,558评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,007评论 2赞 325
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,117评论 1赞 334
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,756评论 4赞 324
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,324评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,315评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,539评论 1赞 262
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,578评论 2赞 355
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,877评论 2赞 345

推荐阅读更多精彩内容