Python-自动完成标准数独的小脚本

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

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

一、反编译

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

分析页面布局

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

二、用python解决

总体的方法思路很简单：

识别初始化的数独 -> 解数独 -> 将解填入至游戏中

1、解数独

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

http://yshblog.com/blog/74

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

2、识别数独

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

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

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

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

附：psm参数的说明，可以使用命令tesseract —help-psm查看

这样通过识别9x9宫格的图片后，我们就自然而然的转化为我们需要的data数组。另外，解法中最后提供的类型是numpy的ndarray类型。

3、填充数字

将数独的81个数据与对应的81个位置联系起来，通过for循环依次填进去。

三、实验

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

最终效果（测试脚本可以通过私聊或者我的git-gist获取）：