“數(shù)獨游戲”算法探析

夏一涵

本文介紹數(shù)獨游戲的一種算法.該算法中多次使用回溯法，初始化時，先隨機生成符合規(guī)則的終盤，然后在此盤中挖空，每次挖空后保證數(shù)獨有唯一解，解不唯一時進行回溯，空格數(shù)等于游戲難度規(guī)定的數(shù)量時停止挖空，形成數(shù)獨初盤，供游戲者填寫.

一、概論

數(shù)獨（Sudoku）是一種運用紙、筆進行演算的邏輯游戲，有四階數(shù)獨、六階數(shù)獨和九宮數(shù)獨.例如圖1就是一個九宮數(shù)獨題，每一行稱為數(shù)獨的行，每一列稱為數(shù)獨的列，每一個小九宮格稱為數(shù)獨的宮.數(shù)獨的基本規(guī)則就是每一行、每一列、每一宮中，1～9這9個數(shù)字都只出現(xiàn)一次.

玩家需要根據(jù)9×9盤面上的已知數(shù)字，通過推理填寫出所有剩余空格的數(shù)字，并滿足每一行、每一列、每一個粗線宮內的數(shù)字均含1～9，不重復.

設計一個數(shù)獨游戲系統(tǒng)，包括以下功能：

（1）難度調節(jié)，包括簡單、中等、困難模式；

（2）游戲功能；

（3）游戲計時功能，記錄當局游戲所需的時間；

（4）游戲成績統(tǒng)計功能，每局游戲結束后自動統(tǒng)計游戲時間作為成績，并在排行榜里顯示最快的10名；

（5）規(guī)則說明等.

圖1 數(shù)獨游戲演示

二、需求分析

1.功能性需求

數(shù)獨游戲需要生成符合數(shù)獨要求的題目.首先，從數(shù)獨題目的正確性考慮，需要一個Sudoku類，其中的create（）方法能生成一個滿足數(shù)獨要求的9×9的數(shù)組，這個數(shù)組就是數(shù)獨的終盤，也是最后生成的數(shù)獨初盤的唯一解；其次，為了驗證數(shù)獨初盤是否只有唯一解，需要一個Solution類，該類的初始化需要輸入一個數(shù)獨初盤，然后通過該類的cal（）方法計算該數(shù)獨的解的數(shù)量，并返回解的數(shù)量；此外還需要一個模塊Problem類，其中的create（）方法能根據(jù)游戲難度在該數(shù)組中隨機挖掉一定數(shù)量的數(shù)，在此期間要保證數(shù)獨的解仍然唯一，然后返回已挖去一些值的數(shù)組和原數(shù)組，作為數(shù)獨的初盤和終盤.挖掉一些數(shù)之后的數(shù)組經(jīng)過簡單的格式整理之后就是一道數(shù)獨的題目了.

界面部分，需要9×9個輸入框，用于顯示題目中的數(shù)字，并讓玩家完成剩下的數(shù)字.1個數(shù)字框，用來顯示游戲時間；一個排行榜，用來顯示各個難度的最快通關時間；六個按鈕，其中三個用于調節(jié)難度，其他三個分別用于“顯示答案”、“再來一局”和“退出”的功能.此外，可以在幫助菜單里獲得游戲的規(guī)則說明.

2.非功能性需求

游戲設計需要注重玩家的游戲體驗，只有最基本的功能是不夠的.顯示界面需要更加人性化.為了便于玩家區(qū)分題目中已有的數(shù)和自己填的數(shù)，需要用不同的顏色區(qū)分.數(shù)獨中，每個3×3的小格也需要包含1～9，不重復，為了便于玩家觀察，也為了游戲界面更加美觀，每個相鄰的3×3的小格需要用不同的背景色加以區(qū)分.

算法方面，生成一個滿足要求的題目并不是一件容易的事.為了保證游戲程序的流暢運行，所有生成題目的算法都需要執(zhí)行得足夠快，從而避免讓玩家感覺到卡頓.雖然可以通過提前生成題目庫的方法減少運算時間，但這會導致游戲文件過大，且題目有限，無法生成足夠多的游戲局面.

3.需求建模

游戲后端算法由3個模塊組成.

（1）Sudoku類用于生成一個如圖2的符合數(shù)獨要求的終盤，這個終盤將被用于生成數(shù)獨初盤：

（2）Solution類用于計算一個數(shù)獨初盤的解的數(shù)量.

（3）Problem類調用Sudoku類和Solution類生成一個數(shù)獨初盤，并確保這個初盤有且僅有一解.

圖2 終盤

三、概要設計

1.Sudoku類設計說明

圖3是該模塊的Sudoku類生成數(shù)獨終盤的流程圖.

如圖3所示，該類使用了回溯法，最終生成一個完整的滿足約束條件的數(shù)獨終盤.

回溯法（探索與回溯法）是一種選優(yōu)搜索法，又稱為試探法，按選優(yōu)條件向前搜索，以達到目標.但當探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標，就退回一步重新選擇，這種“走不通就退回再走”的算法稱為回溯法，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”.

該類先生成9×9個空格.依次往空格中填數(shù)，填入的數(shù)要滿足每一行、每一列、每一宮都不能有重復的數(shù)，并在滿足這3個要求的可選的幾個數(shù)中隨機選擇一個填入.為找到滿足這個要求的數(shù)，需要建立3個集合.集合1是數(shù)獨中所有可填的數(shù)，即｛1，2，3，4，5，6，7，8，9｝；集合2是通過遍歷需要填寫的空所在行、列和宮中的所有數(shù)生成的集合.集合2中的數(shù)不能填寫在目標的單元格中.集合3通過求集合1與集合2之差得到.集合3中的數(shù)就是目標單元格的可選的值.如果某一單元格中沒有任何滿足條件的數(shù)，即集合3為空集，則說明上一個數(shù)填錯了.在上一層可選的幾個數(shù)中排除當前填寫的數(shù)，再次隨機選擇一個數(shù)填入，并繼續(xù)填入之后的空格.如果上一層也沒有任何滿足條件的數(shù)，則再往上一格回溯……以此類推，直至填完所有空格.

回溯法與窮舉法有某些聯(lián)系，它們都是基于試探的.但窮舉法要將一個解的各個部分全部生成后，才檢查是否滿足條件；若不滿足，則直接放棄該完整解，然后嘗試另一個可能的完整解，它并沒有沿著一個可能的完整解的各個部分逐步回退生成解的過程.而對于回溯法，一個解的各個部分是逐步生成的，當發(fā)現(xiàn)當前生成的某部分不滿足約束條件時，就放棄該步所做的工作，退到上一步重新進行嘗試，而不是放棄整個解重來.使用回溯法生成數(shù)獨初盤看似暴力，但隨著填入的格子的數(shù)量的增長，未填的格子的選擇會迅速減少.經(jīng)10000次測試，完成一個9×9的數(shù)獨初盤，平均只需要填入132次，即回溯51次就可以完成.有興趣與耐心的話，完全可以用紙、鉛筆、橡皮按程序的方法手動生成一個數(shù)獨終盤，平均下來只需要擦51個空，就可以填完.

圖3 生成數(shù)獨終盤的流程圖

圖4 計算數(shù)獨解的個數(shù)流程圖

2.Solution類設計說明

Solution類用于計算數(shù)獨解的個數(shù).圖4是Solution類用于計算數(shù)獨解的個數(shù)的流程圖.

如圖4所示，該算法也使用了回溯法，最終可以計算出一個數(shù)獨到底是無解、有唯一解還是有多解.

該算法使用回溯法計算數(shù)獨的解的個數(shù).在空格中按從小到大的順序依次嘗試該空格的可行解，并遞歸地填寫下一個空格.如果某一空格遇到無法填入或所有解都已經(jīng)嘗試過的情況，就回溯至上一層，上一層接著填寫下一個可行解；如果填入的是最后一個空格，就給計數(shù)器加1，再回溯至上一層.當計數(shù)器中的值等于2時，已經(jīng)可以確定該數(shù)獨的解一定不唯一，不必繼續(xù)運算浪費時間，直接退出運行；如果數(shù)獨的解的數(shù)量小于或等于1，程序會在遍歷所有情況后結束，并在計數(shù)器里記錄下解的數(shù)量.

3.Problem類設計說明

該類同樣通過回溯法產(chǎn)生有唯一解的數(shù)獨初盤.它先通過Sudoku類生成一個數(shù)獨終盤，復制生成的初盤并在復制的初盤上不斷挖空，每挖空一次，就調用Solution類計算數(shù)獨解的數(shù)量，看數(shù)獨的解是否仍然唯一.如果某次挖空導致數(shù)獨產(chǎn)生了多解，將該空填回去，并改挖其他空；如果某一狀態(tài)下，無論挖掉哪一格，都會造成數(shù)獨產(chǎn)生多解，則需回溯至上一層，即補回上一次挖掉的空.當挖掉的空的數(shù)量達到預設的值時，停止挖空.此時被挖空的數(shù)獨就是數(shù)獨的初盤，也是數(shù)獨游戲的題目.挖空之前的數(shù)獨初盤，就是題目的答案.

四、程序截圖

圖5 集成測試結果

圖6 顯示答案測試結果