“數獨”游戲的算法研究與實現

摘要：“數獨”游戲是一種在全球范圍內流行的數字拼圖游戲。該文通過數據結構分析，提出了一種基于有序回溯的解決數獨游戲的算法并最終通過C語言編程實現了計算機解，實例數據表明程序非常高效。

關鍵詞：數獨；數據結構；算法；回溯

中圖分類號：TP312文獻標識碼：A文章編號：1009-3044(2008)26-1715-03

The Research and Implementation of the Algorithm about Sudoku

LI Pan-rong

(Wuxi Radio TV University，Wuxi 214011， China)

Abstract: Sudoku is one of the most popular puzzle games those are played all over the world. In this paper， based on study of data structure， the author introduced an algorithm which was based on orderly backtracking and was programmed by C language in order to work out the puzzle. The experiments show that this method has high computation efficiency to get the ending. It is an efficient and reliable way.

Key words: sudoku; data structure; algorithm; backtracking

1 引言

“數獨”（Sudoku）起源于瑞士，由十八世紀的瑞士數學家歐拉發明，于1970年代由美國的一家數學邏輯游戲雜志首先發表，當時名為Number Place，于1984 年取名“數獨”，2004年11月12日“數獨”游戲登上《泰晤士報》的版面，很快“數獨”游戲就成為在世界范圍內流行的數字拼圖游戲。如圖1所示，拼圖由一個3x3的九宮格組成，每個格子又分成一個小九宮格，共九九八十一個小格子。游戲規則：游戲開始前會有一些格子上寫好了1-9的數，在剩下的格子里填1-9的數，直到把所有格子填滿，要求，任何一行或一列或者任一個小九宮中沒有相同的數字[1]。

本文就是試圖通過數據結構分析和算法研究，利用計算機程序來快速完成數獨游戲。

2 簡單分析

數獨號稱是數學問題，但幾乎用不上數學運算方法，事實上，它是一個思維方式。由于某個格子填入數據時有可能要對原來已填入的數據進行修正，程序可以考慮使用回溯法解決問題，實踐證明，回溯法解決數獨游戲問題，有著極快的效果。

解決問題的宏觀考慮：

從界面或文本讀取數獨游戲數據；

判斷題目合法性；（即驗證給出數據本身是否符合游戲規則，行、列以及小九宮中不重復地出現數字1－9）；

逐個取得空白處；

有序遞推，若可以填入數字則填入數字，并入棧以便回溯；否則回溯至前面填入數字處重新填數；

直到所有空白處填滿數據；

輸出結果至屏幕和文件。

如此一來需要細化的就是如何進行有序遞推，填入數字或者通過回溯重新填入數字最終得到解，這個也就是本算法的核心，解題的關鍵。

3 數據結構與相關函數

數據結構[2]是計算機存儲、組織數據的方式。通常情況下，精心選擇的數據結構可以帶來更高的運行或者存儲效率的算法。一般認為，一個數據結構是由數據元素依據某種邏輯聯系組織起來的。對數據元素間邏輯關系的描述稱為數據的邏輯結構；數據必須在計算機內存儲，數據的存儲結構是數據結構的實現形式，是其在計算機內的表示。數獨從形式上看是一個方陣，最適合用二維數組來表達。在C語言中，二維數組可以理解為一維數組[3]，為了編程的統一，本算法考慮采用一維數組。

3.1 幾個重要的數組和變量

3.1.1 int sudoku[81]，sp;

sudoku數組的作用為接收游戲的初始值以及保存最終結果。所有的9*9個數字依次被存在數組中，空白處初始化為0，sp用于記錄填數的位置。

3.1.2 int temp_sd[81] ， temp_sp;

temp_sd數組的作用類似于棧，用于存放每個數字上一次填數的位置，初始值無關緊要，可以全部初始化為0；temp_sp用于記錄棧定位置，初值為0。

它們的值可以在程序初始的時候設定[3]：

for(i=0; i<81; i++) {

start_hor[i]= i/9* 9;

start_ver[i]= i% 9;

start_9block[i]= ((i/9)/3)*27+ ((i%9)/3)*3; }

3.1.4 int add_ hor[9]，add_ver[9]，add_9block[9];

三個數組分別用于存放校驗某格時對應行、列、九宮格每個格子與所在行、列、九宮格的第一個格子的偏移量。由圖2和實際經驗可以很輕松地獲知3者的偏移量分別為0，1，…，8；0，9，…，72；0，1，2，9，10，11，18，19，20。這3個數組可以使得任意的行、列、九宮的9個格子變成連續的9個數據，和3.1.3所述數組配合使用，可以使得校驗行、列、九宮格三種情況合一個函數使用。這些數組的值也可以在直接在程序定義并初始化[3]：

int add_hor[9]={0，1，2，3，4，5，6，7，8};

int add_ver[9]={0，9，18，27，36，45，54，63，72};

int add_9block[9]={0，1，2，9，10，11，18，19，20};

3.2 相關函數[4]

3.2.1 int check(int sp)

該函數的作用為檢查sp所在位置的同行、列、九宮格有沒有相同的數字，若有返回1否則返回0。

int check(int sp){

int fg= 0;

if (!fg) fg= check_9(sp， start_hor[sp]， add_hor);

if (!fg) fg= check_9(sp， start_ver[sp]， add_ver);

if (!fg) fg= check_9(sp， start_9block[sp]， add_9block);

return(fg);}

其中check_9(sp， start_hor[sp]， add_hor)表示調用函數check_9，來檢測sp在所在行是否有相同數據， start_hor[sp] 表示sp所在行的第一個格子的位置（下標），add_hor則表示該行9個格子每個格子與第一個格子之間的位置偏移量，即0，1，…，8，與3.1.4所述吻合。

3.2.2 int check_9(int sp， int start， int *addnum)

該函數的作用為檢查sp所在位置，以start為起始位置的連續9個數，有沒有相同的數字，若有返回1否則返回0；其中每個數和第一個數位置之間的偏移量存放在addnum數組中，分別可以是3.1.4所述的行、列、九宮格。

int check_9(int sp， int start， int *addnum) {

int fg= 0， i， sp1;

for(i=0; i<9; i++) {

sp1= start+ addnum[i];

if (sp!=sp1 sudoku[sp]==sudoku[sp1]) fg++;

}

return(fg);}

顯然sp只要和不包含自身在內的另外8個數據作比較，是以取sp1逐次表示9個數，惟有sp!=sp1才作sudoku[sp]和sudoku[sp1]的比較。

3.2.3 int getNextBlank(int sp)

該函數的作用為取得下一個空白的位置，即sudoku[sp]值為0的格子。函數定義如下：

int getNextBlank(int sp) {

do {

sp++;

} while(sp<81 sudoku[sp]>0);

return(sp);}

4 回溯求解“數獨”

具體的實現步驟如下：

1) 按下標sp由小到大的順序逐個獲取空白位置；

2) 對空白位置sp試圖填數，填數的規律為從1－9依次由小到大選擇（有序）；

3) 若找到一個可以填入的數據，將數據填入sudoku[sp]，并將sp入棧push；否則轉5);

4) 獲取下一個空白位置，若有空白位置則轉2)，否則轉6)；

5) 因為check( sp)返回1，找不到合適數據填入該位置，進行回溯，即pop得到上一次填數的位置sp，重新對該位置試圖填數，且為了遞推的高效性，此時可以僅從當前sp存放的數字大1開始試圖填數，轉(3)；

6) 填數結束。

下面給出完整的回溯求解的函數：

int workout (){sp=getNextBlank(-1);

do {sudoku[sp]++;

if(sudoku[sp]>9)

{sudoku[sp]= 0;

sp= pop();}

else

{if(check(sp)==0)

{push(sp);

sp= getNextBlank(sp);}}}

while(sp>=0 sp<81);}

入棧、出棧函數分別為：

int push(int sp)

{temp_sd[temp_sp++]= sp;}

int pop()

{if(temp_sp<0) return(-1);

else return(temp_sd[--temp_sp]);}

5 仿真結果

如圖3所示，對于圖1所示的數獨游戲，經過程序運行，可以迅速得到解。

6 結論

在本算法思想指導下完成的程序經過實驗驗證即使運算高難度的數獨題目，也可以在極短時間之內給出正確的解。這表明雖然用計算機完全模擬人工智能還具有相當的困難，但是針對具體問題，比如數獨，考慮的特定算法編制程序模擬人類來完成搜索過程從而找到解是完全可以實現的。

參考文獻：

[1] 游戲屋.今天，你數獨了嗎？[J].快樂青春，2007，(11):47.

[2] 嚴蔚敏，吳偉民.數據結構[M].2版.北京:清華大學出版社，1993:93-95，43-45，220-221.

[3] 譚浩強.C程序設計[M].3版.北京:清華大學出版社，2005:131-134，229-241.

[4] 劉曉寶.數獨游戲的解題算法[J].電腦編程技巧與維護，2007，(5):64-67.