全自动玩转小程序“数独”

来源 :中国信息技术教育 | 被引量 : 0次 | 上传用户:www_52810_com
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  随着移动技术的快速发展,“小程序”越来越受人们的喜爱。“数独”就是这样一款廣受人们喜爱的益智类小游戏,它既可以愉悦心情、陶冶情操,又可以促进用脑、开发智力。但有时也会碰到“烦心事”,那就是有些题目花费了很长时间也解不了,着实让人有点儿闹心。
  想起前几年很火的Python挑战“跳一跳”小游戏,笔者萌生了一个念头:能不能用Python来玩转“数独”呢?通过摸索与实践,万能的Python没有让人失望,它不但可以破解,还实现了全自动的执行,从读题、运算到填写答案,一气呵成,其间都无需人工干预。
  ● 数独游戏分析
  “数独”一词源于日语,是“SUDOKU”的音译,意为“每个数字只能出现一次”。“数独”起源于中国古代的九宫格。到了18世纪,瑞士盲人数学家欧拉在九宫格的基础上发明了“拉丁方块”,即今天的“数独”的雏形。[1]游戏要求玩家根据9×9盘面上的已知数字, 推理出所有剩余空格的数字,使1~9每个数字在每一行、每一列和每一宫中都只出现一次。微信小游戏数独的部分界面如图1所示。
  在解答这个数独游戏时,玩家需要精确计算,推算出第一个空格应该填写的数字,然后通过点击九宫格中相应的空格,再点击九宫格下方相应的数字,即完成了一个数字的填写,直到将所有的空格全部填满为止。
  ● 解决方案设想
  由于此游戏属于一款移动应用游戏,运行于移动设备如手机上,为了全自动地求解这款数独游戏,设计采用以下几个步骤。
  第一步:截取游戏画面。通过一定的技术手段截取移动端的游戏画面,并保存到计算机端。
  第二步:识别并保存“数独题目”。设计程序,分析游戏画面,识别九宫格中的已知数字,并将数字保存至一个二维列表变量中,其中,空格部分的数字以“.”字符代替,相当于保存了“数独题目”。
  第三步:求解题目。设计算法,得出此数独题目的答案,保存到一个二维列表变量中。
  第四步:回填答案。以一定的技术手段实现控制手机端的点击,即通过计算机按照答案点击移动端的相应区域,完成题目的解答。其解决方案实施流程如下页图2所示。
  ● 程序代码编写
  在确定了解决方案以后,就可以着手程序代码编写工作了,编程语言采用Python3.7。
  模块一:采用ADB工具实现数独画面保存
  ADB即Android Debug Bridge(安卓调试桥),属于Android开发调试工具,用于实现通过实现计算机端与模拟器或者真实移动设备之间的交互。ADB工具功能强大,本应用主要涉及了3种应用:使用其实现通过计算机截取手机的画面并保存为图片文件;将画面图片文件下载至计算机端;用计算机控制手机端的点击。其中用于截取手机端的画面及将图片下载到计算机的核心代码如图3所示。
  模块二:采用OCR文字识别技术实现“数独题目”构建
  从手机截取图片以后,需要获取“数独题目”,这里必须用到OCR文字识别技术。能实现此功能的方法也有很多,本应用选取了百度大脑AI开放平台的“通用文字识别”模块。只需注册成为百度开发者,下载安装基于Python语言的OCR开发包“OCR Python SDK”,即可调用OCR文字识别功能。
  将图片切割成小方块,并分别保存。在进行OCR识别之前,还需要对图片进行切割处理,也即将9×9盘面上的每一个小方块切割以后保存成一个独立的图片文件,共计81个图片文件。此项任务,可以使用Python语言的PIL模块完成。建立自定义函数get_image_xy(),用于图片切割成小方块,并返回小方块的图片文件名。核心代码如图4所示。
  OCR文字识别。在获取小方块的图片文件后,调用OCR文字识别模块对其进行识别。建立自定义函数get_ocr(),用于识别并返回结果。核心代码如图5所示。
  构建“数独题目”。获取到每一个小方块的字符以后,就可以创建“数独题目”了。建立自定义函数get_sodoku_myxy(),用于构建一个二维数组,存储“数独题目”并返回。核心代码如图6所示。
  模块三:采用回溯算法求解数独
  “数独题目”构建完毕,需采用合适的算法求解数独。数独中的数字千变万化,解法也灵活多样,主要有摒除法、余数法、隐含唯一数法、数对法和回溯法。[2]其中回溯法的基本思路是:从第一个空格开始试着填数,从1开始填,如果1不满足横排竖排九宫格无重复的话,就再填入2,以此类推,直到填入一个暂时满足规则的数,中断此格,移动到下一个空格重复这个过程。如果到达某个空格发现已经无数可选了,说明前面某一格填错了,那就返回上一格,从上一格的中断处继续往 9尝试,直到回朔到填错的那一格。有兴趣的读者可自行深入研究。关键语句如图7所示。
  模块四:采用ADB工具回填答案
  自动完成手机端的答案回填工作,整体思路是使用ADB工具模拟手机点击,构建自定义函数click(x,y),实现手机端指定坐标的模拟点击事件。核心代码如图8所示。
  有了数独解答结果,再使用ADB工具,就可以完成自动回填作业了。根据小游戏的操作流程,程序先点击需要回填的小方块,然后再点击下方的数字区域。核心代码如图9所示。
  ● 程序测试优化
  上述四个核心模块设计完毕后,再建立主程序,按照逻辑顺序加以连接,就可以进入测试修改阶段了。首先要用数据线将手机连接上计算机,然后安装相应的ADB驱动程序,接着就可以在计算机端运行编写完毕的主程序。如果一切顺利的话,你就可以愉快地看到,程序运行后,一只无形的“手指”在轻快地点击着手机屏幕。原先需要我们苦思冥想的数独题,被计算机用不了几秒,或几十秒钟,就神奇地解决了。
  《普通高中信息技术课程标准(2017年版)》除了设置选择性必修模块5“人工智能”外,在必修模块1中也专门引入了人工智能模块的学习,要实现“通过人工智能典型案例的剖析,了解智能信息处理的巨大进步和应用潜力,认识人工智能在信息社会中的重要作用”。[3]如何在中小学开展人工智能教育将是我们面临的新问题。本案例结合了人工智能之OCR文字识别技术的应用,综合了图像切割编辑、移动设备控制、算法与程序设计等知识与技能的学习,并且能够激发探究的兴趣,是一个很好的学习案例。
  参考文献:
  [1]顾雏军.顾氏不动点解法——数独题通用解法[J].北华航天工业学院学报,2008,18(01):27-29.
  [2]李祥琴.数独问题求解算法的研究与实现[J].电脑与电信,2017(09):77-79.
  [3]普通高中信息技术课程标准(2017年版)[M].北京:人民教育出版社,2018.
  作者简介:李伟(1970.3—),杭州市基础教育研究室,高级教师,硕士,主要研究中小学信息技术教育。
其他文献
认识与了解儿童的秘密,不是为了控制和调教,而是为了尊重。今年暑假,学校推荐全体教师阅读《儿童的秘密》,在这里我就索性说一说这本书。我觉得,我们永远无法完全了解儿童的
马克思主义作为一个世界性的理论学说大众化是其内在要求和本质属性。从一定意义上说,马克思主义在中国实现大众化的过程就是其与中国传统文化之间进行相互碰撞、交流、融台
在保险业漫长的发展历程中,人寿保险诚信问题逐渐凸显,成为当今我国人寿保险行业的一大威胁。近年来,随着江西省农村人寿保险市场地不断发展,人寿保险已成为农村新型社会保障的一
在智慧校园的建设中,大数据既是模型构建的技术之一,也是重要的数据来源。高校智慧校园的架构采用层次化的体系结构,由智能感知层、网络通信层、云计算层、大数据层、智能应
目的观察锌剂联合叶酸治疗小儿腹泻的临床效果。方法将迁延性腹泻患儿分为对照组、叶酸组、锌剂组和联合治疗组,对照组接受常规治疗,叶酸组和锌剂组在常规治疗的基础上分别加
财务尽职调查是企业并购运作过程中重要的风险防范工具。财务尽职调查的结果直接影响并购的成败。目前企业并购失败的主要原因在于对财务尽职调查的不重视和调查内容的盲目性
20世纪50年代,阿兰·图灵发表了在人工智能发展史上具有里程碑意义的《计算机器与智能》一文,著名的“图灵测试”就源自此文,图灵认为,若测试者无法通过对话的行为区分出
当前我國已經進入了以技術革命和文化革命为中心的社会主义建設新的歷史时期,宣傳贯徹社会主义建設总路綫,为技術革命和文化革命服务,为促進生產力的發展服务,是一切宣傳工