夏一涵

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

一、概論

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

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

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

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

（2）游戲功能；

（3）游戲計(jì)時(shí)功能，記錄當(dāng)局游戲所需的時(shí)間；

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

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

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

二、需求分析

1.功能性需求

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

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

2.非功能性需求

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

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

3.需求建模

游戲后端算法由3個(gè)模塊組成.

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

（2）Solution類用于計(jì)算一個(gè)數(shù)獨(dú)初盤的解的數(shù)量.

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

圖2 終盤

三、概要設(shè)計(jì)

1.Sudoku類設(shè)計(jì)說明

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

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

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

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

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

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

圖4 計(jì)算數(shù)獨(dú)解的個(gè)數(shù)流程圖

2.Solution類設(shè)計(jì)說明

Solution類用于計(jì)算數(shù)獨(dú)解的個(gè)數(shù).圖4是Solution類用于計(jì)算數(shù)獨(dú)解的個(gè)數(shù)的流程圖.

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

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

3.Problem類設(shè)計(jì)說明

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

四、程序截圖

圖5 集成測(cè)試結(jié)果

圖6 顯示答案測(cè)試結(jié)果