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

    

    

    

    随着移动技术的快速发展，“小程序”越来越受人们的喜爱。“数独”就是这样一款廣受人们喜爱的益智类小游戏，它既可以愉悦心情、陶冶情操，又可以促进用脑、开发智力。但有时也会碰到“烦心事”，那就是有些题目花费了很长时间也解不了，着实让人有点儿闹心。

    想起前几年很火的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—），杭州市基础教育研究室，高级教师，硕士，主要研究中小学信息技术教育。