“數獨游戲”算法探析

夏一涵

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

一、概論

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

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

設計一個數獨游戲系統，包括以下功能：

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

（2）游戲功能；

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

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

（5）規則說明等.

圖1 數獨游戲演示

二、需求分析

1.功能性需求

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

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

2.非功能性需求

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

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

3.需求建模

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

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

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

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

圖2 終盤

三、概要設計

1.Sudoku類設計說明

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

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

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

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

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

圖3 生成數獨終盤的流程圖

圖4 計算數獨解的個數流程圖

2.Solution類設計說明

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

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

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

3.Problem類設計說明

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

四、程序截圖

圖5 集成測試結果

圖6 顯示答案測試結果