Android-数独世界自动完成标准数独的小脚本

2017-11-09 本文已影响157人 h080294

最近从GP上翻出了之前玩的一款消磨时间的游戏“数独世界” --le.lenovo.sudoku，登陆了GP账号发现已经取得了一些成就，但之前的记录没了，得从新开始玩。懒得费力的去重复完成之前关卡，于是想着怎么能自动填充数独。

抱着试一试的态度，开始了研究。

一、反编译

这款app做了混淆处理，和一些简单的防反编译的措施。正常的工具会失败，得使用强力的反编译工具才行。

1、去广告

广告挺多的，从splash activity、ResumeGameActivity、SudokuActivity等页面都有广告。查看了一下，是使用的Android原生广告，并且程序打印了广告的一些log出来。顺着log可以找到关键地方，然后禁用掉。在AndroidManifest.xml中，也可以看到广告activity的声明，直接删掉就好了。剩下可能残留一些banner广告，暂时留着吧，也给开发者留点收入。

2、分析页面布局

游戏的主页面是SudokuActivity，查看布局发现，棋盘宫格的部分是自定义SuduPuzzleView，使用draw方法绘制出来。因为对Android不了解，没想到什么办法能够识别这块内容。代码中做了混淆，数独的生成的地方也懒得找（不才，没找到），于是就换了种思路，打算用python来解决。

二、用python解决

总体的方法思路如下：
识别初始化的数独 -> 解数独 -> 将解填入至游戏中

1、解数独

最复杂的部分就是解数独了，好的算法会更快。但是算法什么的目前还搞不定，先找一找解数独的相关资料用现成的。发现一个排除候选猜测法，感觉还是很不错的。试验了一些数独，解得很快，具体的算法可以参看他的page。
Python秒解最难数独

大概是这样：先是采用“排除候选法”，确定能确定的数字，中间还额外增加了隐形排除法用来简化问题。当所有的空位都确定后，仍有一些空位有多个值，这时候就采用作者后半部分的猜测算法。先是进行对候选的列表进行评分，根据评分选择候选列表中数字最少的一个来开始猜测-回溯。

2、识别数独

有了解数独的方法，剩下的就好办了，只需给他传一个初始化的data数组就行。有内容的填对应的数字，空内容的则填写0。

初始化数组的方法打算用图片处理：先把当前游戏页面截图，然后分别识别数独9x9宫格的对应内容，之后存入data数组

处理图片用的是PIL库，用到的基本操作都很简单：

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

# 确定剪裁区域
box = (x_start, y_start, x_end, y_end)

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

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

图片识别使用的是tesseract-ocr引擎和pytesseract库。因为游戏中数字的背景很纯（忽略颜色），所以非常容易识别，出错率很小。使用方法也异常的简单。需要注意的就是参数psm，不同情况需要调整psm参数才行。

# PIL 打开已经剪裁好的图片
image = Image.open(img)

# 转换为L -> 灰色图像 方便识别。
# 关于PIL其他8种模式可以翻阅其他资料，这里采用L模式
image = image.convert('L')

# 使用pytesseract模块中的image_to_string方法，将图片识别的数字转为string。
text = pytesseract.image_to_string(image, config='-psm 9')

# string转int，这里偷懒，没做校验。如果出错的就挂了╥﹏╥...
number = int(text)

# 返回数字供调用方
return number

附：psm参数的说明，可以使用命令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宫格的图片后，我们就自然而然的转化为我们需要的data数组。另外，解法中最后提供的类型是numpy的ndarray类型。

3、填充数字

这里更懒，通过最原始的adb点坐标形式。。。将数独的81个数据与对应的81个坐标联系起来，通过for循环依次填进去。因为只在自己的机器上，所以坐标什么的都写死了😄。

# 点击空格坐标定位
adb -s %s shell input tao x y
# 输入当前空格的解
adb -s %s shell input text num_input_from_data

三、实验

过程主要耗费在初始化data数组的时候，因为是线性执行的来保证数组的正确顺序，识别完一个后，才识别下一个。关于顺序问题暂时没想好怎么优化，最后填充解的时候也是一个个填进去的🤣。。。

最终效果，点开查看gif。
（不知道为什么，gif有的时候动，有的时候不动🤣）

四、总结

其实到了后面，目的就已经不是自动解题了。。。而是在这个过程中接触的新东西。

1、了解了数独

之前只是单纯的玩儿，但是没想到解题的过程中运用了很高深的知识，尤其是自己摸索出的一切技巧，居然有一些高大上的对应名词。

2、查看了各种数独的解题算法

思路可以理解，但写不出来。。。

3、接触了Tesseract-OCR引擎

发现图像识别可以运用到自己的工作中，如解决一些需要人工验证的自动化。感觉非常好玩，在试验过程中，有一些识别的不是很好，还能通过训练来提高识别度。

关注获取更多