学习
实践
活动
专区
工具
TVP
写文章

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获取):

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180304G0JXLR00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

关注

腾讯云开发者公众号
10元无门槛代金券
洞察腾讯核心技术
剖析业界实践案例
腾讯云开发者公众号二维码

扫码关注腾讯云开发者

领取腾讯云代金券