項目位址
https://github.com/si1entic/sudoku
需求分析
-
生成終局
格式：sudoku.exe -c n
1）不重複
2）1<=n<=1000000，能處理非法參數
3）左上角數字固定為（4+4）% 9 + 1 = 9
4）n在1000以内時，要求程式在 60 s 内給出結果
5）輸出生成的數獨終盤至sudoku.txt
-
求解數獨
格式：sudoku.exe -s path
1）從指定檔案讀取，每讀81個數字視作一道數獨題，忽略其他字元
2）要求檔案内的數獨題目是合法的
3）檔案内數獨個數在1000以内時，要求程式在 60 s 内給出結果
4）輸出已讀入數獨的答案至sudoku.txt。若存在未滿81個的數字，在已解出的答案後輸出“存在錯誤格式!”
解題思路
1.數獨生成算法
首先想到的是暴力解決，第一行進行1~9的全排列，之後的行依次循壞填充數字再驗證，不滿足就回退。但這樣有個明顯的問題——效率極低。于是求助度娘，找到了一些算法，但要麼效率不夠，要麼很難滿足首數字固定的要求。最終，在《程式設計之美》P95裡找到了比較适合的算法，加以改進就可以解決該題目了。
下面簡單地一下該算法思路：首先将9x9的表格視作3x3的九宮格，随機生成正中的九宮格（稱其為種子），再通過行列變化填滿其他九宮格，得到了一個合法的數獨終盤。下面來算算通過對這個終盤進行行列變換能得到多少個不同的終盤。
不難發現，在同一九宮格内進行行列變換（藍框列或粉框行互換），所得新數獨仍是合法的。再考慮到固定左上角數字的要求，我們不動第一行第一列，于是有2!×3!×3!×2!×3!×3!=5184種，這就是一個種子變換出的終盤個數。而種子有8!=40320個，顯然不同種子經行列變換得到的終盤是不重複的，故該算法可生成5184×40320=209018880個不重複終盤，滿足1000000的要求。
注：該算法由本人與室友 @李金奇 結合書中内容讨論所得，但可承諾代碼實作均是各自獨立完成。
2.求解數獨算法
查到求解數獨一般采取高效率的DLX算法，于是去這個部落格了解了一下。算法原理比較容易了解，Dancing Links實際上是一種資料結構(交叉十字循環雙向鍊)。由于解決精确覆寫問題的X算法中需要頻繁用到移除、恢複操作，而在這種結構下，進行這兩種操作的效率極高。
接下來就該考慮如何将數獨求解問題轉換為01精确覆寫問題了，這篇部落格對我幫助很大。
行為狀态，列為條件
-
9x9x9行（狀态）
X行：表示數獨i行j列填入數字k(根據X=81*i+9*j+k-1求出)
-
1+9x9x4列 （條件）
第0列為Head元素所占
Y列：
當0＜Y≤81,表示數獨i行j列是否已填入數字(根據Y=9*i+j+1求出)
當81＜Y≤81*2,表示數獨i行是否已填入數字k(根據Y=81+9*i+k求出)
當81*2＜Y≤81*3,表示數獨j列是否已填入數字k(根據Y=81*2+9*j+k求出)
當81*3＜Y≤81*4,表示數獨b塊是否已填入數字k(根據Y=81*3+9*b+k求出)
轉化之後采用DLX算法就行了，關鍵步驟是深度優先周遊-移除-無法滿足則恢複，詳見下面的代碼說明。
注：該算法參考上述部落格較多，尤其是關于使用數組來建構交叉十字循環雙向鍊的部分，但代碼都是我自己實作的，從注釋也看得出來。
設計實作
輸入處理類：根據參數調用下列函數進行相應處理（包括參數合法性判斷）
終盤生成類：種子生成函數、交換組合函數、行列交換函數、轉換輸出函數
數獨求解類：讀入轉換函數、連結建構函數、結點插入函數、移除函數、恢複函數、深度優先周遊函數
輸入處理類中，根據讀取參數選擇一個執行，調用終盤生成類或數獨求解類完成相應功能，并負責輸出到檔案。
終盤生成類中，種子生成函數調用交換組合函數生成各種變換方式，再調用行列交換函數實作交換，最後通過轉換輸出函數傳回字元串結果。
數獨求解類中，先将字元串輸入轉化為二維整型數組，再建構交叉十字循環雙向鍊，接着在dfs遞歸中進行移除、恢複操作，直到擷取可行解。
DLX算法流程圖如下
單元測試
TEST_METHOD(TestMethod1){
FianlMaker fm;
int a[9][9] = {
{ 9,8,7,6,5,4,3,2,1 },
{ 1,2,3,4,5,6,7,8,9 }};
fm.rowExchange(a, 0, 1);
for (int i = 0; i < 9; i++){
Assert::AreEqual(i+1, a[0][i]);
Assert::AreEqual(9-i, a[1][i]);
}
}
TEST_METHOD(TestMethod2){
FianlMaker fm;
int a[9][9] = {
{ 1,2,3,4,5,6,7,8,9 },
{ 1,2,3,4,5,6,7,8,9 },
{ 1,2,3,4,5,6,7,8,9 },
{ 1,2,3,4,5,6,7,8,9 },
{ 1,2,3,4,5,6,7,8,9 },
{ 1,2,3,4,5,6,7,8,9 },
{ 1,2,3,4,5,6,7,8,9 },
{ 1,2,3,4,5,6,7,8,9 },
{ 1,2,3,4,5,6,7,8,9 } };
fm.colExchange(a, 0, 1);
for (int i = 0; i < 9; i++){
Assert::AreEqual(2, a[i][0]);
Assert::AreEqual(1, a[i][1]);
}
}
覆寫率分析
可以看到兩個功能函數的覆寫率都達到了100%（助教給的這個插件似乎無法對單元測試的覆寫率進行統計，隻能統計EXE實際跑起來執行了哪些代碼？）
優化改進
- 多次輸出改為單次一起輸出
- dfs中，發現優先移除元素最少的列，求解效率更高。(單次求解1.2s→0.3s)
- str+=to_string(table[i][j])改為str+=char(table[i][j]+'0')，快了不少 之前使用string儲存所有的輸出字元，性能分析發現string的+=操作占用了程式大部分時間，于是改為char數組儲存，速度提高了很多(39s→8s)。
- 将輸出由ofstream的<<改為FILE*的fputs，速度略微提高。
- 之前使用swap标準函數來交換二維數組，改為自己用temp實作變快了。(6s→3s)
最終，生成100萬個終盤，開啟O2優化後的release編譯性能分析圖如下
消耗最大的函數是make，負責調用其它函數生成終盤。
解1000次芬蘭數學家提出的“最難數獨”
耗時
代碼說明
void FianlMaker::make(int n) {
num = n;
count = 0;
int a[9] = { 1,2,3,4,5,6,7,8,9 };
while (1) {
table[0][4] = table[1][1] = table[2][7] = table[3][3] = table[4][0] = table[5][6] = table[6][5] = table[7][2] = table[8][8] = a[0];
table[0][5] = table[1][2] = table[2][8] = table[3][4] = table[4][1] = table[5][7] = table[6][3] = table[7][0] = table[8][6] = a[1];
table[0][3] = table[1][0] = table[2][6] = table[3][5] = table[4][2] = table[5][8] = table[6][4] = table[7][1] = table[8][7] = a[2];
table[0][7] = table[1][4] = table[2][1] = table[3][6] = table[4][3] = table[5][0] = table[6][8] = table[7][5] = table[8][2] = a[3];
table[0][8] = table[1][5] = table[2][2] = table[3][7] = table[4][4] = table[5][1] = table[6][6] = table[7][3] = table[8][0] = a[4];
table[0][6] = table[1][3] = table[2][0] = table[3][8] = table[4][5] = table[5][2] = table[6][7] = table[7][4] = table[8][1] = a[5];
table[0][1] = table[1][7] = table[2][4] = table[3][0] = table[4][6] = table[5][3] = table[6][2] = table[7][8] = table[8][5] = a[6];
table[0][2] = table[1][8] = table[2][5] = table[3][1] = table[4][7] = table[5][4] = table[6][0] = table[7][6] = table[8][3] = a[7];
table[0][0] = table[1][6] = table[2][3] = table[3][2] = table[4][8] = table[5][5] = table[6][1] = table[7][7] = table[8][4] = 9;
memcpy(temp, table, sizeof(table));
for (int c1 = 0; c1 < 2 ; c1++)
for (int c2 = 0; c2 < 6 ; c2++)
for (int c3 = 0; c3 < 6 ; c3++)
for (int r1 = 0; r1 < 2 ; r1++)
for (int r2 = 0; r2 < 6 ; r2++)
for (int r3 = 0; r3 < 6; r3++) {
combina(c1, c2, c3, r1, r2, r3);
if (count == num) {
ofstream out;
out.open("sudoku.txt", ios::out | ios::trunc); // 寫入前先清空檔案
out << str;
out.close();
return;
}
}
next_permutation(a, a + 8); // 按升序進行全排列一次，隻排列前8個元素
}
}
這裡生成種子時，采用了next_permutation這個标準庫裡的函數，其作用是将所給範圍内的元素進行升序排列一次，能升序則改變數組并傳回true，否則傳回false。由于1000000的上限決定了不可能用完所有種子，是以無須判斷。然和根據種子生成的終盤，進行行列變換。
void FianlMaker::combina(const int& c1, const int& c2, const int& c3, const int& r1, const int& r2, const int& r3) {
memcpy(table, temp, sizeof(temp));
if (c1 == 1)
colExchange(1, 2);
switch (c2) {
case 1:
colExchange(4, 5);
break;
case 2:
colExchange(3, 4);
break;
case 3:
colExchange(3, 4);
colExchange(4, 5);
break;
case 4:
colExchange(3, 5);
colExchange(4, 5);
break;
case 5:
colExchange(3, 5);
break;
}
...
tableToString();
}
這裡根據6個參數選擇行列變換，确定具體變換方式，然後将該終盤數組轉化為字元串
const int maxrow = 9 * 9 * 9;
const int maxcol = 1 + 9 * 9 * 4;
const int num = maxcol + maxrow * 4; // 總元素個數, 第一個為Head元素,接着9*9*4個為列标元素,最後9*9*9*4個為“1”元素
int Left[num], Right[num], Up[num], Down[num]; // 每個元素的4個方向分量（相當于連結清單中的箭頭）
int Col[num]; // 記錄每個元素的列标元素
int Row[num]; // 記錄每個元素所在的01矩陣行數
int Size[maxcol]; // 記錄每列的“1”元素個數
int Head[maxrow]; // 記錄每行第一個“1”元素
int table[9][9]; // 數獨
int no; // 元素編号
DLX算法用到的交叉十字循環雙向鍊，用數組來實作這一結構
void SudokuSolver::link() {
/* 連結列标元素 */
for (size_t i = 0; i < maxcol; i++) {
Left[i] = i - 1;
Right[i] = i + 1;
Up[i] = Down[i] = i;
Row[i] = 0;
Col[i] = i;
Size[i] = 0;
}
/* 連結Head元素 */
Left[0] = maxcol - 1;
Right[maxcol - 1] = 0;
no = maxcol;
/* 連結“1”元素 */
for (size_t i = 0; i < 9; i++) {
for (size_t j = 0; j < 9; j++) { // 周遊9x9數獨
int k = table[i][j];
if (k) {
for (size_t t = 1; t <= 4; t++) { // 每個非0數字會在01矩陣中産生4個“1”元素
Left[no + t] = no + t - 1;
Right[no + t] = no + t + 1;
Row[no + t] = i * 81 + j * 9 + k - 1;
}
Left[no + 1] = no + 4;
Right[no + 4] = no + 1;
Head[Row[no + 1]] = no + 1;
/* 将4個元素插入列鍊中 */
insertNode(i * 9 + j + 1, no + 1);
insertNode(81 + i * 9 + k, no + 2);
insertNode(81 * 2 + j * 9 + k, no + 3);
insertNode(81 * 3 + (i / 3 * 3 + j / 3) * 9 + k, no + 4);
no += 4;
}
else { // 該位置為0，即待填
for (size_t k = 1; k <= 9; k++) { // 構造9種填法
for (size_t t = 1; t <= 4; t++) { // 生成并連結它們的元素
Left[no + t] = no + t - 1;
Right[no + t] = no + t + 1;
Row[no + t] = i * 81 + j * 9 + k - 1;
}
Left[no + 1] = no + 4;
Right[no + 4] = no + 1;
Head[Row[no + 1]] = no + 1;
insertNode(i * 9 + j + 1, no + 1);
insertNode(81 + i * 9 + k, no + 2);
insertNode(81 * 2 + j * 9 + k, no + 3);
insertNode(81 * 3 + (i / 3 * 3 + j / 3) * 9 + k, no + 4);
no += 4;
}
}
}
}
}
這是形成交叉十字循環雙向鍊的函數，負責将1個Head元素+9*9*4個列标元素+9*9*9*4個“1”元素連結起來，即DLX算法中的DancingLink部分。
bool SudokuSolver::dfs(int select){
if (select > 81) // 已選夠
return true;
/* 周遊列标元素，選一個元素最少的列（回溯率低） */
int c, minnum = INT_MAX;
for (size_t i = Right[0]; i != 0; i = Right[i]) {
if (Size[i] == 0)
return false;
if (Size[i] < minnum){
minnum = Size[i];
c = i;
}
}
remove(c);
/* 周遊該列各“1”元素 */
for (int i = Down[c]; i != c; i = Down[i]){
int row = Row[i];
table[row / 81][row % 81 / 9] = row % 9 + 1; // 根據該元素的行填入數獨
for (size_t j = Right[i]; j != i; j = Right[j]) // 移除與該元素同行元素的列
remove(Col[j]);
if (dfs(select + 1)) // 已選行數+1，遞歸調用
return true;
for (size_t j = Left[i]; j != i; j = Left[j]) // 遞歸傳回false，說明後續無法滿足，故恢複與該元素同行元素的列，循壞進入本列下一進制素
restore(Col[j]);
}
restore(c);
return false;
}
這是求解精确覆寫問題的X算法中的核心部分，即按深度優先周遊遞歸求解
PSP表格
| PSP2.1 | Personal Software Process Stages | 預估耗時（分鐘） | 實際耗時（分鐘） |
|---|---|---|---|
| Planning | 計劃 | ||
| · Estimate | · 估計這個任務需要多少時間 | 10 | 20 |
| Development | 開發 | ||
| · Analysis | · 需求分析 (包括學習新技術) | 120 | 180 |
| · Design Spec | · 生成設計文檔 | 30 | |
| · Design Review | · 設計複審 (和同僚稽核設計文檔) | 5 | |
| · Coding Standard | · 代碼規範 (為目前的開發制定合适的規範) | ||
| · Design | · 具體設計 | 60 | |
| · Coding | · 具體編碼 | 500 | 600 |
| · Code Review | · 代碼複審 | ||
| · Test | · 測試（自我測試，修改代碼，送出修改） | 300 | |
| Reporting | 報告 | ||
| · Test Report | · 測試報告 | ||
| · Size Measurement | · 計算工作量 | ||
| · Postmortem & Process Improvement Plan | · 事後總結, 并提出過程改進計劃 | ||
| Total | 總計 | 1090 | 1480 |
一些感想
草草估計了下，花在這個項目上的時間已經24h了（實際可能更多）。開學這第一周可以說也沒幹别的事，成天腦子裡想的都是學C++、找算法、看教材、寫部落格、組隊……寫煩的時候會想“這真的是兩學分的選修課？花的時間和計組差不多了！”又加上經曆了前後加入的兩個組 組長都帶着半組人退課了這種事，有那麼一刻真的想我也退了算了。理由可以找很多：我沒有C++基礎上來就寫大項目太難了、編譯+資料庫+安卓 課業已經很重了……但其實心知肚明，都是想偷懶的借口。上這課隻是為了學分嗎?畢業想參加工作的我肯定不能隻為混學分。課業雖重，但咬咬牙總能過去。That which does not kill us makes us stronger.
扯遠了，說回這個項目。花了一下午找算法并看懂，花了一天完成初版。然後本來打算做附加題的，但這幾天的時間都花在性能優化上了，再加上一直沒怎麼寫過GUI也不熟悉Qt，就不了了之。 優化的結果還是比較滿意的，從初版的一分多鐘到現在的1.5秒，其中走了很多繞路。舉個例子，之前因為友善都是用string的+=拼接字元串，可沒想到比直接操作char*慢這麼多。(在此之前，還查了+=、append、stringstream、sprintf的效率比較)類似的還有各種檔案IO的處理。也仍有一些不懂的地方，比如VS的編譯優化是怎樣做到的？還有調試時出現的一些link錯誤也沒真正弄懂背後的原理。以前寫代碼時幾乎沒怎麼想效率問題，現在算是有些明白老師講的“軟工作業寫個隻存了五六本書的圖書管理系統有什麼用”了。
雖然現在想想後面的結對、團隊項目仍有點頭皮發麻，但也明白“輕輕松松就完成的作業相當于沒做”。路在前方，唯行而已。