最近从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获取):
领取专属 10元无门槛券
私享最新 技术干货