問題描述：

數獨是一種運用紙、筆進行演算的邏輯游戲。玩家需要根據9×9盤面上的已知數字，推理出所有剩余空格的數字，并滿足每一行、每一列、每一個九宮格內的數字均含1-9，不重復

要求：設計算法隨機生成不同難度的數獨游戲，闡述如何評價所生成數獨的難度。

我的分析思路：

對于數獨程序，主要需要解決兩個問題：數獨生成、數獨求解。目前影響比較大，功能比較完善的數獨程序有：Hodoku、Sudoku Explainer。

要實現數獨的生成，就要先理清每一個位置的約束條件，每個位置的數需要滿足四個約束條件：

首先，這個格子里不能有數字，即為空

其次，同一行不能有相同數字

再次，同一列不能有相同數字

最后，同一個九宮格不能有相同數字

用算法的形式把這四個約束條件表現出來，就是數獨的生成。

計算機程序求解數獨，一般采用回溯法，對于任意數獨初盤，好的算法都可以在一秒內得到解。目前，非常有效的算法，是舞蹈鏈(Dancing Links)算法。它實際上也是一種回溯算法，巧妙地運用了雙向十字鏈表的數據結構，用空間換取時間，將數獨求解轉化為一個精確覆蓋問題，用C語言實現的算法，在普通的微機上，能夠在0.1ms左右對任意標準數獨進行求解。

大致步驟：

數獨求解：

首先，要先確定該數獨中空格的數量以及位置，用count記錄空格的數量，用blank數組記錄所有需要填的空格的坐標。

然后，定義一個初始坐標top，使初始坐標top=0，利用一個雙循環求解。

進行第二步后，會有一部分空格需要填的數不唯一，因此需要進行試填，從而使數獨能更好的解決。定義a，b記錄當前top指向的元素作為當前試填空格的坐標，利用循環從1-9依次試填并檢驗當前空格內填入的數字是否可行，我們定義一個變量ok表示當前空格內填入的數字是否可行，當ok=1時表示可行，ok=0時表示不可行。如果填入的數字可行，top+1進行下一個空格的試填，最終求解。

#include <bits/stdc++.h>bool fill(int sd[][9]) {int count = 0; //count用于記錄需要填的空格數量，初始為0int blank[81][2]; //blank數組用于記錄所有需要填的空格的坐標 for(int i = 0;i < 9;i++) for(int j = 0;j < 9;j++) // if(sd[i][j] == 0) // { // 將整個數獨掃描一遍，blank[count][0]=i; // 統計其中的空格數量blank[count][1]=j; // count++; //}int top = 0; //top指向blank數組元素，表示當前待填坐標。初始為0while(top != -1) //最外層循環，每填一個空格，top加1，每回退一步，top減1，如果top==-1，循環結束 {if(top == count) //因為每填完一個空格后top加1，填最后一個空格時top==count-1，填完后top加1即等于count{printf("最終結果為：\n");for(int s = 0;s < 9;s++) //{ //for(int t=0;t<9;t++) //{ // 輸出一個解printf("%d ",sd[s][t]); //} //printf("\n"); //} top--; //如果找到一個解，回退一步，找其他解continue; //只要發生回退，就回到循環開頭測試循環條件top != -1，不會往下執行}int a = blank[top][0]; //如果執行到這里，說明還有空格要填， int b = blank[top][1]; //用a，b記錄下top指向的元素作為當前試填空格的坐標int n = sd[a][b]; //用n記錄當前空格中的數字，這個數字作為試填的“進度”，從這個數字加1往下試填for(n++;n <= 9;n++) //將n加1后，一直循環到9進行試填{int ok = 1; //ok=1標志當前數字可行for(int k = 0;k < 9;k++) //檢測同行，同列，同塊的數字是否有相同的{if(sd[a][k] == n || sd[k][b]== n || sd[(a / 3) * 3 + k / 3][(b/ 3) * 3 + k % 3] == n ) //同行，同列，同塊的數字一起檢測{ok = 0; //如果同行，同列，同塊某一處有相同數字，則ok=0，表示當前數字不可行break; //不再往下檢測，跳出此層循環，繼續試下一個數字}}if(ok) break; //如果ok保持為1，說明當前數字可行（否則肯定會被修改為0），跳出循環，不再往下試}if(n <= 9) // 如果有一個數字可行，n<=9。否則，n=10 {sd[a][b] = n; //將這個數字填入空格中top++; //top加1，處理下一個空格}if(n > 9) //如果試到9都不行的話，循環結束后n的值為10，此時要回退 {sd[a][b] = 0; //回退時先將當前空格中數字改為0，相當于清零top--; //回退1步}}} int main(void) {int sd[9][9] = { // “世界最難數獨”信息 8,0,0,0,0,0,0,0,0,0,0,3,6,0,0,0,0,0,0,7,0,0,9,0,2,0,0,0,5,0,0,0,7,0,0,0,0,0,0,0,4,5,7,0,0,0,0,0,1,0,0,0,3,0,0,0,1,0,0,0,0,6,8,0,0,8,5,0,0,0,1,0,0,9,0,0,0,0,4,0,0,};fill(sd); //調用函數求解return 0; }

總結

以上是生活随笔為你收集整理的数独生成算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。