全自動玩轉小程序“數獨”

隨著移動技術的快速發展，“小程序”越來越受人們的喜愛。“數獨”就是這樣一款廣受人們喜愛的益智類小游戲，它既可以愉悅心情、陶冶情操，又可以促進用腦、開發智力。但有時也會碰到“煩心事”，那就是有些題目花費了很長時間也解不了，著實讓人有點兒鬧心。

想起前幾年很火的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—），杭州市基礎教育研究室，高級教師，碩士，主要研究中小學信息技術教育。