前言

采用回溯法最經(jīng)典的例子是解決8皇后和迷宮的問題。不習(xí)慣走別人的路，所以下面介紹下用回溯法解數(shù)獨(dú)游戲。寫這個(gè)算法的起因是之前在玩數(shù)獨(dú)游戲時(shí)，遇到了難解的專家模式，就想著寫程序來暴力破解，是不是很無賴，啊哦……

數(shù)獨(dú)介紹

數(shù)獨(dú)（すうどく，Sūdoku），是源自18世紀(jì)瑞士發(fā)明，流傳到美國，再由日本發(fā)揚(yáng)光大的一種數(shù)學(xué)游戲。是一種運(yùn)用紙、筆進(jìn)行演算的邏輯游戲。玩家需要根據(jù)9×9盤面上的已知數(shù)字，推理出所有剩余空格的數(shù)字，并滿足每一行、每一列、每一個(gè)粗線宮內(nèi)的數(shù)字均含1-9，不重復(fù)。

數(shù)獨(dú)盤面是個(gè)九宮，每一宮又分為九個(gè)小格。在這八十一格中給出一定的已知數(shù)字和解題條件，利用邏輯和推理，在其他的空格上填入1-9的數(shù)字。使1-9每個(gè)數(shù)字在每一行、每一列和每一宮中都只出現(xiàn)一次，所以又稱“九宮格”。下圖是一個(gè)完整的數(shù)獨(dú)例子。

下圖是iPad上一個(gè)數(shù)獨(dú)游戲?qū)＜夷Ｊ较碌慕貓D。81個(gè)格子，只給了17個(gè)數(shù)字，確實(shí)有點(diǎn)難度哈。

將上圖轉(zhuǎn)化成程序能夠識別的輸入，{1,1,9}表示第一行第一列的格子數(shù)字是9。

{1,1,9},{1,2,1},{1,8,4},{3,4,5},{3,6,3},{4,1,5},{4,3,6},{4,6,8},{4,7,3},{6,5,1},{6,8,2},{6,9,4},{7,1,8},{7,3,5},{8,3,3},{9,5,4},{9,9,1}

運(yùn)行程序，得出如下解：

9 1 7 | 6 8 2 | 5 4 3
3 5 2 | 1 9 4 | 7 6 8
6 8 4 | 5 7 3 | 1 9 2
~~~~~~~~~~~~
5 9 6 | 4 2 8 | 3 1 7
4 2 1 | 7 3 6 | 9 8 5
7 3 8 | 9 1 5 | 6 2 4
~~~~~~~~~~~~
8 7 5 | 2 6 1 | 4 3 9
1 4 3 | 8 5 9 | 2 7 6
2 6 9 | 3 4 7 | 8 5 1

仔細(xì)觀察不難發(fā)現(xiàn)，每一行、每一列和每一個(gè)九宮格里都是數(shù)字1~9不重復(fù)。這就構(gòu)成了一個(gè)數(shù)獨(dú)的解。也證明，算法通過測試。

算法在解數(shù)獨(dú)題時(shí)，在依次決定每個(gè)格子的數(shù)字時(shí)會(huì)根據(jù)之前已經(jīng)填入的數(shù)字判斷當(dāng)前格子可能填入的數(shù)字，然后選擇其中一個(gè)再去跳到下一個(gè)格子。當(dāng)后面出現(xiàn)無解的情況（一個(gè)格子沒有可填入的數(shù)字），就依次回退到上一個(gè)格子，選取下一個(gè)可能填入的數(shù)字，再依次執(zhí)行下去。直到填入了最后一個(gè)格子，才算完成了數(shù)獨(dú)的一個(gè)解。

回溯法思想

在包含問題的所有解的解空間樹中，按照深度優(yōu)先搜索的策略，從根結(jié)點(diǎn)出發(fā)深度探索解空間樹。當(dāng)探索到某一結(jié)點(diǎn)時(shí)，要先判斷該結(jié)點(diǎn)是否包含問題的解，如果包含，就從該結(jié)點(diǎn)出發(fā)繼續(xù)探索下去，如果該結(jié)點(diǎn)不包含問題的解，則逐層向其祖先結(jié)點(diǎn)回溯。（其實(shí)回溯法就是對隱式圖的深度優(yōu)先搜索算法）。 若用回溯法求問題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有可行的子樹都要已被搜索遍才結(jié)束。 而若使用回溯法求任一個(gè)解時(shí)，只要搜索到問題的一個(gè)解就可以結(jié)束。

核心算法

/*** 填充數(shù)字。實(shí)質(zhì)上是深度遍歷一棵具有9分支的樹，直至遍歷到它的第81層。一定要通過一些判斷剪斷其無用分支，不然該算法的時(shí)間復(fù)雜度相當(dāng)可怕*/ void set_item(Item* items, int position) {if (position==ROW*COLUMN) {printf("第%d個(gè)\n",++count);//填充完最后一個(gè)元素，輸出結(jié)果for (int i = 0; i < COLUMN * ROW; i++) {printf("%3d", items[i].numbers[0]);if ((i + 1) % COLUMN == 0)printf("\n");}printf("\n");return ;}if(items[position].choose!=0){//解數(shù)獨(dú)題時(shí)，當(dāng)前格子已經(jīng)有填入的數(shù)字，就跳到下一個(gè)格子。//如果窮舉出9x9數(shù)獨(dú)所有的解，這個(gè)if判斷不執(zhí)行set_item(items, position + 1);return;}int num =0;//保存當(dāng)前格子可輸入的數(shù)字while (( num= getUseableNum(items, position)) != 0) {//while循環(huán)依次找出當(dāng)前格子，所有可能插入的數(shù)字，再交給下面的if函數(shù)判斷。找不到就結(jié)束while循環(huán)，回到上一個(gè)格子，找到了就遞歸進(jìn)入下一個(gè)格子。//不為0，可輸入//判斷可以填入numif (is_can_set(items, num, position) == 1) {//設(shè)置下一個(gè)格子set_item(items, position + 1);}}//找不到可輸入的數(shù)字，清空當(dāng)前格子填充記錄，回到上一個(gè)格子//若為第一個(gè)格子，找不到填充的數(shù)字就結(jié)束if (position != 0&&items[position].numbers[0]!=0)goback(items, position);}

測試算法代碼段

//定義好17個(gè)已經(jīng)確認(rèn)的格子 Point points[17]={{1,1,9},{1,2,1},{1,8,4},{3,4,5},{3,6,3},{4,1,5},{4,3,6},{4,6,8},{4,7,3},{6,5,1},{6,8,2},{6,9,4},{7,1,8},{7,3,5},{8,3,3},{9,5,4},{9,9,1}}; //初始化數(shù)獨(dú)矩陣 init_matrix(items, COLUMN * ROW); //將17個(gè)格子填入數(shù)獨(dú)矩陣中 init_point(items, points, 17); //從第一個(gè)格子開始遍歷 set_item(items, 0);

附上用到的自定義的函數(shù)，用來決定當(dāng)前格子可填入的數(shù)字的判斷。

/*** 獲取可用的數(shù)字*/ int getUseableNum(Item* items, int position) {for (int i = 1; i < SCALE * SCALE + 1; i++) {if (items[position].used[i] == 0 && items[position].numbers[i] == 0) {//數(shù)字i（1~9）未被使用過且在它所屬的行、列、九宮格里均未出現(xiàn)過就表示可以填入數(shù)字i//有可用的數(shù)字，直接返回return i;}}//沒有可用的數(shù)字，返回0return 0; } /*** 判斷一個(gè)數(shù)字在指定的格子中是否可以插入，返回0表示不能插入，尋找下一個(gè)，*/ int is_can_set(Item* items, int num, int position) {//找到影響的行find_row(row_matrix, position);for (int i = 1; i < SCALE * SCALE + 1; i++) {if(items[row_matrix[i]].numbers[0]==num&&(items[row_matrix[i]].used[num]*items[row_matrix[i]].numbers[num])!=0){items[position].used[num]=1;return 0;}}//找到影響的列find_column(column_matrix, position);for (int i = 1; i < SCALE * SCALE + 1; i++) {if(items[column_matrix[i]].numbers[0]==num&&(items[column_matrix[i]].used[num]*items[column_matrix[i]].numbers[num])!=0){items[position].used[num]=1;return 0;}}//找到影響的塊find_block(block_matrix, position);for (int i = 1; i < SCALE * SCALE + 1; i++) {if(items[block_matrix[i]].numbers[0]==num&&(items[block_matrix[i]].used[num]*items[block_matrix[i]].numbers[num])!=0){items[position].used[num]=1;return 0;}}if (items[position].numbers[0] != 0) {// items[position].used[items[position].numbers[0]]=0;//重置影響到的行changeItemNum(items, row_matrix, items[position].numbers[0],SCALE * SCALE + 1, -1);//重置影響到的列changeItemNum(items, column_matrix, items[position].numbers[0],SCALE * SCALE + 1, -1);//重置影響到的塊changeItemNum(items, block_matrix, items[position].numbers[0],SCALE * SCALE + 1, -1);}items[position].numbers[0] = num;//設(shè)置影響到的行changeItemNum(items, row_matrix, num, SCALE * SCALE + 1, 1);//設(shè)置影響到的列changeItemNum(items, column_matrix, num, SCALE * SCALE + 1, 1);//設(shè)置影響到的塊changeItemNum(items, block_matrix, num, SCALE * SCALE + 1, 1);items[position].used[num] = 1;//能填入return 1; }/*** 清空當(dāng)前格子輸入的信息*/ void goback(Item* items, int position) {//刪除當(dāng)前數(shù)字產(chǎn)生的影響int currentNum = items[position].numbers[0];//重置影響到的行find_row(row_matrix, position);changeItemNum(items, row_matrix, currentNum, SCALE * SCALE + 1, -1);//重置影響到的列find_column(column_matrix, position);changeItemNum(items, column_matrix, currentNum, SCALE * SCALE + 1, -1);//重置影響到的塊find_block(block_matrix, position);changeItemNum(items, block_matrix, currentNum, SCALE * SCALE + 1, -1);items[position].numbers[0]=0;//清空這個(gè)格子里面，使用過的數(shù)字記錄for (int i = 1; i < SCALE * SCALE + 1; i++) {items[position].used[i] = 0;}} /***修改item中的數(shù)字，items表示整個(gè)數(shù)獨(dú)。matrix表示需要修改的下標(biāo)，length表示需要修改個(gè)數(shù)。flag +1表示設(shè)置，-1 表示重置*/ void changeItemNum(Item* items, int* matrix, int num, int length, int flag) {for (int i = 1; i < length; i++) {//需要修改的位置int position = matrix[i];items[position].numbers[num] += flag;} }

小結(jié)

這個(gè)算法，不僅可以用來解數(shù)獨(dú)題，還可以用來遍歷數(shù)獨(dú)所有的終盤，由于9x9的數(shù)獨(dú)，終盤數(shù)量巨大，共6,670,903,752,021,072,936,960（約為6.67×10^21）種組合，程序一直運(yùn)行不完結(jié)果。如果對這個(gè)值沒有概念，請?jiān)囅雽⑺械慕K盤存在txt文本中，只存儲(chǔ)數(shù)字將占用6.07x10^9 TB存儲(chǔ)空間，相信沒有哪臺電腦能夠做到。換句話說，我電腦CPU的主頻是2.4GHz，意思是1秒鐘執(zhí)行2.4x10^12條指令，假設(shè)解出一種終盤需要一條指令（事實(shí)上遠(yuǎn)大于1條），消耗的時(shí)間是88年，本寶寶等不了那么久。慶幸的是4x4 的數(shù)獨(dú)只有288個(gè)終盤，程序還是能夠很快的完美輸出所有解。為什么兩者差別這么大，因?yàn)楦F舉法數(shù)獨(dú)的算法時(shí)間復(fù)雜度是T= n^(n^2).
n = 4時(shí)，T = 4294967296。n = 9時(shí)，T= 1.97Ex10^77。呵呵噠……

總結(jié)

以上是生活随笔為你收集整理的回溯法解数独游戏的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。